Now I honestly don't know if there really is a Mount Sugiyama out there. I've gone hiking many times, but have never had the opportunity or gumption to go scaling up one of 'em big ole mountains. Intellectually though I consider myself to be going on a hike of sorts, this hike being through the Sugiyama drawing framework mentioned in an earlier post. In that post I listed the four general steps of that framework which I will repeat now:
1. remove all directed cycles in your input digraph
2. partition the vertices into groups/layers. The edges of the graph will run between these layers.
3. reorder vertices within layers so as to reduce edge crossings
4. reassign vertex x-coordinates
I have already discussed the first step in a previous post so now on to the second step: layering (i.e. the treacherous path of Mount Sugiyama!!!!)
Before going into algorithm details we should first remember the main purpose of the Sugiyama method: to visualize a directed graph in hierarchical fashion. After giving your digraph the layering treatment it should look something like the following illustration, with vertices bunched into groups/layers and the majority of edges pointing in one direction (up, down, left, right,...etc.). It is the layering step that is responsible for the nice partitioned vertex sets and the uniform edge flows.
Now, how exactly is layering accomplished? As with the first task of removing directed cycles, many different algorithms have been proposed for this problem, each with its own set of advantages and disadvantages. Of all of the layering algorithms in existence the simplest is what is often referred to as the longest path algorithm. It basically works by building up the digraph's layers in a bottom up fashion so that the majority of edges are pointing down. Here is a summary of the algorithm's pseudocode:
Input: directed acyclic graph G = (V, E)
Output: layering
Initialization:
create two empty sets V1 and V2
create an integer variable currentLayer = 1
while |V1| < |V| (Here |V| means the cardinality of V and ditto for V1)
Select a vertex v in V\V1 s.t. all of its outgoing neighbors form a subset of V2. If such an element exists then assign it to the current layer and append it to U.
Else increase currentLayer by one and let Z be the union of Z and U.
The algorithm is simple enough to explain, but it's extremely important to understand exactly what is going on. Let's look at the first selection statement. At the very beginning of each while loop iteration we are trying to find a vertex such that all of its outgoing neighbors form a subset of V2. V2 is initially empty so the step starts by looking for vertices that have no outgoing edges, namely the sinks. Every time that a sink s is found it is assigned to layer 1 and appended to vertex set V1. Following the algorithm you will continue to do this until no more sinks are left. Note that there will be at least one vertex in layer 1 since every digraph has at least one sink (See if you can prove this! Proofs are fun :-D ).
After handling all of the sinks we now reach the point where there is a vertex with positive outgoing degree. Its set of outgoing neighbors clearly can not be a subset of the empty set V2. So we increment currentLayer to 2, take the union of V2 with V1 so that it now has all of the graph's sinks, and troop on.
Again, we check to see if there is a vertex not yet processed that has all of its outgoing neighbors contained in the previous layer(s). Assuming that we just finished handling all of the sinks the question is, is there a vertex that has nothing but sinks as its outgoing neighbors? The answer is yes (again try to prove it! Leave a comment if you would like to see a proof of this and the previous claim ;D ). So we assign that vertex to the currentLayer which is 2, and proceed. If an unprocessed vertex has at least one neighbor that isn't assigned to a layer, then we are forced to increment currentLayer and take the union of V2 and V1. The observant reader should note that the topmost layer will contain the source(s) of the digraph.
The very crucial part that I want to point out here is the condition that a vertex can not be assigned to a layer until all of its outgoing neighbors have been given layers. This is the condition that ultimately creates the uniform edge flows in our hierarchical drawings. The edge flow produced by this algorithm will be from top to bottom. If you assign a vertex to a layer before one of its outgoing neighbors, then you will get an edge pointing up (against the flow) once that particular neighbor is processed. That is not what we want in this kind of drawing, so when programming the longest path algorithm, be sure to check the status of all of the outgoing neighbors of a vertex before giving it the layering treatment. The only time in the Sugiyama method that you will tolerate having edges against the flow is after layering is complete. Once that part is done you can reinsert or reverse the direction of edges that were handled when removing directed cycles (Step 1).
So yeah...remember that!
A few last things I thought I would point out about longest path layering concern its computational and aesthetic pros and cons. Pros: the algorithm is simple, runs in linear time, and constructs a hierachical layout with minimum height.
Cons: Other aesthetic criteria such as edge densities and drawing width are not met so well by the algorithm. In particular, drawings produced by the longest path algorithm tend to be wider at the bottom.
Remember that too! :-D
As with all of my graph theory posts I really enjoyed researching the material for this one. It's fascinating that there are so many different ways of approaching graph drawing, a problem that initially sounds easy but becomes much more detailed and complex upon further inspection. I like to think of the algorithms and heuristics that I pick up on my graph visualization journey as pretty little gems nested inside the walls of a deep dark cavern. Because I enjoyed discussing layering so much, it is possible that I may revisit this topic in a future post. If so then I will most likely discuss another algorithm that is commonly used for layering, the so-called Coffman-Graham algorithm. Until then, keep on graphing and don't be afraid to go searching for some gems to add to your algorithms collection. :-)
