RE: [gef-dev] CDAG layout algorithms

[Randy Hudson <hudsonr@xxxxxxxxxx>]

Thanks for the LNCS link.  I am
able to reference all volumes.
That article on X-coordinate assignment
looks pretty promising, but we don't have time to implement it for our
first release.

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.  In this case, the "pair"
consists of one node, and one compound group of 3 nodes.  Some pairs
cannot be considered since swapping them would break the subgraph ordering.

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.  It
seems like using your algorithm, the node would have to jump across the
whole subgraph (compound node) at once, or not at all.

Topological sorting:
Yes, I just realized that.  This
is just a topological sorting, with heuristics for breaking ties.  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

-Randy