search

dagrejs / dagre

Directed graph layout for JavaScript
MIT License
4.72k stars 606 forks source link

Support for re-flowing graphs with dynamically-sized nodes #134

Open brianchin opened 10 years ago

brianchin commented 10 years ago

If you had a graph that you wanted to interact with, then nodes could potentially be resized as you use it (e.g. by expanding or collapsing information in the node). From what I've read of the graph layout algorithm, it seems that the first two steps of the graph layout (ranking and ordering) could be kept between iterations of the algorithm. Would it be possible to add this to dagre with its current architecture?

cpettitt commented 10 years ago

Since all of the stages are deterministic out of the box I would expect that you could rerun the layout with the new dimensions and get the same layout taking into account the new dimensions. We could also take an attribute that skips the rank and order phases for efficiency reasons, but this would require that all nodes already have a rank and order assigned. It shouldn't be a lot of work to do this, provided we're getting the deterministic layout I'm expecting.

brianchin commented 10 years ago

The big question: Would this save us much in terms of rendering time? I don't know how expensive ranking and order are compared to the later phases. If it isn't at least 50%, there probably isn't too much of a reason there.

cpettitt commented 10 years ago

You can find out empirically by setting the debugLevel to at least 1. This will turn on timing instrumentation for each of the phases.

brianchin commented 10 years ago

On the first graph I'm working on, it appears that about 2/3rds of the time is spent on ranking and ordering (131ms of 193ms). There may be something there.