Layered Graph Drawing

Sugiyama-style graph drawing: https://en.wikipedia.org/wiki/Layered_graph_drawing

Overview Paper:

An Efficient Implementation of Sugiyama’s Algorithm for Layered Graph Drawing

Sugiyama consists of several steps:

Starting with

1. A directed graph without cycles

 

2. Find the longest path and add connection vertices

Find the nodes that have no children and walk backwards, putting all parent nodes in layers. If a connection line passes over several layers, a node has to be added in every layer.

 

3. Crossing Reduction

Using: Simple and Efficient Bilayer Cross Counting

 

4. Y-placement (works, but is not an average of alignments)

Using: Fast and Simple Horizontal Coordinate Assignment

 

Example Usage

You can test this library by

• Uncommenting the diagrams-code in app/Main.hs and uncommenting the diagrams-dependencies in layerd-graph-drawing.cabal
• cabal build or stack build
• generate the upper image by executing cabal run graph-drawing-exe -- -w 400 -o g3.svg

Algorithm extensions (vertical and virtual edges, ports)

• Sometimes nodes have to be drawn vertically below each other. To force the algorithm to do this, you have to connect them with vertical edges. The edges are not drawn, but guide the algorithm, which unfortunelty made the algorithms (especially longest path) more complex.

• Virtual edges are also not drawn but are used when several unconnected graphs have to be displayed in a a row. I don't know if this was the best decision.

• A node can have sub fields (ports), which is important when these sub fields are connected separately to other nodes. The number of this port is used in Crossing reduction.

Putting the graph in a box

The module SubgraphWindows contains an algorithm that calculates boxes around graphs and subgraphs by using a nesting attribute and box id of the node, adding border and nesting attributes to every cell of the html table. When you generate nodes that should be in a box, put the boxId of the current box to every node. The algorithm in subgraphwindows then adds borders to every cell of the table.

This algorithm was implemented to develop a visual programming environment, which is work in progress: www.autocompletion.io

Y-Placement in Javascript (advanced)

The normal layout is to use a table and then to place each node in a table cell with integer x,y coordinates. This can lead to unpleasant white space when a node is big and other nodes are small:

 

If you display the graph in html this can be solved by replacing the table with individually sized divs in a column.

 

 

The code to calculate the size of the divs in my application could only be done in javascript because the size of the nodes depends on the the html+css layouting.

We calculate the blocks for y-positioning (YBlockLines) with the function

layeredGraphAndCols ::
  (NodeClass n, EdgeClass e, ShowGraph n e) =>
  Bool ->
  CGraph n e ->
  (CGraphL n e, (Map.Map GraphMoveX [UINode], Map.Map Int ([Column], YBlockLines)))
layeredGraphAndCols cross graph = (g, getColumns g)

Copy these blocks in the backend into the html, so that javascript can use them

In graph-drawing.js there is a function setHeightsOfColumnCells which does the y-placement in javasript.