DAG Graph Layout - Sugiyama Algorithm
Hi everyone,
I was working with large and complex DAG's applying Sugiyama algorithm to see it in a hierarchy. I have a question about the second phase of the algorithm execution where you need to reverse the two vertices with equal barycenter values, and apply phase 1 so that the algorithm can further minimize edge crossings. Now my typical graphs contain about 500 vertices arranged in about 10 vertical levels, and lots of edges. The book says that apply phase 1 when you change only one pair, but in my case there are lots of nodes with equal barycenters. If I do it one by one it will take forever to run the algorithm. So I swap all the adjacent vertices with equal barycenters and then run phase 1. Is that the right way?
Example given in the book and other web site refers to a DAG which happens to have only two vertices with equal barycenter which they swap and run Phase 1. To see the example refer to http://plg.uwaterloo.ca/~itbowman/CS746G/Notes/Sugiyama1981_MVU/
That is not the case with the complex graphs.
I read at some other site that a better alternative is to start with a random arrangement of nodes and apply phase 1 hoping that one of those random arrangement will find the best possible layout. This approach is very fast but may not be optimal.
Also I could not find the IBM GFC as mentioned above. It says that the package is expired :(
Any thoughts?
Hi,
> I read at some other site that a better alternative is
> to start with a random arrangement of nodes and apply
> phase 1 hoping that one of those random arrangement
> will find the best possible layout. This approach is
> very fast but may not be optimal.
I totally agree with this statement. As for "deterministic" approaches, you will always find situations (vertex constellations) that cannot be solved in reasonable run-time. In contrast, using randomization you cannot find examples that cannot be solved optimally, since all you need is a little bit of luck and you will solve the problem optimally just by guessing ;-)
No, really: I did parts of the implemention of the sequencing phase for the Sugiyama algorithm for the yFiles graph visualization library and we did a lot of research. There is a lot that can be done (and has been done in yFiles) to tweak the original algorithm and using randomization is one such thing. You will be suprised how quick you can get better results using (pseudo-) randomization just a couple of times.
If you still want to use the original algorithm, I would say you should definitely swap (or at least permutate somehow) the equal barycenter vertices all together and then restart the first phase. Otherwise to much computation time will be spent in actually doing nothing (leave most of the vertices in their positions).
If you want to have a look, you can see our implementation in action in the free java graph editor yEd.
Greetings, Sebastian
