Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2007
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: A pattern matching problem
  • Next by Date: Re: Orderless attribute for named functions and function arguments
  • Previous by thread: Re: Finding paths in graphs
  • Next by thread: Re: Finding paths in graphs