Re: Re: Finding paths in graphs

*To*: mathgroup at smc.vnet.net*Subject*: [mg72550] Re: [mg72542] Re: Finding paths in graphs*From*: John Dickmann <jqd at mit.edu>*Date*: Sat, 6 Jan 2007 23:23:04 -0500 (EST)*References*: <enkrvm$9k0$1@smc.vnet.net> <200701060830.DAA02594@smc.vnet.net>

Arek, this looks like it works (see addition in bold below). john >> << 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), Print[s]; 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]] On Jan 6, 2007, at 3:30 AM, Arkadiusz.Majka at gmail.com wrote: > Great! > > John, could you please rewrite a bit your and Andrzej's code and print > all pathes (not only their number) > > Thanks, > > Arek > > > John Dickmann napisal(a): >> 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 > 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

**References**:**Re: Finding paths in graphs***From:*Arkadiusz.Majka@gmail.com