Re: Finding paths in graphs

*To*: mathgroup at smc.vnet.net*Subject*: [mg72527] Re: [mg72524] Finding paths in graphs*From*: John Dickmann <jqd at mit.edu>*Date*: Fri, 5 Jan 2007 01:42:04 -0500 (EST)

OT, this works for me, courtesy of Andrezj Koslowski from a 1996 posting, modified to improve speed some. If there's anybody else out there who has a faster way to do this, I'd really like to see it. << DiscreteMath`Combinatorica` << DiscreteMath`GraphPlot`; AllPaths[g_Graph, {a_, b_}] := Module[{s = {a}, done, npath = 0, e = ToAdjacencyLists[g], x, v, ind, n = V[g], c = 0}, ind = Table[1, {n}]; While[Length[s] > 0, v = Last[s]; done = False; While[ind[[v]] <= Length[e[[v]]] && ! done, If[! MemberQ[s, (x = e[[v, ind[[v]]++]])], done = True]]; If[done, s = {s, x}; s = Flatten[s]; If[(x == b), npath = npath + 1;(*If[npath == c + 1000, Print["npath: ", npath]; c = npath];*)If[Length[s] >= 0, s = Drop[s, -1]]], If[Length[s] > 0, s = Drop[s, -1]]; ind[[v]] = 1]]; Print["Start node: ", a, "; End node: ", b, "; Number of Paths: ", npath]] john On Jan 4, 2007, at 7:00 AM, OT wrote: > Hi all, > > I have a big oriented graph in a Mathematica notebook, described as a > list of rule (i.e the graph is something like {1->2 , 1->3, 2- > >3, ... }) > and I want to find all the path from vertex 'a' to vertex 'b'... > > How can I do that ? The function ShortestPath doesn't work on graphs > defined in this way, and moreover this function only return one of the > shortest paths, while I'm looking for all the existing paths... > > thanks, > OT > John Q. Dickmann Research Assistant Lean Aerospace Initiative Massachusetts Institute of Technology Bldg 41-205 77 Massachusetts Ave. Cambridge, MA 02139 jqd at mit.edu 401-225-3511