6

I need a 2d or 3d graph visualization algorithm by which adding/removing a node or a relationship does not have a butterfly effect on the positions of other nodes. (We are talking about a directed cyclic graph with weighted nodes and relationships if that matters.)

For example by a regular force layout adding a new node affects the position of every other node. Do you have any idea which algorithm could help?

inf3rno
  • 1,209
  • 10
  • 26
  • (Personal opinion) Unfortunately seems to be a difficult problem, judging by the fact that currently most people are still using GraphViz (which does suffer from that butterfly effect) and there aren't many replacements available. – rwong May 03 '15 at 22:26
  • @rwong Yepp, I checked a lot of available tools. Nothing helped. :S – inf3rno May 03 '15 at 22:28
  • 2
    A constraint based layout may allow you to avoid updating too many other nodes - see http://marvl.infotech.monash.edu/webcola/examples/downwardedges.html and http://marvl.infotech.monash.edu/webcola/. Failing that, I'd try just doing some sort of "snap to grid" on the results of a force-directed-layout algorithm. – Tom May 05 '15 at 23:11
  • @Tom Thanks for writing! In the example you linked we can see only trees (hierarchy) and not acyclic graphs (no hierarchy). A "snap to grid" does not work in cases when nodes move more than the cell size. If you increase the cell size, then the distances will be too large between nodes. – inf3rno May 06 '15 at 06:40
  • I was rather thinking on using relative coordinates and multi level force layout, which uses only certain sized (relationship count) nodes by each level, but many things are still not clear. Especially how to describe relative coordinates. But I am working on it. – inf3rno May 06 '15 at 06:41
  • I think constraint based layout will work just as well for graphs. What I was hoping is that by adding additional layout constraints you could mitigate the knock on effects of the force directed layout. e.g. constraining spacing/alignment means a new node would only push close neighbours and not cause a "bulge" in the entire graph. – Tom May 07 '15 at 12:25
  • @Tom Please add a detailed answer about this constraint based layout. It might work, at least I am working on something similar. I'll add weights to the nodes, so I can break it down from bigger nodes to smaller ones. Each level could use a force layout or something like that. It works in theory, I'll implement it and post it, but it will take at least a weak, because I never used webgl before. – inf3rno May 07 '15 at 16:29

1 Answers1

1

A problem that may be related is one where I have program to show the changing process trees running on a computer, as a real-time animation.

In that context each level of the tree generally goes from narrow to wide. So to keep regularity, you could keep larger subdivisions around for a little while before reducing them.

For example. I have at the top level 1 item. Next level 3 items, next level 10 items. Suppose an item at level 2 and 3 children of that disappear. You could keep the positions they are at still around but now just as invisible items and lines so that nothing else changes. So visually it would be as one expects, they just disappear. Then slowly over time that gap could get closed up. But in my case, often a new set of processes would take its place. I'd have that then in the space occupied by the gap.

The paper describing my situation and solution is http://motif-pstree.sourceforge.net/xps-full.ps

The main idea is laying out a grid for each depth to put stuff in and keeping that around for a little bit of time.

rocky
  • 200
  • 11