The Sugiyama Method - Layered Graph Drawing
I’m a dual study programme student at Disy and
the DHBW. As part of our
lecture on software engineering we had to do an assignment. Since I am lazy I
said to myself I’ll do something simple and be done with it in a jiffy. So I
decided to create a step-by-step algorithm visualisation to transform a
deterministic finite automaton (from here on
dfa) to a regular expression. I chose to use web
technologies, giving me fast feedback and a vast ecosystem of libraries
to use. The first steps were indeed simple and done in no time. But then I hit a
brick wall: I couldn’t find a library to draw layered
graphs. D3, the de-facto standard library for
This method doesn’t produce pretty graphs for
dfas. There is a plugin for
wrapping viz.js for gaining access
to Graphviz layout algorithms. But
with emscripten, clocking in at
1.6 MB. So I had to roll my own.
Note: Use dagre
In the meantime I discovered dagre, a library doing everything I needed.
The Sugiyama Method - Steps and Resources
The Sugiyama Method consists of 4 Steps:
Cycle Removal: The graph representing the
dfamight contain cycles. These have to be removed.
Layer Assignment: Vertices are assigned to layers.
Vertex Ordering: Dummy vertices and edges are added to the graph so that every edge connects only vertices from adjacent layers. Vertices in a layer are reordered so that edge crossings are minimised.
Coordinate Assignment: Assign coordinates to vertices.
I used these excellent resources to guide my implementation:
We are going to represent a graph with this class
Given a simple cyclic graph, such as the one in figure 1, the
CycleRemover will loop through all vertices and perform a depth-first
search for every vertex. If one of the edges used for the depth-first search
leads to a vertex that is already on the stack, we have detected a cycle and
remove this edge (line 27). If this isn’t the case we visit the next vertex
This depth-first search based algorithm isn’t the only one to make an graph acyclic. Visualisation of state machines using the Sugiyama framework mentions several other algorithms.This leaves us with this acyclic graph:
Abovementioned papers use algorithms like ‘Longest Path from Tamassia’ or ‘Network Simplex’. I opted to use a topological sort of the acyclic graph. The results may not be optimal but the algorithm was implemented in a timely manner.
First of all we make defensive copies of the
edges. Next we
look for all vertices with no incoming edges. These vertices are added to the
sorted array. After that we remove all edges that originated from these vertices.
The vertices that are already in the sorted array can be removed from the graph.
Once this is done we look again for all vertices with no incoming edges and loop
until there are no vertices left.
Vertex Ordering first replaces edges spanning multiple layers with smaller edges that only span one layer at a time. To do this, it sweeps the layers and determines for every vertex if the vertex is part of such an edge. If this is the case, the edge is removed from the graph. A virtual vertex is inserted into the next layer and two smaller edges are inserted into the graph, connecting the two original vertices with the new virtual vertex.
Now we have a graph without edges spanning multiple layers. For this graph we apply the following steps 23 times (this magic number was taken from the paper).
The median heuristic sweeps through the graph (on even iterations from left to right or else vice versa) and places every vertex at the median position of its neighbours.
transpose method transposes vertices in a layer and checks if this
improves the number of crossings.
If there are less crossings after these steps, the changed graph is set as the new best solution.
Sometimes this algorithm does not find the optimal layout. But for most cases it finds an adequate solution.
Now that we have ordered the vertices in a layer, we can move on to assigning coordinates to each vertex.
Coordinate Assignment tries to draw the graph as compact as possible. Another criterion to optimise is aesthetics. Edges shouldn’t have sharp or unnecessary bends.
In my implementation I skipped this step and simply positioned the vertices at equal
distances. The layers are drawn in columns, which are then distributed
evenly across the width of the
SVG element. Vertical spacing is done in a
similar fashion. The first vertex of each layer is positioned in the top-most row and
all following vertices are placed below their predecessor. For simple graphs
this works quite well.
To draw the splines connecting vertices through virtual vertices I used
Catmull-Rom splines and converted them to the Bezier paths that
More involved algorithms are described in the linked papers.
Layered Graph Drawing is quite complex. I wish I had found
dagre earlier in
the process. The other brick wall I hit during development was the
simplification of regexes. The algorithm I used creates rather large
expressions with every step. My implementation still doesn’t simplify some cases that
are obvious to the human eye. Especially if the source
dfa isn’t minimised, the
resulting expressions slow down latex rendering.
The Sugiyama Method can use many different algorithms for each step. In my case I didn’t need to choose the best algorithms and sometimes just employed brute force.
If you want to try it out, visit regex-tool. The interface is in German, but just try the buttons labelled ‘Beispiel…’.