Directed acyclic graph using d3.js without DOT

Question

I am trying to draw directed acyclic graph using d3.js. While searching for the layout, I came across Dagre but it seems to be of less use as I do not want to use DOT based code anywhere. If anyone knows about pure Javascript solution for this or plugin/custom layout for DAG, please let me know. Thanks in advance.

Solution 1

Dagre author here. Dagre doesn't include any of the graphviz code - it is pure JavaScript. It is based on similar layout techniques though; both are based on techniques from the Sugiyama paper.

You can find some examples of dagre here:

http://cpettitt.github.io/project/dagre-d3/latest/demo/interactive-demo.html http://cpettitt.github.io/project/dagre-d3/latest/demo/sentence-tokenization.html http://cpettitt.github.io/project/dagre-d3/latest/demo/tcp-state-diagram.html

The minified source can be found here: http://cpettitt.github.io/project/dagre-d3/latest/dagre-d3.min.js. It clocks in at about 44K.

Solution 2

Rendering directed acyclic graphs (and actually highlighting the directedness property) is a domain of the Sugiyama layout algorithms.

They basically assign layers (through a topological sorting) to the nodes and then calculate a sequencing for the nodes in the layers. Using a simple heuristic to reverse cycles first, this works well for cyclic graphs as well. Graphviz DOT has an implementation of this layout called dot, which is also the name of the file format it uses, so there sometimes is a bit confusion when DOT is mentioned.

Of course there are other implementations of the algorithm, even a cross-compiled Javascript version of dot is available. The probably most feature-complete solution available for Javascript is the commercial implementation of the algorithm in the yFiles library. So if this is in a commercial scenario, you might want to take a look at the corresponding live demo. Note that although yFiles comes with its own rendering and editor implementation, you could still plug the code into d3.js, since the layout algorithms can be used as standalone implementations to "just" calculate the coordinates of the nodes, the edge connection points, the bends, and the labels. This specific implementation supports a great number of additional constraints, like "Port Constraints" (to restrict the direction of the outgoing and incoming edges as well as their exact locations at the nodes), hierarchically grouped nodes (where each node can have a parent node and the parent node "contains" all of its child nodes), layer and sequence constraints, edge labeling constraints, different edge routing styles, bus-routing, and more.

Disclosure: I work for the company that creates said library, however on SO I do not represent my employer.