cpettitt/dagre — pull request #95 by solleks (2013-10-17 22:27:05+00:00)
Title: Network simplex ranking

Here is our implementation of network simplex ranking. The pull request represents the delta between your exp-rank-fixes branch (as of commit ede2d945e0f978d7475ed113351277d2f9e8514a) and our simplex branch, which includes exp-rank-fixes. If there's a better pair of commits to diff, I'd be happy to change that.

The rankSimplex property of layout controls whether to use network simplex or not. When rankSimplex is true, ranking will iteratively replace edges with negative cut values in the spanning tree. This implementation is based directly on the algorithm described by Gansner, et al in "A Technique for Drawing Directed Graphs", supplemented by some reading of the graphviz code. All of the complexity comes from maintaining the spanning tree through edge deletions and insertions, and from calculating cut values using only local information. Getting all of the signs right in that code was quite tricky.

I added a trivial test by duplicating the file test/rank-test.js and enabling rankSimplex. The algorithm runs without errors on all of the graphs from the North dataset that we've tried (about 6000 of them), but I still haven't identified the circumstances under which network simplex alters the ranking.