Re: Re: Graph issue
- To: mathgroup at smc.vnet.net
- Subject: [mg102019] Re: [mg101992] Re: [mg101968] Graph issue
- From: "Stuart Nettleton" <stuart.nettleton at optusnet.com.au>
- Date: Sun, 26 Jul 2009 05:53:27 -0400 (EDT)
- References: <200907241015.GAA17472@smc.vnet.net>
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 http://en.wikipedia.org/wiki/Topological_sort Best regards, Stuart On Sat, 25 Jul 2009 18:18:46 +1000, Daniel Lichtblau <danl at wolfram.com> wrote: > 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 defects.
- References:
- Graph issue
- From: "Stuart Nettleton" <stuart.nettleton@optusnet.com.au>
- Graph issue