Disy Tech-Blog

The Sugiyama Method - Layered Graph Drawing

The Sugiyama Method - Layered Graph Drawing

22.08.2017 | Carlo Götz

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 visualisations in JavaScript, only implements force-directed graph drawing. This method doesn’t produce pretty graphs for dfas. There is a plugin for D3 wrapping viz.js for gaining access to Graphviz layout algorithms. But viz-lite.js is just Graphviz compiled 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:

  1. Cycle Removal: The graph representing the dfa might contain cycles. These have to be removed.

  2. Layer Assignment: Vertices are assigned to layers.

  3. 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.

  4. Coordinate Assignment: Assign coordinates to vertices.

I used these excellent resources to guide my implementation:

Cycle Removal

We are going to represent a graph with this class

 1 class Graph {
 2     private _edges: Edge[]
 3     private _vertices: Set<string> = new Set<string>()
 5     constructor(edges: Edge[]) {
 6         this._edges = edges
 7         for (let edge of edges) {
 8             this._vertices.add(edge.from)
 9             this._vertices.add(edge.to)
10         }
11     }
13     // helper methods and properties omitted
14 }
16 class Edge {
17     from: string
18     to: string
19     label: string
21     constructor(from: string, to: string, label: string) {
22         this.from = from
23         this.to = to
24         this.label = label
25     }
27     equals(other: Edge): boolean {
28         return this.from === other.from
29             && this.to === other.to
30             && this.label === other.label
31     }
32 }
a b d c 0 1 0 1 0, 1 0 1
1: a simple cyclic graph

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 recursively.

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.

 1 class CycleRemover {
 2     private _graph: Graph
 3     private _stack: Set<string> = new Set<string>()
 4     private _marked: Set<string> = new Set<string>()
 5     private _edges: Edge[]
 7     constructor(graph: Graph) {
 8         this._graph = graph
 9         this._edges = this._graph.edges;
10     }
12     removeCycles(): Graph {
13         for (let vertex of this._graph.vertices.toArray()) {
14             this.dfsRemove(vertex)
15         }
16         return new Graph(this._edges)
17     }
19     private dfsRemove(vertex: string) {
20         if (this._marked.contains(vertex)) {
21             return
22         }
23         this._marked.add(vertex)
24         this._stack.add(vertex)
25         for (let edge of this._graph.getOutgoingEdgesFor(vertex)) {
26             if (this._stack.contains(edge.to)) {
27                 _.remove(this._edges, e => e.equals(edge))
28             } else if (!this._marked.contains(edge.to)) {
29                 this.dfsRemove(edge.to)
30             }
31         }
32         this._stack.remove(vertex)
33     }
34 }

This leaves us with this acyclic graph:

a b d c 0 1 1 1
2: the same graph after removing cycles

Layer Assignment

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.

 1 class LayerAssignment {
 2     private _graph: Graph
 4     constructor(graph: Graph) {
 5         this._graph = graph
 6     }
 8     assignLayers(): string[][] {
 9         const sorted = []
10         const edges = this._graph.edges
11         const vertices = this._graph.vertices.toArray()
12         let start = this.getVerticesWithoutIncomingEdges(edges, vertices)
13         while(start.length > 0) {
14             sorted.push(start)
15             _.remove(edges, e => _(start).includes(e.from))
16             _.remove(vertices, v => _(start).includes(v))
17             start = this.getVerticesWithoutIncomingEdges(edges, vertices)
18         }
19         return sorted
20     }
22     getVerticesWithoutIncomingEdges(edges: Edge[], vertices: string[]): string[] {
23         const targets = _(edges)
24             .map(e => e.to)
25             .uniq()
26         return _(vertices)
27             .filter(v => !targets.includes(v))
28             .value()
29     }
30 }

First of all we make defensive copies of the vertices and 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

 1 class VertexOrderer {
 2     private _graph: Graph
 3     private _layers: string[][]
 5     constructor(graph: Graph, layers: string[][]) {
 6         this._graph = graph
 7         this._layers = layers
 8     }
10     orderVertices(): [string[][], Edge[]] {
11         const virtualized = this.createVirtualVerticesAndEdges(this._layers, this._graph.edges) 
12         const layers = virtualized[0]
13         const edges = virtualized[1]
14         let best = this.copy(layers)
15         for (let i = 0; i < 24; i++) {
16             this.median(layers, edges, i)
17             this.transpose(layers, edges)
18             if (this.crossing(layers, edges) > this.crossing(best, edges)) {
19                 best = this.copy(layers)
20             }
21         }
22         return [best, edges]
23     }
24 }

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.

 1 private createVirtualVerticesAndEdges(layers: string[][], edges: Edge[]): [string[][], Edge[]]{
 2     let virtualIndex = 0
 3     for (let i = 0; i < layers.length - 1; i++) {
 4         const currentLayer = layers[i]
 5         const nextLayer = layers[i + 1]
 6         for (let vertex of currentLayer) {
 7             const outgoingMulti = _(edges)
 8                 .filter(e => e.from === vertex)
 9                 .filter(e => Math.abs(this.getLayerNumber(e.to, layers) - this.getLayerNumber(vertex, layers)) >1)
10                 .value()
11             const incomingMulti = _(edges)
12                 .filter(e => e.to === vertex)
13                 .filter(e => Math.abs(this.getLayerNumber(e.from, layers) - this.getLayerNumber(vertex, layers)) >1)
14                 .value()
15             for (let edge of outgoingMulti) {
16                 const virtualVertex = `virtual${virtualIndex++}`
17                 nextLayer.push(virtualVertex)
18                 _.remove(edges, e => e.equals(edge))
19                 edges.push(new Edge(edge.from, virtualVertex, edge.label))
20                 edges.push(new Edge(virtualVertex, edge.to, edge.label))
21             }
22             for (let edge of incomingMulti) {
23                 const virtualVertex = `virtual${virtualIndex++}`
24                 nextLayer.push(virtualVertex)
25                 _.remove(edges, e => e.equals(edge))
26                 edges.push(new Edge(virtualVertex, edge.to, edge.label))
27                 edges.push(new Edge(edge.from, virtualVertex, edge.label))
28             }
29         }
30     }
31     return [layers, edges]
32 }

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.

The 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

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 SVG expects.

More involved algorithms are described in the linked papers.

Final Thoughts

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…’.