Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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
you have received this message in error, please notify the sender
immediately and delete this message. Any views expressed in this message
are those of the individual sender, except where the sender expressly, and
with authority, states them to be the views the University of Technology,
Sydney. Before opening any attachments, please check them for viruses and
defects.

• Follow-Ups:
  • Re: Re: Graph issue
    • From: "Stuart Nettleton" <stuart.nettleton@optusnet.com.au>
  • Re: Graph issue
    • From: Daniel Lichtblau <danl@wolfram.com>