Unix Family Tree

Directed graph flow layout and shortest-path edge routing

This is a cola.js rendering of the classic graphviz dot example. We use graphlib-dot.js to parse the dot file. The initialization for cola here is interesting:

d3cola
    .avoidOverlaps(true)
    .flowLayout('x', 150)
    .size([width, height])
    .nodes(nodes)
    .links(edges)
    .jaccardLinkLengths(150);

In particular, the call to flowLayout causes all edges not involved in a cycle (strongly connected component) to have a separation constraint generated between their source and sink, with a minimum spacing set to 150. Specifying the 'x' axis achieves a left-to-right flow layout. The default is top-to-bottom flow layout (i.e. 'y'). You can also specify a function as the second argument to flowLayout that returns different separations for each edge. Specify a different minimum as a second parameter to flowLayout.

Another feature of this example is shortest-path edge routing. That is, after layout stops, the edge paths are routed to avoid passing through node boundaries. To do this, we call the following function on the layout "end" event:

var routeEdges = function () {
    d3cola.prepareEdgeRouting(margin / 3);
    link.attr("d", function (d) { return lineFunction(d3cola.routeEdge(d)); });
    if (isIE()) link.each(function (d) { this.parentNode.insertBefore(this, this) });
}

The function prepareEdgeRouting(padding) creates a tangent visibility graph over the polygonal boundaries of the nodes. The padding parameter controls how close edges can come to the node boundaries. Here we set it to be a third of the minimum spacing that layout allows between nodes. This visibility graph looks like this:

The call to d3adaptor.routeEdge for each edge, uses the Dijkstra algorithm to find a shortest path through the visibility graph from the centre of the source node to the centre of the target node.

The last bit: if (isIE()) link.each(... is an IE10/11 specific hack to force it to redraw the edges. This is necessary because IE has trouble with SVG markers (in this case the arrow heads).