[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
[
List Home]
|
[gef-dev] Rép. : gef-dev digest, Vol 1 #97 - 1 msg (Réponse automatique)
|
Je suis absent du mercredi 13 août au mercredi 27 août inclus.
Pour toute urgence, contacter Jocelyn Carfantan au 55.15.
--------------------------------------------------------------------------------------------------
Antony GUILLOTEAU - Système U Ouest
Service : DSI - Normes / Méthodes / Qualité
Tél : 02.40.68.59.59 poste 51.08
E-mail : antony.guilloteau@xxxxxxxxxxxx
>>> "gef-dev@xxxxxxxxxxx" 12/08/03 18h00 >>>
Send gef-dev mailing list submissions to
gef-dev@xxxxxxxxxxx
To subscribe or unsubscribe via the World Wide Web, visit
http://dev.eclipse.org/mailman/listinfo/gef-dev
or, via email, send a message with subject or body 'help' to
gef-dev-request@xxxxxxxxxxx
You can reach the person managing the list at
gef-dev-admin@xxxxxxxxxxx
When replying, please edit your Subject line so it is more specific
than "Re: Contents of gef-dev digest..."
Today's Topics:
1. RE: CDAG layout algorithms (Randy Hudson)
--__--__--
Message: 1
To: gef-dev@xxxxxxxxxxx
Subject: RE: [gef-dev] CDAG layout algorithms
From: Randy Hudson <hudsonr@xxxxxxxxxx>
Date: Mon, 11 Aug 2003 14:29:23 -0400
Reply-To: gef-dev@xxxxxxxxxxx
This is a multipart message in MIME format.
--=_alternative 0065BDD785256D7F_=
Content-Type: text/plain; charset="US-ASCII"
Any suggestions on how to break cycles without violating subgraph
requirements? It seems like inverting random edges could result in a
situation where the bottom of a subgraph is not below all of the nodes
inside it.
If possible, I was wondering if I could write one algorithm which inverts
edges, thus removing cycles, for both directed and compound directed. If
not possible, what is the technique for compound graphs? Perhaps a
modification to the greedy algorithm (Graph Drawing 1999), which uses a
left and right stack. The first time a node N belonging to subgraph S is
added to "left", the top boundary for its subgraph is added first.
Something similar for bottom boundaries.
-Randy
"Michael Forster" <forster@xxxxxxxxxxxxxxxxx>
Sent by: gef-dev-admin@xxxxxxxxxxx
08/07/2003 05:11 PM
Please respond to gef-dev
To: <gef-dev@xxxxxxxxxxx>
cc:
Subject: RE: [gef-dev] CDAG layout algorithms
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
_______________________________________________
gef-dev mailing list
gef-dev@xxxxxxxxxxx
http://dev.eclipse.org/mailman/listinfo/gef-dev
--=_alternative 0065BDD785256D7F_=
Content-Type: text/html; charset="US-ASCII"
<br><font size=2 face="sans-serif">Any suggestions on how to break cycles
without violating subgraph requirements? It seems like inverting
random edges could result in a situation where the bottom of a subgraph
is not below all of the nodes inside it.</font>
<br>
<br><font size=2 face="sans-serif">If possible, I was wondering if I could
write one algorithm which inverts edges, thus removing cycles, for both
directed and compound directed. If not possible, what is the technique
for compound graphs? Perhaps a modification to the greedy algorithm
(Graph Drawing 1999), which uses a left and right stack. The first
time a node N belonging to subgraph S is added to "left", the
top boundary for its subgraph is added first. Something similar for
bottom boundaries.</font>
<br>
<br><font size=2 face="sans-serif">-Randy</font>
<br>
<br>
<br>
<br>
<table width=100%>
<tr valign=top>
<td>
<td><font size=1 face="sans-serif"><b>"Michael Forster" <forster@xxxxxxxxxxxxxxxxx></b></font>
<br><font size=1 face="sans-serif">Sent by: gef-dev-admin@xxxxxxxxxxx</font>
<p><font size=1 face="sans-serif">08/07/2003 05:11 PM</font>
<br><font size=1 face="sans-serif">Please respond to gef-dev</font>
<td><font size=1 face="Arial"> </font>
<br><font size=1 face="sans-serif"> To:
<gef-dev@xxxxxxxxxxx></font>
<br><font size=1 face="sans-serif"> cc:
</font>
<br><font size=1 face="sans-serif"> Subject:
RE: [gef-dev] CDAG layout algorithms</font></table>
<br>
<br>
<br><font size=2><tt>Hi,<br>
<br>
> I've skimmed over your paper. The sub-optimal reodering <br>
> shown in Figure 6 could be corrected by a final pass through <br>
> the graph which exchanges "adjacent pairs" of nodes if it
<br>
> improves the quality of the layout. <br>
<br>
Of course. This is just a minimal example where Sander's algorithm<br>
fails. So it is not surprising that a simple heuristic can solve this<br>
particular problem. But remember: It still stays a heuristic, and it<br>
does no solve the fundamental problem. So you will definitely get<br>
unneccessary crossings.<br>
<br>
> My concern with preserving the containment hierarchy during <br>
> the crossing reduction is that this prevents a node from <br>
> gradually passing through a subgraph to which it doesn't <br>
> belong. <br>
<br>
This does not happen, and this is proven (Well, the proof is sketched,<br>
at least :-) in the paper.<br>
<br>
> It seems like using your algorithm, the node would <br>
> have to jump across the whole subgraph (compound node) at <br>
> once, or not at all. <br>
<br>
This is correct, and the nodes make these big jumps. If two subgraphss<br>
which are high in the subgraph hierarchy are exchanged while applying<br>
the crossing reduction to an enclosing subgraph or the root of the<br>
subgraph hierarchy, the dependent (base) nodes "jump" over the
whole<br>
other subgraph.<br>
<br>
I admit that my algorithm may be harder to understand and implement than<br>
Sander's. But it is better than Sander's by proof. It is even optimal if<br>
only considered according to a single rank (=layer=level). This means,<br>
there will be only unnecessary crossings that come from the underlying<br>
2-level crossing reduction (These occur in both algorithms - the problem<br>
is NP-hard, so you cannot expect global optimality), but _no_ crossings<br>
that come from the application to the clustered graph. Sander's<br>
application generates such crossings. So I am highly convinced that my<br>
algorithm performs better than Sander's. Of course, I am biased, and I<br>
do not have numbers to substantiate my opinion, but the theoretical<br>
results in my paper promise good practical results. By the way: I talked<br>
to Sander last year after my talk at the conference, and he admitted<br>
that my method is more promising than his quick-and-dirty solution.<br>
<br>
Note that I do not want to persuade you to use my algorithm, especially,<br>
if you are under deadline pressure and fully understand Sander's<br>
algorithm but not mine. On the contrary: I will be happy to have an<br>
implementation of Sander's algorithm to compare to mine in my thesis<br>
:-).<br>
<br>
By the way: Would it be possible, to have a look at your code? It will<br>
be published under the CPL anyway, right?<br>
<br>
> Here is a case <br>
> where reversing the edge from a cycle is better than removing it.
<br>
> <br>
> Given Subgraph A with members a1, a2, a3 <br>
> Given Subgraph B with members b1, b2, b3 <br>
> And a node X. <br>
> <br>
> Ignoring all edges, here are the final rank orderings: <br>
> a1 b1 <br>
> a2 b2 <br>
> b3 X a3 <br>
> <br>
> The two subgraphs are intertwined, with a random node falling <br>
> between them. <br>
> The cycle A -> B -> X -> A exists. If you break X ->
A, you <br>
> then end up with last row of: <br>
> a3 b3 X <br>
> But, if you reverse it to be A->X, you have partial ordering <br>
> A->X, and A->B, which allows for: <br>
> a3 X b3 <br>
<br>
No, it does not, because you forgot the edge B -> X, which still exists.<br>
<br>
In general: If you have a cycle<br>
<br>
X1 -> X2 -> ... -> Xn -> X1<br>
<br>
and you break it up at Xn -> X1, it does not matter whether the edge<br>
<br>
X1 -> Xn<br>
<br>
is inserted, because the partial ordering is transitive, and so Xn has<br>
to be right of X1 anyway. This means, the quality depends only on the<br>
concrete implementation of the topological ordering, but not on the edge<br>
X1 -> Xn.<br>
<br>
<br>
Regards, Mike<br>
<br>
_______________________________________________<br>
gef-dev mailing list<br>
gef-dev@xxxxxxxxxxx<br>
http://dev.eclipse.org/mailman/listinfo/gef-dev<br>
</tt></font>
<br>
--=_alternative 0065BDD785256D7F_=--
--__--__--
_______________________________________________
gef-dev mailing list
gef-dev@xxxxxxxxxxx
http://dev.eclipse.org/mailman/listinfo/gef-dev
End of gef-dev Digest
