Cola layout improvements

[astefanutti]

It looks like the relative stress information, alpha, has been overridden by the lastStress variable which holds the absolute stress information in the Layout class.

[tgdwyer]

This change wasn't entirely unintentional.

At some point in the distant past (last year I guess), the Descent.ReduceStress function was used to advance the layout at each iteration. This actually computed the absolute 'stress' such that the relative stress calculation here made sense. However, now the "stress" being considered here is actually not absolute stress at all, but the square of the displacement vector length (see Descent.RungeKutta). Basing our assumption of convergence simply on monotonic decrease in length of displacement vector length is probably not sensible - so I switched to the absolute measure. In my testing I didn't feel that this was causing any problems... but perhaps it has affected you?

[astefanutti]

In some larger graphs, like this one http://astefanutti.github.io/cdeye/test.html?example=cnct.json, the absolute measure is obviously higher than in a smaller graph like this one http://astefanutti.github.io/cdeye/test.html?example=metrics.json. I used to rely on the relative measure, that is the alpha parameter, as a convenient way to have a generic threshold for the convergence. And rely on the absolute measure to do some contraction logic so that the end result is both well laid out and compact enough (see https://github.com/astefanutti/cdeye/blob/ac8cdf1b7f60cddbd7c7886c848c8d23d3b272f4/webapp/src/main/webapp/cdeye.js#L228).

So, from my understanding, this has somehow impacted the definition of the threshold parameter which cannot be considered generic anymore and whose default value 0.01 is not applicable for large graphs.

That being said, I can compute the relative measure and override the convergence logic within the tick event.

In any case, that may required to revisit the attributes passed in the tick event.

[tgdwyer]

Wow! It's really cool the way you dynamically adjust the edge lengths as the graph converges. Also, I'm impressed you are using the gridrouter... that code is a little experimental still, also it was really designed for nodes arranged on smaller grids... like this one: http://marvl.infotech.monash.edu/webcola/examples/statemachinepowergraph.html. Anyway, if it's working for you now that's great - but I will be adding some proper gridlayout capabilities to cola soon. I'll let you know as soon as I have something useful.

Anyway, regarding convergence you make a good point regarding larger graphs. Since your use-case is so specific, it might be better for now if you take the absolute value in alpha and do your own scaling in the tick function (as you suggest). I'll make a contract with you right now (if you like) that we'll keep event.alpha (or some rename of it) as the absolute displacement which you can use for your own calculations and maybe later I'll add an additional relative displacement property.

Does that work?

[astefanutti]

Thanks. That works for me.

Using the grid router with dynamically laid out graphs leads to some unpleasant routing as the nodes aren't precisely aligned with the computed grid, as depicted in the image below.

Besides, for larger graphs, I'm still trying to find the right setup as I find the visual result less understandable compared to shortest-path edge routing. I presume this is caused both by the larger grid size and the nodes being misaligned with it. I've tried to increase the generated group constraint minimum separation without that much improvement.

I'm eager to give these upcoming grid layout capabilities. Hopefully, that'll be applicable to my use cases.

[astefanutti]

I've just upgraded to the latest revision and experimented with the new features and examples. Here is my feedback:

• I've used the hybrid layout technique and I confirm this is an effective way to accelerate the layout. However, I've faced the following issues:
  • Multiple passes do not work well with predefined groups for the power graph compression over the same nodes because the construction of the root group in https://github.com/astefanutti/cdeye/blob/45daa4fcf1d03f1133893da4e3da5e170a7960c8/webapp/src/main/webapp/lib/cola.js#L3096 is not idempotent so that I had to delete these properties manually: https://github.com/astefanutti/cdeye/blob/45daa4fcf1d03f1133893da4e3da5e170a7960c8/webapp/src/main/webapp/cdeye.js#L186
  • Similarly, I had to add a guard to avoid dereferencing leaves and groups in https://github.com/astefanutti/cdeye/blob/45daa4fcf1d03f1133893da4e3da5e170a7960c8/webapp/src/main/webapp/lib/cola.js#L3086 and https://github.com/astefanutti/cdeye/blob/45daa4fcf1d03f1133893da4e3da5e170a7960c8/webapp/src/main/webapp/lib/cola.js#L3092
  • When user constraints are defined, the corresponding variables state is overridden from one pass to another so I had to add a check to avoid losing that state which leads to descent issues when dragging the nodes: https://github.com/astefanutti/cdeye/blob/45daa4fcf1d03f1133893da4e3da5e170a7960c8/webapp/src/main/webapp/lib/cola.js#L1084
• I've used the grid snapping feature and I confirm that is a killer combination with the metroline routing feature. However, I've noted the following points:
  • While the grid layout works perfectly for square nodes as the grid size is adjusted from the first node width, it should support rectangle nodes as the snapping feature leads to unpleasant layout in that situation
  • Smooth transition between the hybrid layout and the gridified layout isn't obvious to achieve (though I haven't really put that much effort into it yet): https://github.com/astefanutti/cdeye,/blob/45daa4fcf1d03f1133893da4e3da5e170a7960c8/webapp/src/main/webapp/cdeye.js#L266
  • That'd be useful to have the snapping strength configurable as well as having a configurable gap between the columns and rows of the grid.

Besides, I still have to address the following points:

• Achieve Layout compactness for constrained graphs without compromising understandability (mainly because of edge crossing) nor impacting convergence time,
• Define a generic threshold, that is independent from the graph size, for the convergence.

Here is a screenshot of what I've been able to achieve so far (with manual manipulation to work-around the grid snapping square node limitation and improve the graph compactness):

PS: I've renamed the title of this issue to reflect the content of that discussion.

[tgdwyer]

Thanks for the feedback, sorry for the slow reply. I'll continue working (slowly) on the gridlayout. I have some ideas about how to make it work with non-square nodes - but it's not entirely trivial.

[astefanutti]

Thanks for the heads up. I wish I could contribute more to that part though I hit the limits of my CS classes memories. I can't wait to give the new layout features a try!

[tgdwyer]

Please see our forthcoming paper on grid layout. The most basic version of which is now available in webcola.
Better handling of non-square nodes is still a to-do item, but I'm closing this issue as part of a cleanup.