Graph Layout Algorithms

Mike C. Fletcher mcfletch at
Tue Sep 10 10:05:20 EDT 2002

Boa Constructor has some code in their UML view that I contributed to do 
this using topological sorts.  The topological sorting algos (one by me, 
one by Tim) are available seperately here (as

if you don't want the GPL contamination of using Boa's copy.

Basically, you do the topo-sort, then lay out each generation 
above/below next/previous generations.  For really nice-looking graphs, 
you'd want to do some post-processing to make children show up 
underneath parents as much as possible (i.e. minimise number of crossing 
arcs in the graph), and maybe do some work with spacing so that each 
generation takes up approx. the same amount of space.


Duncan Smith wrote:
> Hello,
>          Just wondering if anyone has implemented anything in Python.  I
> need to lay out my graphs (directed acyclic / undirected / trees) in a
> reasonably clear way.  So if anyone has already implemented anything, or if
> anyone has advice on appropriate algorithms, I'd be glad to hear about it.
> Cheers.
> Duncan
   Mike C. Fletcher
   Designer, VR Plumber, Coder

More information about the Python-list mailing list