[Monotone-devel] Drawing graphs (was Re: Ancestry Graph)

[Bruce Stephens]

This isn't monotone specific, so please feel free to stop reading
whenever you want.

I've started looking at the possibility of producing a simple graph
plotting library to replace dot in monotone-viz.  So I downloaded
TSE93.pdf from
<http://www.research.att.com/sw/tools/graphviz/TSE93.pdf>, which
allegedly describes dot's algorithm.  (I say allegedly because this is
from 1993, so presumably things have changed a bit since then.  Also
papers don't always reflect all the details of code accurately,
although I've no reason to believe there's any real problem with this
one.)

In short, it looks quite feasible to do, for graphs of less than a
thousand or so nodes and a suitable number of edges---much as you
might get in a monotone database.  The current monotone.db has 293
nodes and 340 edges, for example.  dot seems to struggle at about 1K
nodes; I don't know what its limit is.  vcg goes larger than that, of
course.

Outlining, as far as I understand it, the algorithm does a depth first
search of the nodes from some node that doesn't have any ancestors,
and thus works out which edges to reverse in order to make the graph
acyclic.  That shouldn't be necessary for monotone's ancestry
database, of course, but it seems easy enough to code.

Then it does rank assignment, arranging the nodes in one direction
(top to bottom, as monotone-viz shows the graph).  The assignment is
expressed as an integer programming problem, and the paper gives
details of a way to solve it reasonably efficiently using a network
simplex technique.  That looked like it had lots of opportunities for
screwing things up, so I'm looking at using some existing code for
that part.

Then you create virtual nodes for edges that are longer than one rank,
so that the remaining steps can deal with edges that are simply
between adjacent ranks.

The next step is to arrange nodes in horizontal order, and their
suggested algorithms look reasonably easy to code.

Then they do horizontal node placement by using network simplex on a
larger graph (i.e., it's a bigger integer programming problem).  They
do vertical placement in some mostly unspecified way, but it doesn't
seem that that part is expensive.

Then they work out how to draw the edges as splines, but that all
looks reasonably straightforward.

I've been looking at lp_solve and glpk, to see if they'd be likely to
be up to solving the integer programming problems.  And it looks to me
like lp_solve, at least, would be.  It can solve the initial rank
problem for a random acyclic graph with 3000 nodes and 9501 edges in
about 30s on my PC, using less than 10M of memory.  glpk looks less
promising, unfortunately (since there's an ocaml binding to it).

Probably it'll be desirable eventually to implement the network
simplex algorithms, since the two problems to be solved are related,
and that can be used to improve efficiency.


Anybody know of any other reasonably well-described algorithms for
drawing directed graphs that I could look at?  Is it even worth trying
to code this up, since the Debian vcg source code looks
unobfuscated---perhaps it would be more useful to try to turn one or
two of the layout algorithms into library form?  (I must admit, I
don't find the graphs drawn by vcg to be as good as those drawn by
dot, but for an interactive application such as monotone-viz it
probably doesn't matter a whole lot.)