[gef-dev] CDAG layout algorithms

["Michael Forster" <forster@xxxxxxxxxxxxxxxxx>]

Hi,

This is the continuation of a discussion started on the GEF newsgroup.

Randy Hudson wrote:
> GREAT!  Perhaps you'd like to shed some light on the subject.  

I will do, what I can. I think, I have a reasonable overview over the
field - well, I should have :-)

Since my PhD-thesis demands an implementation of a CDAG layout
algorithm, it may also be possible to contribute some code, but I cannot
promise anything, mainly because I probably have a different time frame,
and I cannot work full time on my implementation.

> Are you subscribed to the developement mailing list?  

I subscribed right now. This article is posted to the mailing list and
the newsgroup. I propose to continue on the mailing list.

> We are using the terminology from Sander 1996, and most of his
algorithm.

I expected that, and it is probably the right decision. The most
prominent alternative algorithm for directed layout of clustered graphs
is an algorithm of Sugiyama / Misue, 1991. This paper is not easy to
understand, and I prefer Sander's results from an aesthetical point of
view, anyway.

Which publication of Sander are you using? His PhD-thesis is probably
the best, but because it is in german, it may be unreadable for you. But
IIRC, the technical report is also pretty detailed. 

> We convert the CDAG to a simple DAG.  So, for each subgraph, we
introduce a
> head and tail node.  However, we don't connect every node contained in
the
> subgraph to both the head and tail.  Instead, we connect only a subset
of
> the nodes to the head and or tail nodes.

Probably only those nodes that have no incoming edges from other nodes
contained in the same subgraph? This is equivalent anyway. Does this
give you a performance boost? Since the inserted edges are needed for
the ranking step only, calculating the right edges might be more
expensive than just inserting all of them. In my prototype I do not
insert edges at all, but I just use the inclusion relationship as
"implicit edges", when doing the ranking. I am not sure yet, however, if
this is better. It also depends on the data structure used for storing
the graph.

> Also, we don't use the rank spacing suggested.  In our use cases, the
> subgraphs have pretty large labels on them, so the heads and tails are
just
> as tall as other nodes in the graph.

Sounds reasonable. I suggest, that you use some kind of grid / threshold
technique for assigning the ranks, so that you don't end up with too
many ranks. The number of ranks is probably the most important factor
for the running time. Ranks with too little distance also make the
layout look cluttered.

> So, once you layout the simple DAG, you may have violated the subgraph
> requirements.  This means we need to make another pass through the
ranks to
> respect the subgraphs.  This seems to be the hardest step in the
process,
> and it may introduce crosses which could be removed by another
MinCross pass
> which avoids mixing up subgraph boundaries.

For this, you might be interested in some of my work. See

@InProceedings{forster02,
  author =	 "Forster, Michael",
  title	=	 "Applying  Crossing Reduction Strategies to Layered
                  Compound Graphs",
  pages =        "276--284",
  booktitle =    "Proc. Graph Drawing, {GD} 2002",
  editor =       "Kobourov, Stephen G. and Goodrich, Michael T.",
  series =       "Lecture Notes in Computer Science",
  volume =       2528,
  publisher =    "Springer",
  year =         2002
}

If you do not have access to LNCS, I can send you a private copy. This
paper proposes an alternative to Sander's crossing reduction method.
Instead of first ignoring the subgraphs and correcting the subgraph
requirements afterwards, my algorithm respects the requirements right
from the start. This leads to an (in some sense) optimal application of
any two-layer crossing reduction method to CDAGS. It should generate
fewer crossings than Sander's algorithm and _might_ even be faster,
depending on the data structure. It probably is harder to implement,
however, and I do not have empirical results up to now. 

> Another area of difficulty for us is in assigning the attachment point
for
> edges between subgraphs.  You don't know how wide a subgraph is going
to be
> until you have solved the X-coordinate assigment.  In some cases, you
want
> edges to be attached at the center of the nodes/subgraphs.

I have not seen work on this yet. It is an interesting problem, however.
I will think about it. Maybe, I'll have an idea. I suspect, however,
that attaching edges to the center of a subgraph is not possible without
increasing the number of crossings. or doing some undesireable edge
routing.

BTW: Which X-coordinate assignment algorithm do you use? Maybe you are
interested in this:

Ulrik Brandes and Boris Köpf: Fast and Simple Horizontal Coordinate
Assignment. Proc. 9th Intl. Symp. Graph Drawing (GD '01), LNCS 2265, pp.
31-44. © Springer-Verlag, 2002. 


I hope, I could help a bit. If you have further questions or problems,
feel free to ask. I am interested in solving any problems related to
this area, as this always contributes to my thesis. And solving real
problems is always more satisfying than defining and solving theoretical
problems :-).

Regards, Mike