Home » Eclipse Projects » GEF » CDAG layout algorithm
| CDAG layout algorithm [message #88780] |
Tue, 29 July 2003 08:07  |
Eclipse User |
|
|
|
Originally posted by: forster.fmi.uni-passau.de
Hi,
The GEF 2.2 Release Plan mentions that you are planning on a Compound
Directed Acyclic Graph layout algorithm. Is there any additional
information available?
Mike
|
|
| | |
| Re: CDAG layout algorithm [message #89636 is a reply to message #89588] |
Tue, 05 August 2003 13:34  |
| Eclipse User |
|
|
|
Originally posted by: none.us.ibm.com
GREAT! Perhaps you'd like to shed some light on the subject. Are you
subscribed to the developement mailing list? We could talk about it there,
but I'll start here.
We are using the terminology from Sander 1996, and most of his algorithm.
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.
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.
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.
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.
"Michael Forster" <forster@fmi.uni-passau.de> wrote in message
news:bgohoc$her$1@eclipse.org...
> Randy Hudson wrote:
> > What would you like to know?
>
> Mainly, which algorithm(s) are used. I am interested, because layout of
> CDAGS is the main topic of my PhD-thesis.
>
> Mike
>
|
|
|
| Re: CDAG layout algorithm [message #89709 is a reply to message #89636] |
Tue, 05 August 2003 18:30 |
| Eclipse User |
|
|
|
Originally posted by: forster.fmi.uni-passau.de
Hi,
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
|
|
|
| Re: CDAG layout algorithm [message #89815 is a reply to message #89709] |
Wed, 06 August 2003 00:27 |
| Eclipse User |
|
|
|
Originally posted by: none.us.ibm.com
This is a multi-part message in MIME format.
------=_NextPart_000_0027_01C35BB1.8E30AEC0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
"Michael Forster" <forster@fmi.uni-passau.de> wrote in message =
news:bgpb4d$f4p$2@eclipse.org...
> Hi,
>=20
> Randy Hudson wrote:
> > GREAT! Perhaps you'd like to shed some light on the subject. =20
>=20
> I will do, what I can. I think, I have a reasonable overview over the=20
> field - well, I should have :-)
>=20
> Since my PhD-thesis demands an implementation of a CDAG layout=20
> algorithm, it may also be possible to contribute some code, but I =
cannot=20
> promise anything, mainly because I probably have a different time =
frame,=20
> and I cannot work full time on my implementation.
Don't worry about that. Our timeframe is pretty short, so maybe you =
could use/extend our implementation ;-)
>=20
> > Are you subscribed to the developement mailing list? =20
>=20
> I subscribed right now. This article is posted to the mailing list and =
> the newsgroup. I propose to continue on the mailing list.
>=20
> > We are using the terminology from Sander 1996, and most of his =
algorithm.
>=20
> I expected that, and it is probably the right decision. The most=20
> prominent alternative algorithm for directed layout of clustered =
graphs=20
> 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.
>=20
> Which publication of Sander are you using? His PhD-thesis is probably=20
> the best, but because it is in german, it may be unreadable for you. =
But=20
> IIRC, the technical report is also pretty detailed.
I am using the technical report.
>=20
> > 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.
>=20
> Probably only those nodes that have no incoming edges from other nodes =
> contained in the same subgraph? This is equivalent anyway. Does this=20
> give you a performance boost? Since the inserted edges are needed for=20
> the ranking step only, calculating the right edges might be more=20
> expensive than just inserting all of them. In my prototype I do not=20
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. If the subgraph's contents =
are relatively connected, you insert a small number of edges, which =
doesn't affect much. If the subgraph contains lots of disconnected =
nodes, then adding these edges helps keep the subgraph together during =
the MinCross stage of the layout.
> insert edges at all, but I just use the inclusion relationship as=20
> "implicit edges", when doing the ranking. I am not sure yet, however, =
if=20
> this is better. It also depends on the data structure used for storing =
> the graph.
>=20
> > 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.
>=20
> Sounds reasonable. I suggest, that you use some kind of grid / =
threshold=20
> technique for assigning the ranks, so that you don't end up with too=20
> many ranks. The number of ranks is probably the most important factor=20
> for the running time. Ranks with too little distance also make the=20
> layout look cluttered.
>=20
> > 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.
>=20
> For this, you might be interested in some of my work. See
>=20
> @InProceedings{forster02,
> author =3D "Forster, Michael",
> title =3D "Applying Crossing Reduction Strategies to Layered
> Compound Graphs",
> pages =3D "276--284",
> booktitle =3D "Proc. Graph Drawing, {GD} 2002",
> editor =3D "Kobourov, Stephen G. and Goodrich, Michael T.",
> series =3D "Lecture Notes in Computer Science",
> volume =3D 2528,
> publisher =3D "Springer",
> year =3D 2002
> }
>=20
> If you do not have access to LNCS, I can send you a private copy. This =
I'd appreciate that - I don't have access to this system.
> paper proposes an alternative to Sander's crossing reduction method.=20
> Instead of first ignoring the subgraphs and correcting the subgraph=20
> requirements afterwards, my algorithm respects the requirements right=20
> from the start. This leads to an (in some sense) optimal application =
of=20
> any two-layer crossing reduction method to CDAGS. It should generate=20
> 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.
> depending on the data structure. It probably is harder to implement,=20
> however, and I do not have empirical results up to now.
>=20
> > 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.
>=20
> I have not seen work on this yet. It is an interesting problem, =
however.=20
> I will think about it. Maybe, I'll have an idea. I suspect, however,=20
> that attaching edges to the center of a subgraph is not possible =
without=20
> increasing the number of crossings. or doing some undesireable edge=20
> routing.
Maybe you misunderstood me. It doesn't cause any edge crossing, it just =
affects horizontal alignment of a chain of subgraphs of different =
widths. Each subgraph's tail has to be placed somewhere, and assuming =
that all of the outgoing edges originate from the tail, it is desirable =
for that to be the bottom-center of the subgraphs bounding box. =
Alternatively, you could allow each edge to attach *anywhere* along the =
bottom edge of the box. But, it would still be nice to have a way to =
balance a chain of boxes such as:
+-----+
|a b c|
+-----+
|
+---+
| d |
+---+
>=20
> 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. We have an additional step for crude balancing of the nodes. =
BTW, this technique describes the "edge offsets" in relation to the =
nodes to which they attach.
I am considering performing this techinque bottom-up, assigning =
x-coordinates to the deepest subgraph's first, after which I will have =
determined their width, and therefore can determine where the heads and =
tails should be positioned in order to center connections to the =
subgraph. To do this, you would solve the subset of nodes and edges =
inside a subgraph. Once completed, the edges making up the spanning =
tree wouldn't be cut during the layout of the parent subgraph, even if =
they have negative cut-values.
> interested in this:
>=20
> Ulrik Brandes and Boris K=F6pf: Fast and Simple Horizontal Coordinate=20
> Assignment. Proc. 9th Intl. Symp. Graph Drawing (GD '01), LNCS 2265, =
pp.=20
> 31-44. =A9 Springer-Verlag, 2002.
I don't know where to download that either :-(
>=20
>=20
> 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=20
> this area, as this always contributes to my thesis. And solving real=20
> problems is always more satisfying than defining and solving =
theoretical=20
> problems :-).
>=20
> Regards, Mike
>=20
------=_NextPart_000_0027_01C35BB1.8E30AEC0
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Diso-8859-1">
<META content=3D"MSHTML 6.00.2726.2500" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>"Michael Forster" <</FONT><A=20
href=3D"mailto:forster@fmi.uni-passau.de"><FONT face=3DArial=20
size=3D2>forster@fmi.uni-passau.de</FONT></A><FONT face=3DArial =
size=3D2>> wrote in=20
message </FONT><A href=3D"news:bgpb4d$f4p$2@eclipse.org"><FONT =
face=3DArial=20
size=3D2>news:bgpb4d$f4p$2@eclipse.org</FONT></A><FONT face=3DArial=20
size=3D2>...</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>> Hi,<BR>> <BR>> Randy Hudson=20
wrote:<BR>> > GREAT! Perhaps you'd like to shed some light =
on the=20
subject. <BR>> <BR>> I will do, what I can. I think, I have =
a=20
reasonable overview over the <BR>> field - well, I should have =
:-)<BR>>=20
<BR>> Since my PhD-thesis demands an implementation of a CDAG layout =
<BR>>=20
algorithm, it may also be possible to contribute some code, but I cannot =
<BR>> promise anything, mainly because I probably have a different =
time=20
frame, <BR>> and I cannot work full time on my =
implementation.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Don't worry about that. Our =
timeframe is=20
pretty short, so maybe you could use/extend our implementation =
;-)<BR>>=20
<BR>> > Are you subscribed to the developement mailing list? =
<BR>> <BR>> I subscribed right now. This article is posted to the =
mailing=20
list and <BR>> the newsgroup. I propose to continue on the mailing=20
list.<BR>> <BR>> > We are using the terminology from Sander =
1996, and=20
most of his algorithm.<BR>> <BR>> I expected that, and it is =
probably the=20
right decision. The most <BR>> prominent alternative algorithm for =
directed=20
layout of clustered graphs <BR>> is an algorithm of Sugiyama / =
Misue,=20
1991. This paper is not easy to <BR>> understand, and I prefer =
Sander's=20
results from an aesthetical point of <BR>> view, anyway.<BR>> =
<BR>>=20
Which publication of Sander are you using? His PhD-thesis is probably =
<BR>>=20
the best, but because it is in german, it may be unreadable for you. But =
<BR>> IIRC, the technical report is also pretty =
detailed.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>I am using the technical =
report.<BR>> <BR>>=20
> We convert the CDAG to a simple DAG. So, for each subgraph, =
we=20
introduce a<BR>> > head and tail node. However, we don't =
connect=20
every node contained in the<BR>> > subgraph to both the head and=20
tail. Instead, we connect only a subset of<BR>> > the nodes =
to the=20
head and or tail nodes.<BR>> <BR>> Probably only those nodes that =
have no=20
incoming edges from other nodes <BR>> contained in the same subgraph? =
This is=20
equivalent anyway. Does this <BR>> give you a performance boost? =
Since the=20
inserted edges are needed for </FONT></DIV>
<DIV><FONT face=3DArial size=3D2>> the ranking step only, calculating =
the right=20
edges might be more <BR>> expensive than just inserting all of them. =
In my=20
prototype I do not </FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>I think this is both a performance and =
quality=20
boost. First, you want nodes within the same subgraph to have some =
small=20
amount of cohesion. Otherwise, they will end up almost =
anywhere. If=20
the subgraph's contents are relatively connected, you insert a small =
number of=20
edges, which doesn't affect much. If the subgraph contains lots of =
disconnected nodes, then adding these edges helps keep the subgraph =
together=20
during the MinCross stage of the layout.</FONT></DIV>
<DIV><BR><FONT face=3DArial size=3D2>> insert edges at all, but I =
just use the=20
inclusion relationship as <BR>> "implicit edges", when doing the =
ranking. I=20
am not sure yet, however, if <BR>> this is better. It also depends on =
the=20
data structure used for storing <BR>> the graph.<BR>> <BR>> =
> Also,=20
we don't use the rank spacing suggested. In our use cases, =
the<BR>>=20
> subgraphs have pretty large labels on them, so the heads and tails =
are=20
just<BR>> > as tall as other nodes in the graph.<BR>> <BR>> =
Sounds=20
reasonable. I suggest, that you use some kind of grid / threshold =
<BR>>=20
technique for assigning the ranks, so that you don't end up with too =
<BR>>=20
many ranks. The number of ranks is probably the most important factor =
<BR>>=20
for the running time. Ranks with too little distance also make the =
<BR>>=20
layout look cluttered.<BR>> <BR>> > So, once you layout the =
simple DAG,=20
you may have violated the subgraph<BR>> > requirements. This =
means=20
we need to make another pass through the ranks to<BR>> > respect =
the=20
subgraphs. This seems to be the hardest step in the =
process,<BR>> >=20
and it may introduce crosses which could be removed by another MinCross=20
pass<BR>> > which avoids mixing up subgraph boundaries.<BR>> =
<BR>>=20
For this, you might be interested in some of my work. See<BR>> =
<BR>>=20
@InProceedings{forster02,<BR>> author =3D "Forster,=20
Michael",<BR>> title =3D "Applying Crossing =
Reduction=20
Strategies to Layered<BR>>=20
&=
nbsp; =20
Compound Graphs",<BR>> pages=20
=3D &nb sp; "276--284",<BR>> =
=20
booktitle =3D "Proc. Graph Drawing, {GD} =
2002",<BR>>=20
editor =3D &nb sp; "Kobourov, =
Stephen G.=20
and Goodrich, Michael T.",<BR>> series=20
=3D &nb sp; "Lecture Notes in Computer=20
Science",<BR>> volume =
=3D &nb sp;=20
2528,<BR>> publisher =3D =
"Springer",<BR>>=20
year =3D &nb sp; =
2002<BR>>=20
}<BR>> <BR>> If you do not have access to LNCS, I can send you a =
private=20
copy. This </FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>I'd appreciate that - I don't have =
access to=20
this system.</FONT></DIV>
<DIV><BR><FONT face=3DArial size=3D2>> paper proposes an alternative =
to Sander's=20
crossing reduction method. <BR>> Instead of first ignoring the =
subgraphs and=20
correcting the subgraph <BR>> requirements afterwards, my algorithm =
respects=20
the requirements right <BR>> from the start. This leads to an (in =
some sense)=20
optimal application of <BR>> any two-layer crossing reduction method =
to=20
CDAGS. It should generate <BR>> fewer crossings than Sander's =
algorithm and=20
_might_ even be faster,</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>I was thinking of performing the =
subgraph=20
corrections halfway through the crossing minimization. Then, =
continue with=20
crossing minimization in a way which preserves subgraph integrity. =
Interleaving the two is probably equivalent, but =
slower.</FONT></DIV>
<DIV><BR><FONT face=3DArial size=3D2>> depending on the data =
structure. It=20
probably is harder to implement, <BR>> however, and I do not have =
empirical=20
results up to now.<BR>> <BR>> > Another area of difficulty for =
us is in=20
assigning the attachment point for<BR>> > edges between =
subgraphs. =20
You don't know how wide a subgraph is going to be<BR>> > until you =
have=20
solved the X-coordinate assigment. In some cases, you want<BR>> =
>=20
edges to be attached at the center of the nodes/subgraphs.<BR>> =
<BR>> I=20
have not seen work on this yet. It is an interesting problem, however. =
<BR>>=20
I will think about it. Maybe, I'll have an idea. I suspect, however, =
<BR>>=20
that attaching edges to the center of a subgraph is not possible without =
<BR>> increasing the number of crossings. or doing some =
undesireable=20
edge <BR>> routing.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Maybe you misunderstood me. It =
doesn't cause=20
any edge crossing, it just affects horizontal alignment of a chain of =
subgraphs=20
of different widths. Each subgraph's tail has to be placed =
somewhere, and=20
assuming that all of the outgoing edges originate from the tail, it is =
desirable=20
for that to be the bottom-center of the subgraphs bounding box. =20
Alternatively, you could allow each edge to attach *anywhere* along the =
bottom=20
edge of the box. But, it would still be nice to have a way to =
balance a=20
chain of boxes such as:</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>+-----+</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2>|a b c|</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2>+-----+</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2> |</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2>+---+</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2>| d |</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2>+---+</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT><FONT face=3DArial =
size=3D2></FONT><BR><FONT=20
face=3DArial size=3D2>> <BR>> BTW: Which X-coordinate assignment =
algorithm do=20
you use? Maybe you are </FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>We are using a network simplex =
algorithm (the same=20
one which determines ranks) on an auxilary graph. This is =
described in a=20
paper by Stephen North. We have an additional step for crude =
balancing of=20
the nodes. BTW, this technique describes the "edge offsets" in =
relation to=20
the nodes to which they attach.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>I am considering performing this =
techinque=20
bottom-up, assigning x-coordinates to the deepest subgraph's first, =
after which=20
I will have determined their width, and therefore can determine where =
the heads=20
and tails should be positioned in order to center connections to the=20
subgraph. To do this, you would solve the subset of nodes and =
edges inside=20
a subgraph. Once completed, the edges making up the spanning tree =
wouldn't=20
be cut during the layout of the parent subgraph, even if they have =
negative=20
cut-values.</FONT></DIV>
<DIV><BR><FONT face=3DArial size=3D2>> interested in this:<BR>> =
<BR>> Ulrik=20
Brandes and Boris K=F6pf: Fast and Simple Horizontal Coordinate <BR>> =
Assignment. Proc. 9th Intl. Symp. Graph Drawing (GD '01), LNCS 2265, pp. =
<BR>> 31-44. =A9 Springer-Verlag, 2002.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>I don't know where to download that =
either=20
:-(</FONT></DIV>
<DIV><BR><FONT face=3DArial size=3D2>> <BR>> <BR>> I hope, I =
could help a=20
bit. If you have further questions or problems, <BR>> feel free to =
ask. I am=20
interested in solving any problems related to <BR>> this area, as =
this always=20
contributes to my thesis. And solving real <BR>> problems is always =
more=20
satisfying than defining and solving theoretical <BR>> problems =
:-).<BR>>=20
<BR>> Regards, Mike<BR>> </FONT></DIV></BODY></HTML>
------=_NextPart_000_0027_01C35BB1.8E30AEC0--
|
|
| |
Goto Forum:
Current Time: Thu Jul 03 20:38:17 EDT 2025
Powered by FUDForum. Page generated in 0.05416 seconds |
Home