Algorithm for automatic placement of flowchart shapes

Question

My team needs to build a flowchart generator in JavaScript, using either HTML5 Canvas or the D3 library (or anything else more suitable, suggestions welcome). The flowchart will be generated from a directed graph defined in a JSON document. My question is the following: which standard algorithm could we use to facilitate the automated placement of shapes in the flowchart (nodes in the graph) in order to minimize the number of overlapping connections and their lengths?

Answer 1

This is the library I found useful. Its called GoJS. Hope this helps.

Answer 2

The standard algorithm you're looking for is force directed graph: http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing) If you want a lightweight, browser agnostic and efficient FD js library take a look at arbor.js: https://github.com/samizdatco/arbor

IMHO D3 is the most powerful library you'll find (it embeds force based algorithm), but it's not compatible with IE < 9 and a bit lower level (document oriented) than over libraries (less to learn, more to think).

JIT is also a good library (it also embeds force based algorithm), not compatible with IE < 9. It's more like Highcharts for infovis. More to learn (helpers, options, parameters), less to think.

WireIt (YUI3) and JSplump (jQuery) are good plumbing libraries but do not include FD algorithms.

Answer 3

Force-directed algorithm is not exactly optimal for this kind of problems. I'd rather suggest to use a Layered graph drawing (http://en.wikipedia.org/wiki/Layered_graph_drawing) algorithm. A nice JS implementation of such algorithm is Dagre (https://github.com/cpettitt/dagre). You can also take a look at my blog post about auto-layout and rendering of directed graphs: http://www.daviddurman.com/automatic-graph-layout-with-jointjs-and-dagre.html.