Drawing a directed graph with ASCII-characters in Emacs (Part 1)

I recently wrote emaci, a Continuous-Integration server in Emacs. It already proved to be quite usable. So far it's very simple queue managment system, that has multiple queues of jobs and executes each job of a queue serially. Having multiple queues allows parallelization and having multiple jobs in a queue introduces dependencies. Because each job can also checkout a branch or apply stashes of a git repo (quite useful when working locally) I found my self in a situation where I wanted 2 sets of parallel jobs with a dependency to the other set. That's not possible with my current setup so I need a proper dependency graph. Implementing the graph is probably quite easy (if you don't care about any validation, like cycles etc). But since I also visualize the jobs in a managment buffer, I need to draw those graphs with just plain text. I could use graphviz or something similar. I tried it and it works quite well, but it introduces a dependency and is probaly not really interactive.

So I set my goal to implement a graph drawing algorithm with will produce ascii graphs. I googled "drawing directed graphs" and took the first paper that I found. It has the fitting title A technique for drawing directed graphs.

Gansner, Emden R., et al. "A technique for drawing directed graphs." Software Engineering, IEEE Transactions on 19.3 (1993): 214-230.

All that follows is described in the paper and not my research work. Credits to Ganser, Emden R. and the rest for their work. It's quite enjoyable. Not an extensive research I did there but that paper was published when I was born (which is an irrational excuse for me being lazy researching some more). Then again, I might have found a way easier to implement paper. Anyway I'm currently reading through the paper and taking notes. So far it seems doable even though I have absolutely no background in graph theory or maths. But all the formulas kinda make sense and are quite simple. I'm afraid of the parts where the paper doesn't go into much detail. But I'll learn soon enough and I could always find somebody that might help me with it (in exchange for a good Single Malt Whisky).

It's midnight and tomorrow is bank holiday. Let's see how far we get.

Main algorithm

So it all starts very simple.

(defun draw-graph ()
  (rank)
  (ordering)
  (position)
  (draw-edges))

There is obviously some hidden state. I have to resolve that later and make it more functional. But I should be able to break down each part as much as possible until I finally have an algorithm that shits out ASCII-graphs.

So first we place nodes in discrete ranks with a network simplex algorithm. Simplex doesn't mean it's trivial, sadly. But probably quite simpler than other solutions. Ranks are the levels of the graph:

a -- b -- c
  \- d

Here we can see that a has rank 0, b and d have rank 1 and c has rank 2. So far so simple(x). Then we order nodes in that graph to avoid edge crossing. Afterwards we calculate the positions of each node, taking into consideration the size of each node. Then we draw edges. The paper uses spline curves. I have to come up with something simple/clever.

A edge can have a weight. I don't think I'm gonna need weights, so I have to see if that would simplify the formulas. So far I know that delta(e) defines the minimum edge length that I or the user can set. Probably a defcustom variable, right? The length of each edge has to be greater or equal. It's defined via lambda(weight) - lambda(node). I have no idea what lambda is yet, but at least the weight is gonna be 1. Leaf edges are trivially calculated (plus 1 of the highest parent node). I have to take in to consideration, that I might have multiple graphs for one build. Let's see how I'm gonna sequeze them in. Single nodes should also find it's place somewhere.

The rank algorithm first needs to find a feasible tree. Then edges are replaced to optimize that tree. Afterwards the tree is normalized and balanced, meaning minimum rank is zero and nodes that can go to multiple ranks are placed to ranks with minimum amount of nodes to avoid clustering:

(defun rank ()
  (feasible-tree)
  (let (e)
    (while (setq e (leave-edge))
      (exchange e (enter-edge e))))
  (normalize)
  (balance))

e are edges. Finding the feasible tree already is quite a thing. The paper gives the following pseudo code:

(defun feasible-tree ()
  (init-rank)
  (while (< (tight-tree) (absolute-value V))
    (let ((e (get-non-tree-node-incident-on-tree-with-min-slack))
          (delta (slack e)))
      (when (eq incident-node (e-head e))
        (setq delta (- delta)))
      (mapc
       (lambda (v) (setf (v-rank v) (+ (v-rank v) delta)))
       tree)))
  (init-cutvalues))

v is a node (math, right? Use m,n always to make it hard to read but here use v).

Slack of an edge is simple:

(defun slack (edge)
  (- (length edge) (min-length edge)))

If the slack is nonnegative for every edge the ranking is feasible. If the slack is zero the edge is tight.

The rest of the feasible tree algorithm is quite a read. I'm 90% sure what to do, but I'm gonna continue this in the next part. First I want to read further to understand it in more detail.

Coincidentally I'm currently listening to the song We don't know by the Strumbellas. I hope it's not a bad sign.

Continue in part 2.

Storax

Drawing a directed graph with ASCII-characters in Emacs (Part 1)

Main algorithm

Comments