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