MathGroup Archive 2007

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

Search the Archive

Re: Finding paths in graphs

  • To: mathgroup at smc.vnet.net
  • Subject: [mg72527] Re: [mg72524] Finding paths in graphs
  • From: John Dickmann <jqd at mit.edu>
  • Date: Fri, 5 Jan 2007 01:42:04 -0500 (EST)

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



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