Also returns a map with Columns to allow navigation with arrows

layered graph drawing with subgraph layouting

Layout a directed acyclic graph in several steps (Sugiyama) 1. Assign the nodes to several layers (longest path) 2. Dummy vertices for lines that are longer than a layer 3. Reduce crossings, place the longest path on top 4. Assign y-coordinates to the nodes so that long lines that pass several layers are as straight as possible

Similar to longestPathAlgo, we take the rightmost node (which is an output type node) and explore the graph from there to the left When a function is exploded the nesting value of every node of this subgraph is increased by one by the explosion (ExplodeImplode.hs). A difference of the nesting value of two adjacent nodes signals a new subgraph. This function returns a map of subgraphs with a nesting and which graph is embedded in another graph

No spaces between the nodes. This is good for testing purposes, because it is simple

See "Fast and Simple Horizontal Coordinate Assignment" (Brandes, Köpf)

Takes two layers and returns a list of lists of independent edges. A list A of edges is independent of a list B of edges if every edge of A does not intersect or connect any edge of B. This sweeping should save some time because graphs often have edges crossing near to each other. The number of intersections has been reduced in crossingreduction. Because of this we can assume that most edges are quite short and rectangular to layer0 and layer1. A sweep in the parallel direction of the two layers should reduce the number of edges that have to be examined. The overall algorithm (sweep + resolve) should have a runtime more like n*log(n) instead of n², because we only have to search for conflicts inside of these independent lists. The Brandes-Köpf paper is not explaining very well how they find intersections between two layers. I doubt that the whole algorithm is O(n). It seems more like a quadratic runtime in the worst case. Even finding the number of intersections (without giving back the exact edges that intersect) is O(n log n), See: Simple and Efficient Bilayer Cross Counting by Barth, Mutzel, Jünger or chapter 33 of Cormen: Introduction to algorithms If several edges emanate from a node the algorithm takes (one of the) the median. (e.g. three edges have one median, 4 edges have two) The sweep works by looking at the next node in the two layers, and comparing which node deletes more edges and introduces less new edges from the set of edges to look at. Every edge has a start node (first appearing at its y-position) and an end node. A start node means adding an edge when its source or target node appears in one of the two layers, and the edge disappears when both its nodes have been swept over.

Either e0 prevails against all e1s or all e1s prevail against e0

Compare all edges of a layer with each other. Worst case: O(n²). But n can shrink fast in every round and n is small, because of sweepForIndependentEdgeLists

The resolveConflicts-algorithm has to be constructed in a consistent way It should be impossible that edge e has priority to edge x (keeping e), and another edge y has priority to edge e (deleting e). It would not be clear if e has to be deleted or not

Given two edges that intersect or connect, which one will prevail?

Similar to Brandes-Köpf but without arrays and no placement of blocks The basic algorithm is longest path. debugging can be done with graphviz, also uncomment line 533 in longestPath | otherwise

Every graph has a longest path, which is the center of attention for us Return layers of node ids This algorithm is a little bit more complicated because we have to connect nodes vertically, so that they are guaranteed to be all in one vertical layer All nodes before this vertical layer have to be placed in layers before we can proceed

partition nodes into non-vertically connected nodes and vertically connected nodes

Some functions don't have an input (e.g. True). But a function without input can only appear directly after a case node That's why we insert a connection node between this case node and the function node

To prevent crossing reduction from changing the order of vertically connected nodes we insert them in the right order again

Crossing reduction is like taking a comb and aligning a chain of nodes from left to right and right to left until it is ordered with as little crossings as possible

One pass right to left and left to right

Arrange vertical nodes directly below each other, returns Nothing if there are no vertical nodes in this layer

Assign every node in l1 a number thats the barycenter of its neighbours in l0, then sort. If the node is marked as a vertical node with a number, this number has precedence in sorting subgraph layouting is done here, by sorting nodes inside of blocks recursively

Sort two edges lexicographically after their y-position in the layer An edge has two points, each point has a y-position (e.g. e0y0) and a node number (e.g. e0n0)

See: Simple and Efficient Bilayer Cross Counting by Barth, Mutzel, Jünger

Modified merge sort for counting of edge crossings which is the same as counting inversions (see) http://www.geeksforgeeks.org/counting-inversions/

The idea behind the following heuristic: Very frequent chaining of functions are obvious and need no attention, e.g. Data.Text.pack str unusual chainings need the highest attention a long path means it is the main path of activity, like a table of contents in a book that is a guide where to go. This long path should be a straight line at the top of the page.