MathGroup Archive 2007

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

Search the Archive

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


  • Prev by Date: Re: [TS 48]--Re:why isn't Rational[1,2] (apparently) atomic until it is evaluated?
  • Next by Date: Re: A pattern matching problem
  • Previous by thread: Re: Finding paths in graphs
  • Next by thread: Re: Re: Finding paths in graphs