Re: Finding paths in graphs

*To*: mathgroup at smc.vnet.net*Subject*: [mg72542] Re: Finding paths in graphs*From*: Arkadiusz.Majka at gmail.com*Date*: Sat, 6 Jan 2007 03:30:28 -0500 (EST)*References*: <enkrvm$9k0$1@smc.vnet.net>

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

**Follow-Ups**:**Re: Re: Finding paths in graphs***From:*John Dickmann <jqd@mit.edu>