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.

Neoimpressionism

Answer 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.

Extraversion

Thanks Chris. I studied dagre in detail now but still not clear about few aspects: 1. Can it handle cycles in graph, not a big limitation though? 2. Can I have icons instead of basic shapes in graph layout? – Neoimpressionism

1) It can handle graphs with cycles. 2) It doesn't have special handling for shapes other than rectangles. However,you can override the function that draws the node shape (renderer.drawNode(yourDrawNode)). You can see an example of how that works here: cpettitt.github.io/project/dagre-d3/latest/demo/…. Alternatively, you can use HTML, by starting the label with an HTML element. See the label for node A in this example: cpettitt.github.io/project/dagre-d3/latest/demo/…. – Extraversion

Dagre doesn't seem to be supported anymore and uses d3v3. Are there any good alternatives to dagre? – Rasputin

At first, Dagre-d3 looked promising. However, it is broken on IE.Also, it seems to bury the power of d3 by not using proper d3 coding practices. For example, you can make an html label instead of a text label, by specifying an html flag explicitly. A proper d3 implementation would allow your nodes to be svg tags that you fully control using the enter/update/exit concept. – Metabolism

The links in this answer seem to have been replaced with an Indonesian gambling site. – Stupa

Answer 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.

Alidus

Thanks. Basically, I am shying away from using the graphViz as it requires compilation for each OS but I'll take a look at yFiles. – Neoimpressionism

@AmitGupta: The Javascript cross-compiled version of GraphViz does not need to be "recompiled" of course. However it still feels like a huge binary blob in the browser - it does not have a real API, but it's more like a console application, even in the browser. – Alidus

Yes. I agree. Seems like there is a need of custom layout. – Neoimpressionism

I tried dagre, mxgraph, yFiles, Cytoscape and a lot of others. The most complete implementation is definitley the yFiles Hierarchical Layout Style implementation. I would love to use this layout with d3.js or cytoscape, but I couldn't find anything about it. Could you help? – Prospector

@SimonS. The yFiles library can be used even without their viewer implementation. The algorithms can be run "headless" and all of the relevant properties can read through the API and applied to a d3 graph. The other option would be to use the yFiles viewer implementation and use d3js node renderings. Contact the support team for more details! – Alidus