Group nodes within a bounding container #25
Comments
|
To group the nodes you probably want clustering support (dagrejs/dagre#13). It turns out to be a fair amount of work to add this support - the ticket references some of the papers that describe how to add it. Unfortunately, I haven't had a lot of dedicated time to work on it. |
|
Haha yeah I figured it might require a little bit of effort to get it to work! No worries, is there some way of faking it in the meantime, maybe by adding the nodes to the graph in order and then manually drawing a rect around them? It wouldn't do "collision detection" or anything fancy like that, but it would serve as a visual aid for now!? |
|
I just re-added forster's constrained ordering algorithm, which gets your part of the way to your goal. With this ordering algorithm all nodes in a subgraph are grouped contiguously in each layer. Furthermore, the ordering of subgraphs are maintained across layers, so that you can't have subgraph A before subgraph B in layer 1 and then subgraph B before subgraph A in layer 2. This doesn't get you all of the way though. In addition to the above you want all of the nodes to be grouped into a rectangular region across layers. This will likely not be available until I finish support for clusters. |
|
Any update here? I little background. I'm currently updating lipstick (https://github.com/Netflix/Lipstick) to work with dagre instead of relying on graphviz. Things are going great so far: (https://github.com/thedatachef/Lipstick/blob/dagre/lipstick-server/web-app/tossboss-graph-view/js/tossboss-graph-renderer.js) with one real issue. Grouping nodes for a map-reduce job inside a rectangle. If you look (https://github.com/thedatachef/Lipstick/blob/dagre/lipstick-server/web-app/tossboss-graph-view/js/tossboss-graph-renderer.js#L102-L155) you'll see that I add the rectangles manually after the graph layout using d3. Unfortunately, this only works some of the time. Occasionally dagre puts nodes from one subgraph in the same region as another making my rectangles nest. Now, I'm using a CDigraph for the graph and Digraphs for the subgraphs. Is there something else I should be doing? Here's some screen shots: With graphviz (what I want, sans graphviz itself and the ugly paths...): And with dagre (what I've got so far): Thanks! |
|
Here's a block that illustrates things simpler. http://bl.ocks.org/thedatachef/raw/9818190/ Just looking for a workaround or something. If necessary I can spend some time on the renderer code if I knew where to start. Thanks! |
|
You're doing everything right, it's just that clustering support isn't done yet. I have a set of patches on a local branch that gets us closer to clustering support, but I haven't had time to work on them. The main issue seems to be that the position phase algorithm, which has been generally been problematic, doesn't seem to play well with clustering. I'll take a look through the patches I have and if they aren't too embarrassing (they're proof-of-concept code) I'll clean them up and post them to a branch on github this weekend. |
|
That's good to hear. I've hacked together a workaround that (at least for this gnarly graph: http://bl.ocks.org/thedatachef/raw/9841692/) appears to work. The idea is that, when laying out nodes, group them by cluster. Then, in the post processing, select the clusters, get their bboxes, and run the layout again using just the clusters as nodes. Of course the details are the beast here: https://gist.github.com/thedatachef/9841692 I'm happy to work on the more general solution when you post your branch. Thanks! |
|
Ok, one last comment for now. Theres a problem in my hack related to the minLen variable that the dagre layout uses. That is, if I treat the clusters/groups as nodes and run the layout it sets the number of ranks for an edge to 1, which means the length of the intercluster edges is way too long. If I could set the minLen to a fractional value I think I could go home happy. Thoughts? |
|
minLen itself has to be a whole number because it is used to set up ranks. You could change the rankSep for the inter-cluster edges, which would reduce their length. Take a look at https://github.com/cpettitt/dagre#configuring-the-layout for details. |
|
I've pushed most of what I have for the clustering support to the "cluster" branch for dagre. It doesn't work as it is and there are at least three places that probably need attention:
|
|
Actually, 1 above may have been me trying to hack around the positioning algorithm (2 above). I would suspect the position algorithm first. |
|
Interesting about minLen. In my hacky example rankSep seems to work fairly well only if I set it to a negative number. However, if I try that with the lipstick graph there's cluster overlap again. Ah well. I'll take a look at the cluster branch. Not sure how helpful I'll actually be since I'll have to read up on the algorithms you're using (and graph layout in general...) so I'm not totally lost. However, this is the last bit preventing me from totally replacing graphviz in lipstick so it's worth the effort on my part. I'll post any real progress here. |
|
Latest code on the clusters branch addresses the bug with addBorderSegment and fixes some issues in ordering for clusters. Two obvious issues remain:
The code on the clusters branch is prototype-grade and needs some doc + tests before I push it to master. This will probably happen after 1 is addressed. |
|
It looks like the output of graphviz most closely corresponds with strategy 2 in Sander's paper. At a very high level, this seems to be the idea: As usual, add dummy nodes for each rank r from rank(u) + 1 to rank(v) - 1. At each step we try to find the next closest subgraph s such that rank_min(s) <= r <= rank_max(s). We effectively do this search by moving up the nesting graph until we hit the lowest common ancestor of u and v and then move back down towards v. It is possible that multiple subgraphs along this path have overlapping ranks, which is why we need to keep track of where we are on the path from u to v. I'll take a stab at this sometime next week as time permits. Likely this will be next Saturday. |
|
Take a look at the "cluster" branch. For the test cases I've thrown at it, it no longer shows any overlap. A few thoughts:
On the positive side, now that we have something that works through all of the phases it is possible to make incremental improvements. |
|
@cpettitt Appears to be working great for 'normal' graphs but still overlap for neurotic cases. See: http://bl.ocks.org/thedatachef/raw/9915158/ (sane graph) I'll try this with lipstick today on some of the more eccentric graphs. I could probably make some of these examples tests for dagre once I have some time to grok your tests. Thanks! |
|
@TheDataChef that would be great. I'd probably add those graphs in test/smoke. See https://github.com/cpettitt/dagre/blob/master/test/smoke/smoke-8.dot as an example. The only special consideration is that the nodes have to have some size associated with them since dagre doesn't do that. To catch the overlapping issue, we could add a test to https://github.com/cpettitt/dagre/blob/master/test/smoke-test.js to check that no clusters bounding box overlaps another that is not part of a parent-child relationship. I don't recall if I have the code for setting up the bounding boxes in dagre or just in a local branch for dagre-d3 on my laptop. If its not in dagre, it needs to be added. |
|
Ok, tried with Lipstick using the cluster branch. Things are a bit...off but there's no overlap. Seems like too many dummy nodes are added there? Or maybe the endpoints for the intercluster edges should be at the top and bottom of their nodes but they're on the sides? I'll add that as a graph to the smoke tests and make a pr so you can take a look at it. |
|
@TheDataChef I tried out the neurotic graph, but I'm not getting the same result. Here's what I got: http://bl.ocks.org/cpettitt/9925588/741d7687e1acb47d3779c3c2ab388dc024abbba1. BTW, here's how I've been testing dagre with dagre-d3:
This gives you a new dagre-d3 with the dagre that has cluster support. I think that in at least some cases it makes sense to put the first (and last?) dummy node in the cluster. That should yield better results for your graph and others. |
|
Check this out (your smoke test graph): http://bl.ocks.org/cpettitt/raw/9927284/6cd3388cfa70c6108ccb4f365a5820cbfbe3deab/. You can zoom out and pan to see the whole picture. This is from the cluster3 branch. I suspect this is going to cause problems with nested subgraphs though. It also has problems if edges cross nodes at the same level (nothing to do with the most recent change though). I'm probably going to take a few days to think about how to address some of these problems(and maybe start some cleanup / test / doc work. Happy to answer questions in the meantime. |
|
Is there a local branch of dagre-d3 you're using that draws the clusters? I don't see from your link how the rectangles get there. |
|
Yes, sorry, I'll push it to dagre-d3 tonight. |
|
Sweet! I'll just keep using what I have for lipstick (wrapping clusters in a group during drawing and then postrendering the rectangles) since I have some additional code that goes into the label drawing already. I haven't tried every example graph I have yet, but the cluster3 branch has taken care of the ones I've looked at. Thanks! |
|
Trying this with a large lipstick graph and getting issues. The same graph renders fine with graphviz yet I get (using cluster3 branch of dagre, cluster branch of dagre-d3): Uncaught Error: Graph already has node 'scope-4120' dagre-d3.js:3866 Here's the graph (https://gist.github.com/thedatachef/10426606). I've stripped all the metadata I could. Sorry for the size, if I knew what the issue was I'd replicate with a smaller one. |
|
I'm able to repro and was able to compact this down quite a bit: The error is for a different node (scope-3971), but the error is the same. I don't have a lot of time to look at this tonight, but should be able to give it a thorough investigation this weekend. |
|
Ok, I got that graph to "render" by adding a check for self loops (which may just be treating the symptom): https://github.com/thedatachef/dagre/commit/7e728f98a5a06dfa73372cad6db42780ebb155ce But dagre-d3 isn't drawing the cluster for scope-3971 properly. Just contains node 350. Makes me think it's a larger problem. That's probably all I can contribute for now without a deep dive into the code. |
|
Unfortunately I spent most of the weekend sick, but I was able to look at the problem with the large graph. The reported issue is fixed in the cluster4 branch, but be warned - rendering that graph takes about a minute right now and there are some issues with cluster overlap. I'll work on both fronts over the next week. |
|
I now have dagre master rendering "neurotic" graph successfully. It is also able to do this in about 15 seconds, versus the > 50 seconds it takes with the current released version of dagre. There are still some optimization opportunities to be had as well. Dagre-d3 needs to be updated to pick up the new versions of dagre and graphlib - they were massively rewritten for better performance and test coverage. |
|
Thanks! I've pulled down dagre (and graphlib) and tried to run make, but having issues with a clean build. First, with master branch of graphlib: "TypeError: 'undefined' is not an object (evaluating 'require('graphlib').converter.json')" If I just use npm's version of graphlib the tests don't pass: TypeError: 'undefined' is not an object (evaluating 'inputGraph.graph') If it's non-trivial I can wait, otherwise any guidance on updating dagre-d3 to use the latest changes? |
|
Yeah, I need to update dagre-d3 to the new API - I'm going to try to knock that out in the next day or two. In the meantime, you can use the test console in dagre, if you'd like. You need to do a make build first. It requires dot as an input, but I converted your graph to dot. |
|
Ok, I finally got some time to try it out. For the most part everything I've looked at lays out great, even with multiple levels of nesting! However, I've got one that doesn't layout right: Tested with latest (master branch) version of dagre. |
|
Confirmed repro'd and the problem is coming out of the down-right alignment. Here's a variant with some simplification (17 should be in the same cluster as 14): |
|
@TheDataChef I fixed the problem with that graph in v0.6.4. Getting more and more suspicious I'm going to need to use a different positioning algorithm (maybe graphviz's)... Let me know if you find any more broken graphs. |
|
Alright, of the 100 or so widely varied graphs I looked at there's only one that's still got cluster overlap, but I can't reproduce it using the dagre console: However, when I render with html in the node labels there's overlap:
In the dot graph it's subgraphs A, B, and L. Possibly an issue with the foreignobject tag? |
|
The above layout is not right in the down-left alignment. Here's a slightly simplified and tweaked version still showing a problem: |
|
Even simpler, more tweaked: |
This version includes fixes to horizontal position. This fixes the last failing graph in #25.
Apologies if this is already possible and I've just missed it, but I'm using dagre-d3 to draw our network diagrams (servers and load-balancers) within our provisioning tool so that we can spin up a new environment based on the resources in the diagram.
Dagre-d3 is awesome so far, I've been able to get all the functionality I needed without too much effort, the only thing that's missing is that I'd like to group my servers by subnet (or AWS availability zone, I haven't decided yet). I guess this is just a special case of bounding boxes around a group of nodes where the boxes don't overlap.
If this isn't already a feature that I've missed, is it something that I could do using d3 directly? Any pointers in the right direction would be great!
Thanks
The text was updated successfully, but these errors were encountered: