| RE: [gef-dev] CDAG layout algorithms |
Hi,
Randy Hudson wrote (partially on the newsgroup, partially on the mailing
list):
> We would like copies of any/all of the articles you mentioned.
> I haven't been able to find Sugiyama/Misue 91 on the internet,
> nor the other two papers you mentioned.
My paper:
http://www.michael-forster.de/publications/gd02.pdf
X-coordinate assignment by Brandes/Köpf:
http://algo.fmi.uni-passau.de/~brandes/publications/bk-fshca-01.ps.gz
Unfortunately, I do not have the Sugiyama/Misue paper in electronic
form, but you can read Chapter 8.4 of
http://www.inf.uni-konstanz.de/~cornelse/Papers/gigd.cluster.ps.gz
which is a summary of this algorithm.
It appears to me, that you are using only papers, that are available on
the net. That way you miss many more current improvements. The best
source for graph drawing papers are the proceedings of the yearly graph
drawing conference. All of these are published as LNCS volumes. I highly
recommend at least skipping the contents of the proceedings. I think
these are publically availabe:
http://www.springerlink.com/openurl.asp?genre=issue&issn=0302-9743&volum
e=1731
http://www.springerlink.com/openurl.asp?genre=issue&issn=0302-9743&volum
e=1984
http://www.springerlink.com/openurl.asp?genre=issue&issn=0302-9743&volum
e=2265
http://www.springerlink.com/openurl.asp?genre=issue&issn=0302-9743&volum
e=2528
I am not sure if these links work without an subscription, because the
access system is based on the IP address, and all our university
computers are subscribed.
> > > 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
>
> I think this is both a performance and quality boost. First, you want
> nodes within the same subgraph to have some small amount of cohesion.
> Otherwise, they will end up almost anywhere.
Ok. You are right. I was thinking in terms of my crossing reduction
method, not that of Sander. Sander's crossing minimization ignores the
subgraph constraints first and so has bad intermediate results. This
does not happen with my method, because the subgraph constraints are
respected right from the start.
> > If you do not have access to LNCS, I can send you a private copy.
>
> I'd appreciate that - I don't have access to this system.
IBM does not have a library with the LNCS (=Lecture Notes in Computer
Science) Series? I can hardly believe this. Anyway, I've put the paper
on my publications page, see above.
> > 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,
>
> I was thinking of performing the subgraph corrections halfway through
> the crossing minimization. Then, continue with crossing minimization
in
> a way which preserves subgraph integrity. Interleaving the two is
> probably equivalent, but slower.
I'd be interested in what you mean with "in a way which preserves
subgraph integrity". But maybe you should read my paper first. I think,
it does exactly that.
> > BTW: Which X-coordinate assignment algorithm do you use? Maybe you
are
>
> We are using a network simplex algorithm (the same one which
determines
> ranks) on an auxilary graph. This is described in a paper by Stephen
> North. [...]
http://citeseer.nj.nec.com/gansner93technique.html ?
You should definitely have a look at the Brandes/Köpf paper.
> I think the relavant problem to discuss now is the one I need
> to implement next. It is taking the converted DAG, and
> reordering ranks so as to restore the subgraph requirements.
> Sanders suggests generating a subgraph ordering graph using
> the initial MinCross results. He then suggests breaking
> cycles by removing the edges, but I think inverting the edges
> will give better results.
Isn't this equivalent? If you remove a cycle edge, the rest of the cycle
is equivalent to an inverted edge?
> Then, for each rank, sort the rank based on the subgraph
> ordering graph. This sounds easy, but the details of this
> step were left out. I don't think a traditional sorting
> method works here since we are dealing with a
> partially-ordered set.
Sorry, I do not quite understand. Isn't this simply topological sorting?
Mike
Attachment:
smime.p7s
Description: S/MIME cryptographic signature