Re: Finding paths in graphs

*To*: mathgroup at smc.vnet.net*Subject*: [mg72532] Re: Finding paths in graphs*From*: Peter Pein <petsie at dordos.net>*Date*: Fri, 5 Jan 2007 02:02:09 -0500 (EST)*Organization*: 1&1 Internet AG*References*: <eniov4$heo$1@smc.vnet.net>

OT schrieb: > 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 > Hi, if your graph is free of loops, the following should work: paths[gr_, from_, to_] := Reap[NestWhile[ Flatten[Map[ #1 /. {a___, b_} /; (If[b === to, Sow[{a, b}]]; True) :> ({a, b, #1} & ) /@ ReplaceList[b, gr] & , #1, {-2}], 1] & , {{from}}, #1 =!= {} & ]][[2,1]] In[2]:= paths[{1 -> 2, 1 -> 3, 2 -> 3}, 1, 3] Out[2]= {{1, 3}, {1, 2, 3}} In[3]:= gr = DeleteCases[Flatten[ Table[{If[Mod[i, 4] > 0, i -> i + 1], If[i < 12, i -> i + 4]}, {i, 15}]], Null] Out[3]= {1 -> 2, 1 -> 5, 2 -> 3, 2 -> 6, 3 -> 4, 3 -> 7, 4 -> 8, 5 -> 6, 5 -> 9, 6 -> 7, 6 -> 10, 7 -> 8, 7 -> 11, 8 -> 12, 9 -> 10, 9 -> 13, 10 -> 11, 10 -> 14, 11 -> 12, 11 -> 15, 13 -> 14, 14 -> 15, 15 -> 16} In[4]:= paths[gr, 1, 16] Out[4]= {{1, 2, 3, 7, 11, 15, 16}, {1, 2, 6, 7, 11, 15, 16}, {1, 2, 6, 10, 11, 15, 16}, {1, 2, 6, 10, 14, 15, 16}, {1, 5, 6, 7, 11, 15, 16}, {1, 5, 6, 10, 11, 15, 16}, {1, 5, 6, 10, 14, 15, 16}, {1, 5, 9, 10, 11, 15, 16}, {1, 5, 9, 10, 14, 15, 16}, {1, 5, 9, 13, 14, 15, 16}} In[7]:= paths[gr, 2, 7] Out[7]= {{2, 3, 7}, {2, 6, 7}} hth, Peter