RE: [gef-dev] CDAG layout algorithms

["Michael Forster" <forster@xxxxxxxxxxxxxxxxx>]

Hi,

> I've skimmed over your paper.  The sub-optimal reodering 
> shown in Figure 6 could be corrected by a final pass through 
> the graph which exchanges "adjacent pairs" of nodes if it 
> improves the quality of the layout. 

Of course. This is just a minimal example where Sander's algorithm
fails. So it is not surprising that a simple heuristic can solve this
particular problem. But remember: It still stays a heuristic, and it
does no solve the fundamental problem. So you will definitely get
unneccessary crossings.

> My concern with preserving the containment hierarchy during 
> the crossing reduction is that this prevents a node from 
> gradually passing through a subgraph to which it doesn't 
> belong.  

This does not happen, and this is proven (Well, the proof is sketched,
at least :-) in the paper.

> It seems like using your algorithm, the node would 
> have to jump across the whole subgraph (compound node) at 
> once, or not at all. 

This is correct, and the nodes make these big jumps. If two subgraphss
which are high in the subgraph hierarchy are exchanged while applying
the crossing reduction to an enclosing subgraph or the root of the
subgraph hierarchy, the dependent (base) nodes "jump" over the whole
other subgraph.

I admit that my algorithm may be harder to understand and implement than
Sander's. But it is better than Sander's by proof. It is even optimal if
only considered according to a single rank (=layer=level). This means,
there will be only unnecessary crossings that come from the underlying
2-level crossing reduction (These occur in both algorithms - the problem
is NP-hard, so you cannot expect global optimality), but _no_ crossings
that come from the application to the clustered graph. Sander's
application generates such crossings. So I am highly convinced that my
algorithm performs better than Sander's. Of course, I am biased, and I
do not have numbers to substantiate my opinion, but the theoretical
results in my paper promise good practical results. By the way: I talked
to Sander last year after my talk at the conference, and he admitted
that my method is more promising than his quick-and-dirty solution.

Note that I do not want to persuade you to use my algorithm, especially,
if you are under deadline pressure and fully understand Sander's
algorithm but not mine. On the contrary: I will be happy to have an
implementation of Sander's algorithm to compare to mine in my thesis
:-).

By the way: Would it be possible, to have a look at your code? It will
be published under the CPL anyway, right?
 
> Here is a case 
> where reversing the edge from a cycle is better than removing it. 
> 
> Given Subgraph A with members a1, a2, a3 
> Given Subgraph B with members b1, b2, b3 
> And a node X. 
> 
> Ignoring all edges, here are the final rank orderings: 
> a1       b1 
> a2       b2 
> b3  X  a3 
> 
> The two subgraphs are intertwined, with a random node falling 
> between them. 
> The cycle A -> B -> X -> A exists.  If you break X -> A, you 
> then end up with last row of: 
>         a3  b3  X 
> But, if you reverse it to be A->X, you have partial ordering 
> A->X, and A->B, which allows for: 
>         a3 X b3 

No, it does not, because you forgot the edge B -> X, which still exists.

In general: If you have a cycle

    X1 -> X2 -> ... -> Xn -> X1

and you break it up at Xn -> X1, it does not matter whether the edge

                       X1 -> Xn

is inserted, because the partial ordering is transitive, and so Xn has
to be right of X1 anyway. This means, the quality depends only on the
concrete implementation of the topological ordering, but not on the edge
X1 -> Xn.


Regards, Mike