MathGroup Archive 2009

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

Search the Archive

Re: Re: Graph issue

  • To: mathgroup at
  • Subject: [mg102019] Re: [mg101992] Re: [mg101968] Graph issue
  • From: "Stuart Nettleton" <stuart.nettleton at>
  • Date: Sun, 26 Jul 2009 05:53:27 -0400 (EDT)
  • References: <>

Hi Daniel, Many thanks for looking at this. Perhaps I have complicated the  
issue by mentioning TopologicalSort. The key matter I wanted raised is  
that MakeGraph produces an apparently incorrect result, which you can see  
in the result from ShowGraph where the arrow is from h to g, when it  
should be from g to h. The second matter I wanted to raise is that the use  
of the graph gives the incorrect result. This was to confirm that it is  
actually MakeGraph and not ShowGraph or some other representation that is  
wrong. Instead of involving Topological Sort, I could have used InDegree  
or some other function to demonstrate that the result of MakeGraph was  
wrong. I am sorry that this has been confusing, as I am not suggesting  
that TopologicalSort acts incorrectly. You may recall the acyclic solver I  
posted on MathGroup for the very difficult task of optimising a objective  
function containing the whole of William Nordhaus' nonlinear global  
warming-economic DICE model. In this acyclic solver I make extensive use  
of graphical processing. MakeGraph is indispensable for this so it is  
essential for me that MakeGraph works properly. I first noticed that  
something appeared to change in the way it worked when I upgraded from  
Mathematica V6.01 to V6.3. However, I was continuing my economic-climate  
research by moving the nonlinear model into the constraints. FindMinimum  
doesn't allow numerical processing in constraints in the same way as we  
are able force numerical processing of objective functions with  
_?NumericQ. I had to put aside my acyclic solver and settle for symbolic  
processing by limiting the scope of my model from 60 decades to 13  
decades. You were very kind in helping me to stretch this boundary as much  
as possible! FindMinimum is already a magnificient operations research  
function but a major enhancement would be to provide for external  
numerical processing of constraints. I really appreciate you providing the  
topological solver code, which I will remember for other purposes. Many  
thanks for responding to my post (and thanks to the others on the  
MathGroup who have so graciously included me in their correspondence on  
the matter).
BTW the topological sort I provided was Tarjan (1976) depth-first method.  
It is the second method at
Best regards,

On Sat, 25 Jul 2009 18:18:46 +1000, Daniel Lichtblau <danl at>  

> Stuart Nettleton 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. Any
>> thoughts would be appreciated! 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]
> So far as I can tell, TopologicalSort gives a valid result. I cannot
> figure out what your code does.
> Here is code that works reasonably fast for a dense coding of the
> directed edge 0-1 matrix. It uses Range[n] to denote the n vertices. You
> can convert to letters or whatever after the fact.
> toposort3C = Compile[{{mat, _Integer, 2}}, Module[
>     {v, n = Length[mat], k, m, res},
>     v = Total[mat];
>     m = 0;
>     res = Table[0, {n}];
>     While[m < n,
>      m++;
>      For[k = 1, k <= n, k++, If[v[[k]] == 0, Break[]]];
>      v[[k]] = -1;
>      v -= mat[[k]];
>      res[[m]] = k;
>      ];
>     res
>     ]]
> One can get better algorithmic complexity using a sparse representation.
> Daniel Lichtblau
> WOlfram Research

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

  • References:
    • Graph issue
      • From: "Stuart Nettleton" <>
  • Prev by Date: Mathematica Animations by High School Students
  • Next by Date: Re: Re: Graph issue
  • Previous by thread: Re: Graph issue
  • Next by thread: Re: Graph issue