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?

  • (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 3 '15 at 22:26
  • @rwong Yepp, I checked a lot of available tools. Nothing helped. :S – inf3rno May 3 '15 at 22:28
  • 2
    A constraint based layout may allow you to avoid updating too many other nodes - see marvl.infotech.monash.edu/webcola/examples/downwardedges.html and 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 5 '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 6 '15 at 6: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 6 '15 at 6:41
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.