stable layout for disconnected graph

[gordonwoodhull]

Hi @tgdwyer, back at this after having to do some other stuff for a while.

Back in Chicago we discussed a better way to deal with disconnected graphs. If you recall, I'm seeing a lot of extraneous movement because the packing algorithm runs on every iteration, presumably fitting everything in the most compact arrangement.

Basically I would like to start with the packed layout but on future iterations keep the components reasonably close to where they were, only rearranging them when two components become connected.

It didn't sound that difficult and I'd like to contribute - could you remind me your ideas on this?

One sort of hacky approach I could imagine is to treat the existing graph as if it were one component and only do packing on any new components on each round. But I think you mentioned something more intelligent.

[tgdwyer]

Hi @gordonwoodhull !

My suggestion is: after performing an initial layout and applying the disconnected graph separation (as per the current start method), we can place the contents of each component inside a group and thereafter rely on avoid overlaps to keep the rectangular group bounds neatly separated.

Of course all this is complicated somewhat if the graph already has groups. We need a better notion of "disconnected" in this case.

[gordonwoodhull]

Makes sense, will try!

[gordonwoodhull]

I attempted simply putting the components in their own groups from the start, but it seemed to overconstrain (compactify?) each layout, and the components still would fly around over each other. Must be doing something wrong.

This is what I tried (very stupid):

    if(opts.groupConnected) {
        var components = cola.separateGraphs(wnodes, wedges);
        groups = components.map(function(g) {
            return {leaves: g.array.map(function(n) { return n.index; })};
        });
    }

https://github.com/dc-js/dc.graph.js/blob/8bdf26afc7731a750868e0a447427725235e6c6e/src/cola-worker.js#L69-L74

[wizzard0]

my 5 cents: splitting a graph in two and restarting layout also results in random jumping around; this could definitely use some improvement because interactive graph editing becomes very confusing

[ancashoria]

Did you guys make any progress on this? I also use Cola on an interactive graph and the jumping around is quite confusing. Any suggestions on how to fix this?

Thanks for your hard work

[gordonwoodhull]

Yes! After struggling with this for quite a while I figured out I could put each component in its own group and then make sure at least one node from each group is fixed.

There is a bug where cola really expects everything to be in groups #166 - I'll submit a PR for that. And handleDisconnected is unstable - components jump around as described above.

I'm not at the computer right now but I'll update with more details later - I think there was something built-in that I used instead of groupConnected. I'm also not sure if fixing nodes was really necessary for stability but it was something my clients wanted.

I can also share a cool demo or two - that might take a little longer but I can update this weekend with the details of what I did.

[ancashoria]

@gordonwoodhull your post gives me hope because this is quite an issue I am unsure how to handle it. If it helps, I'm using layout.avoidOverlaps(false) because it's quite resource intensive. Anything you can provide is greatly appreciated.

Thanks

[gordonwoodhull]

So here's what I found.

handleDisconnected, which is true by default, handles the problem of how to layout multiple components by putting the components into groups and then packing the rectangles.

The rectangle packing is unstable, and that's what causes components to fly around.

However, cola's core algorithm only works on connected graphs, so the alternative is to put each component in a group. So what I finally did is set .handleDisconnected(false) and instead use groupConnected as defined above.

I just confirmed this produces a stable layout when no nodes are fixed.

In my application, the user is clicking on the canvas or dragging nodes onto it, so the initial positions are fixed. Whenever a change to the graph happens, I calculate the components, and if any components have been combined, I only leave nodes fixed in the largest former component.

https://github.com/dc-js/dc.graph.js/blob/6a2bd547e43fe472c65e644973884e0f3b1c03c2/src/fix_nodes.js#L187

This produces an ultra-stable, user-driven layout that still obeys any constraints.

@tgdwyer, I'd be happy to contribute groupConnected as a resolution for this issue. I agree that in some cases it might be better to run handleDisconnected once, and that's something we could add as an option in the future. In my current application, we're building from scratch so it doesn't matter.

[gordonwoodhull]

FWIW, I promised a demo of using constraints, groupConnected, and fixed node positions for an ultra-stable layout for visual programming.

That demo is here: https://dc-js.github.io/dc.graph.js/drag-drop-composition.html

(and, sorry this took N months!)

This is only one specific use case - I wouldn't say that I have solved stable layouts, but it works very well in this case where you want things pretty much where you dropped them, except with edges constrained left-to-right or top-to-bottom.