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

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

```

• Prev by Date: Re: Forcing vertical scale on Histogram
• Next by Date: Optimize evaluation of symbolic expressions
• Previous by thread: Re: Re: Graph issue
• Next by thread: Re: Re: Graph issue