Graph issue

• To: mathgroup at smc.vnet.net
• Subject: [mg101968] Graph issue
• From: "Stuart Nettleton" <stuart.nettleton at optusnet.com.au>
• Date: Fri, 24 Jul 2009 06:15:06 -0400 (EDT)

```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. Ant
thoughts would be appreicated! Stuart

<< Combinatorica`
myverts1 = {a, b, c, h, d, e, f, g};
myedges1 = {{g, h}, {a, c}, {b, d}, {c, e}, {d, f}, {e, g}, {f, g}};
mygraph1 =
MakeGraph[myverts1, (MemberQ[myedges1, {#1, #2}]) &,
Type -> Directed, VertexLabel -> True];
ShowGraph[mygraph1]
Print["Before Edges: ", myedges1]
Print["After Edges: ", Map[myverts1[[#]] &, Edges[mygraph1]]]
Print["Before Leaves: ", {a, b}]
Print["After Leaves: ", Pick[myverts1, InDegree[mygraph1], 0]]
Print["Topological sort1: ", myverts1[[TopologicalSort[mygraph1]]]]

Clear[visit];
toposort = {}; nodes = myverts1;
visited = Table[False, {t, Length[nodes]}];
visit[n_] := Module[{},
If[Pick[visited, nodes, n] == {False},
visited[[Position[nodes, n][[1, 1]]]] = True;
Map[visit,
Cases[Map[Reverse, myedges1], {a_, b_} /; a == n][[All, 2]]];
toposort = Append[toposort, n]
]
];
Map[visit, nodes];
Print["Topological sort2: ", toposort]

--
UTS CRICOS Provider Code:  00099F
DISCLAIMER: This email message and any accompanying attachments may contain
confidential information.  If you are not the intended recipient, do not
read, use, disseminate, distribute or copy this message or attachments.  If