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
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:
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:
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>()
4
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 }
12
13 // helper methods and properties omitted
14 }
15
16 class Edge {
17 from: string
18 to: string
19 label: string
20
21 constructor(from: string, to: string, label: string) {
22 this.from = from
23 this.to = to
24 this.label = label
25 }
26
27 equals(other: Edge): boolean {
28 return this.from === other.from
29 && this.to === other.to
30 && this.label === other.label
31 }
32 }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[]
6
7 constructor(graph: Graph) {
8 this._graph = graph
9 this._edges = this._graph.edges;
10 }
11
12 removeCycles(): Graph {
13 for (let vertex of this._graph.vertices.toArray()) {
14 this.dfsRemove(vertex)
15 }
16 return new Graph(this._edges)
17 }
18
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 }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
3
4 constructor(graph: Graph) {
5 this._graph = graph
6 }
7
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 }
21
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[][]
4
5 constructor(graph: Graph, layers: string[][]) {
6 this._graph = graph
7 this._layers = layers
8 }
9
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…’.
Share via
