Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

D3-dag – Layout algorithms for visualizing directed acylic graphs

github.com

Post reply on HN
Print view View original

31–40 of 44 posts

Re: D3-dag – Layout algorithms for visualizing directed acylic graphs

#31

Post by codethief »

Can anyone recommend a JS library which calculates "optimal" node positions for an acyclic graph under the following constraints:

- Nodes are rectangles that have width and height (they'll later be rendered as HTML divs) and should not overlap

- If possible, edges should not overlap with nodes / cross any node's boundaries

?

I really just need the positions as I would like to have precise control over how and when things are rendered. So far, I've been using WebCola for this and while it works ok, it tends to become quite slow in some situations.

Re: D3-dag – Layout algorithms for visualizing directed acylic graphs

#33

Post by lmeyerov »

kevin_thibedeau wrote: post #23
abs221 wrote: post #18

All these graph layout algorithms should ideally be run on the backend. Most of these js libraries are missing the point in trying to run layout in Javascript on the frontend. If you have a huge graph, you can't view all of it at once anyways and you're viewing a subset of it any 1 moment. So the ideal library should be running the layout on the backend and the frontend should be plain dummy, simply showing each grap…

Then you sacrifice the potential for fluid dynamic layouts. Everyone is walking around with portable supercomputers. May as well use them.

We find that is ok if you build it right for the bulk of business settings. The intuition is that if you can do youtube, streaming layout updates should not be a problem.

I would agree that building a distributed architecture that achieves this is a distraction for most solutions- oriented teams. Before you get to the benefits, most/all teams would drown from the complexity.

Re: D3-dag – Layout algorithms for visualizing directed acylic graphs

#34

Post by brazzledazzle »

zfrenchee wrote: post #24
andrewvc wrote: post #12

Can't believe no ones mentioned webcola yet, which implements some very cool layout algorithms and is the result of cutting edge academic research. https://ialab.it.monash.edu/webcola/

Webcola is great -- but no docs or support.

Support as in commercial support, a bug tracker or what?

Re: D3-dag – Layout algorithms for visualizing directed acylic graphs

#35

Post by abs221 »

leppr wrote: post #25
abs221 wrote: post #18

All these graph layout algorithms should ideally be run on the backend. Most of these js libraries are missing the point in trying to run layout in Javascript on the frontend. If you have a huge graph, you can't view all of it at once anyways and you're viewing a subset of it any 1 moment. So the ideal library should be running the layout on the backend and the frontend should be plain dummy, simply showing each grap…

You're missing the point by thinking only of your specific use case of huge graphs. Client side interactivity without network delay is a valid use case for these libs. Client side encrypted data also.

Most humans can't make much sense of anything more than 50-100 node graph at a time. At a graph size of containing 50-100 nodes or lesser which is a rather small graph, huge variety of graph algorithms are not very helpful. These libraries are good to experiment with each layout algorithm but ultimately a graph analysis most of the time involves exploration and querying, like a repl and making sense of that. Most frontend js libraries will not be helpful in doing that.

It's a surprise that there is no robust backend library that does graph layout.

Re: D3-dag – Layout algorithms for visualizing directed acylic graphs

#36

Post by dragonshed »

abs221 wrote: post #35
leppr wrote: post #25

Earlier quoted context omitted.

You're missing the point by thinking only of your specific use case of huge graphs. Client side interactivity without network delay is a valid use case for these libs. Client side encrypted data also.

Most humans can't make much sense of anything more than 50-100 node graph at a time. At a graph size of containing 50-100 nodes or lesser which is a rather small graph, huge variety of graph algorithms are not very helpful. These libraries are good to experiment with each layout algorithm but ultimately a graph analysis most of the time involves exploration and querying, like a repl and making sense of that. Most fro…

You can run d3 on the backend with node. It shouldn't be too difficult using it with a layout to constrain the potential visualization to a more comprehensible data set.

There's even a d3-node package available to generate a static SVG or png.

[edit]

Additionally, grouping or binning the data may be something to consider when dealing with a visualization with 100+ nodes. Never tried that with DAG datasets, not sure how that would work, but it's interesting to think about.

Re: D3-dag – Layout algorithms for visualizing directed acylic graphs

#37

Post by dman »

MasterScrat wrote: post #30

I'm using vis.js to visualize DAG of large train networks, I love how the output looks: https://i.imgur.com/BAwbyB1.png I really wish the computation would be offloaded to web workers though. Right now it completely freezes the browser when updating very large graphs (above around 1.5k edges and .5k nodes in my experience). Eg of a much larger graph after 15min trying to stabilize: https://i.imgur.com/f06n9Ic.jpg

Would you be willing to pay for something that ran much faster?

Re: D3-dag – Layout algorithms for visualizing directed acylic graphs

#38

Post by eslaught »

Of all the tools mentioned in this thread: how do they scale?

We have DAGs that cause graphviz to choke (tens of minutes running time, if it ever finishes). So far I'm not aware of anything that scales better than graphviz with similar results to the dot layout engine.

Re: D3-dag – Layout algorithms for visualizing directed acylic graphs

#39

Post by porterde »

eslaught wrote: post #38

Of all the tools mentioned in this thread: how do they scale? We have DAGs that cause graphviz to choke (tens of minutes running time, if it ever finishes). So far I'm not aware of anything that scales better than graphviz with similar results to the dot layout engine.

Even if you can calculate the layout for a very large DAG in a reasonable time, the zooming and scrolling required as a user to make sense of it and follow interesting paths makes it unwieldy in my experience. One approach to use with very large DAGs is to interactively expand / collapse nodes - for a simple tree example imagine something like a treeview control for browsing a file system, expanding folders of interest to drill down rather than viewing all expanded. For non-tree DAGs you need the layout algorithm and you might need to automatically collapse unrelated sections as you expand nodes along a path to keep the time reasonable.

This approach can be combined with lazy loading data as you expand a node as another performance enhancement.

With some effort you can add this interactivity to vis.js or d3. I have previously used a commercial product called KeyLines [1] which has this feature, uses WebGL to run the layout in gpu.

[1] https://cambridge-intelligence.com/keylines/layouts/

Re: D3-dag – Layout algorithms for visualizing directed acylic graphs

#40

Post by ygra »

evmar wrote: post #3

I recently wanted to render some graphs and found there are a confusing variety of options. In particular https://github.com/dagrejs/dagre/wiki seems to be layout focused and then plugs into a bunch of other systems including d3. It would be nice if one of these tools was able to describe itself in contrast to the others.

Many tools that produce similarly-looking layouts use pretty much the same algorithms, just with different tweaks. I.e. hierarchical layout is usually based on Sugiyama's work; force-directed is also a staple that's very easy to implement and thus is widely implemented. There often is no simple list why one implementation is better/different than another. There are common improvements you can make or features you can add, though:

- In a hierarchical layout, supporting custom layering and sequencing to ensure that certain nodes will appear in a given layer, or that within a layer the order of nodes is fixed. This is fairly easy to add, since layering and sequencing have to be done anyway.

- Support for grouping, where nodes can be enclosed in a box, which requires the layout to keep them close to each other and also ensure that no other nodes protrude in that box (and preferably prevent edges from passing through as well).

- Customizability of edge routes, where you could, for example, say that edges have to leave a node on the bottom and enter from the top, instead of having that property implicit due to the layout direction and choosing to pur ports in the center of nodes.

- Some applications don't concern themselves with interactivity and thus don't care about algorithms that, for example, would ensure that after incrementally changing the graph, the resulting image would still look similar to the old one (when adding a node to a tree you don't want the order of subtrees higher up to change completely just because of that change).

- Any features you add may interact with each other and further complicate the implementation to ensure that each one still works (and results in acceptable runtime).

Generally, due to the breadth of features that can be supported/implemented in a given implementation, you sometimes have to study the documentation closely. If all you care about is getting a nice result with default settings, then that's often easy to test, though. But the nature of graph drawing is sadly that the most visible effect of an algorithm is what you see.

Post reply on HN