Re: Graph issue
- To: mathgroup at smc.vnet.net
- Subject: [mg101982] Re: Graph issue
- From: mark mcclure <mcmcclur314 at gmail.com>
- Date: Sat, 25 Jul 2009 04:16:58 -0400 (EDT)
- References: <h4c1il$h18$1@smc.vnet.net>
On Jul 24, 6:14 am, "Stuart Nettleton"
<stuart.nettle... at optusnet.com.au> wrote:
> Hi friends, a change appears to have occurred in the behaviour of
> MakeGraph between Versions 6 and 7.01 (which has caused me some grief!)
> Below is a small example problem that produces the wrong answer in
> Version 7.01.0, both 32bit and 64bit. A small topological sort I have
> included shows Combinatorica's topological sort also gives the wrong
> answer.
The problem is not in the TopologicalSort function, but rather the
MakeGraph function. Note that the V7 MakeGraph returns a graph
containing the edge {4,8} (or {h,g}, in the original notation), while
the V6 version returns the correct {8.4}. After a quick look at the
Combinatorica package, I don't really see why.
Why don't you represent you graph as a list of edge rules and use
ToCombinatoricaGraph from the GraphUtilities package, if you need to
use Combinatorica. Thus,
Needs["GraphUtilities`"];
G = Rule @@@ {{g, h}, {a, c}, {b, d},
{c, e}, {d, f}, {e, g}, {f, g}};
GraphPlot[G, DirectedEdges -> True,
VertexLabeling -> True,
Method -> "CircularEmbedding"]
It's easy to see that we get the correct graph. Now, the
TopologicalSort.
VertexList[G][[TopologicalSort[
ToCombinatoricaGraph[G]]]]
Mark McClure
- Follow-Ups:
- Re: Re: Graph issue
- From: stu-ultimo <stu-ultimo@optusnet.com.au>
- Re: Re: Graph issue