So you want to write a program that takes directed graphs and plots them in an aesthetically pleasing manner, huh?
Then you'll probably end up reading about this general approach. (Generally, it's considered more aesthetically pleasing if you draw a digraph such that out edges are in the same direction, edges are as short and straight as possible, and there is a minimum number of edge crossings.)
The 3 letters STT are the initials of the last names of three computer scientists who developed this general approach. The men are K. Sugiyama, S. Tagawa, and M. Toda and they first presented their approach in 1981 in a paper entitled "Methods for Visual Understanding of Hierarchical Systems" which you can find in:
- IEEE Transactions on Systems, Man, and Cybernetics, vol. SMC-11, no. 2, pp. 109-125, 1981.
You'll find a billion references to STT if you ever look into this. Trust me. So here's the general approach:
- Assign all vertices to a set of discrete layers
such that all edges go in the same direction.
- Split every edge that spans multiple layers into
a chain of unit length edges between dummy
router nodes, assigning the intermediate
router nodes to the layers that the edge
spanned.
- Assign all vertices within each layer a discrete
order number.
- Permute the vertex ordering within each layer
so as to find the optimal intra-layer ordering to
reduce edge crossings.
- Shift vertices apart within each layer as necessary
to minimize the number of bends along each edge that
had to be routed through one or more router
nodes.
Once you complete the above steps, the derived layer and
order numbers for each vertex should give you a fairly
nice looking set of coordinates for drawing your graph in
an aesthetically pleasing fashion. Below are some more
details on how to achieve each of the above mentioned steps.
Step 1:
A simple technique for doing this is to perform a depth first search on your graph, and assign each vertex to a layer that corresponds to the maximum depth at which it was visited during the DFS. A common thing you'll see in
the literature on this topic is that it's a good idea to
break cycles in your graph during this step, by temporarily reversing some of the edges. You can then turn them back again when you're done with the other steps.
Step 2:
Just iterate through your vertices examining each of
their edges. For each edge that connects two vertices
that are more than one layer apart, add extra router vertices through which you can split the edge apart into multiple edges.
Step 3:
Consider a breadth first search traversal of the graph, assigning each vertex of each layer an order number that is one higher than the last vertex visited within its same layer.
Step 4:
Now here's the difficult part. Minimizing edge crossings is an NP-hard problem. You're basically going to want to use a heuristic to find an approximate solution. Solutions for this step usually involve a series of iterations in which vertices are swapped within each layer, and the number of edge crossings is checked. And the iterations proceed until an acceptable ordering is derived.
Step 5:
During this step, the vertices within each layer are shifted such that they are pretty much centered above or
below their input and output vertices on adjacent layers.
STT suggests the use of barycenters to perform this step. Some other approaches which are based on STT utilize medians.