Graph Layouts (revisited)

[Malcolm Tredinnick]

OK, I was bored on the weekend (well, it was raining on Saturday and
playing on the computer seemed more fun than cleaning the apartment). So I
decided to play around with some graph layout algorithms as a response to
the recent thread where somebody requested such a monster.

Not quite at the point where I'm going to release code yet, but I have a
couple of questions which souls more knowledgeable in graph theory than I
might be able to answer. If people want to just reply via direct email,
rather than to the list, that is fine by me (since the discussion may get a
little dry and technical). However, sometimes I find others' tangential
discussions on here to be interesting anyway, so you decide.

So far I have implemented an algorithm (in Python, of course) that lays out
undirected graphs in a reasonably visually pleasing manner (following an
algorithm  from the proceedings of the DIMACS International Workshop on
Graph Drawing (held at Princeton in 1994 -- proceedings are are the
Springer Lecture Notes in Computer Science, vol 894). My question concerns
*directed* graphs: what extra layout criteria are usually used here? I
assume it would be nice to have as many arrows as possible pointing in the
same general direction -- so that flows in the graph move generally, say,
from left to right.  Anything else that is "usual"?

Just to give people a flavour for what I have done so far: I am leaving the
issues of how to get the graph data in the first place and how to display
the laid out graph at the end up to the user. I am simply writing a class
that is given a graph (which is just a dictionary containing the number of
vertices in the graph and a list of two-tuples (ordered for directed
graphs) which represent the edges) and generates a list of coordinates for
placing the various vertices. Of course, debugging such an abstract class
is a little interesting on its own, so I have also written a module that
generates various "standard" graphs (e.g. complete graphs, chains, wheels,
square and triangular grids, ...) for passing to the algorithm class. I
also have a nearly complete back end that outputs encapsulated postscript.
My intention is to try and write some interfaces to PIDDLE if I feel so
motivated.

Problems that need to be dealt with: The algorithm assumes that all nodes
are basically of zero size. That is, it doesn't worry about wrapping edges
around nodes of significant size. This is on the "to do" list, but is
definitely a version 2 feature.

Well, as usual, I have rabitted on and on and this reads like a vapourware
announcement. The important bit is paragraph 3. Can you help?

Thanks in advance,
Malcolm Tredinnick