MathGroup Archive 2001

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

Search the Archive

Re: Path finding in graph theory, Lookig for your help,

  • To: mathgroup at smc.vnet.net
  • Subject: [mg31804] Re: [mg31755] Path finding in graph theory, Lookig for your help,
  • From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
  • Date: Sun, 2 Dec 2001 04:25:53 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

What do you mean by all routes? Clearly there are infinitely many of 
them so you have to specify some condition that will make the number 
finite. For example, you may require that each vertex only appears once 
in a route (a Hamiltonian condition), or that each edge appears only 
once (Eulerian) or that the length is bounded by some integer. In any 
case, you will need to use backtracking so the program will be slow. You 
can modify one of the existing functions in the Combinatorica package to 
do what you want. For example, here is a (quickly done so possibly 
buggy!) modification of the HamiltonianCycle function which should give 
all Hamiltonian paths between two vertices:

<< DiscreteMath`Combinatorica`

AllHamiltonianPaths[g_Graph, {a_, b_}] :=
   Module[{s = {a}, all = {}, done, adj = Edges[g], e = 
ToAdjacencyLists[g], x,
        v, ind, n = V[g]}, 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, AppendTo[s, x], If[Length[s] > 0, s = Drop[s, -1]];
         ind[[v]] = 1];
       If[(x == b), AppendTo[all, s];
         If[Length[s] > 0, s = Drop[s, -1]]]];
     all]


gr = RandomGraph[5, 0.6]; ShowLabeledGraph[gr]

(picture supressed)

In[5]:=
ToAdjacencyLists[gr]

Out[5]=
{{5},{3,4,5},{2,5},{2,5},{1,2,3,4}}


In[6]:=
AllPaths[gr,{1,3}]

Out[6]=
{{1,5,2,3},{1,5,3},{1,5,4,2,3}}

Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/

On Saturday, December 1, 2001, at 04:44  PM, nem nemran wrote:

> Dear,
> While am surveying through MathGroup Archive
> April/1998, I have noticed that you addressed the
> following problem:
> "I'm modelling a computer network as a graph and would
> like to find an algorithm in Mathematica that will
> return all 'routes' from one vertex to another.  There
> are some algorithms within the DiscreteMaths package
> that will return the shortest path between two
> vertices, but none (it appears) that return all
> paths."
>
> Am looking for an algorithim that find all paths
> "routes" between two vertex.
>
> I appreciate any comment and help.
>
> Yours,
>
> Nemran
>
> University of Leeds
>
>
> __________________________________________________
> Do You Yahoo!?
> Yahoo! GeoCities - quick and easy web site hosting, just $8.95/month.
> http://geocities.yahoo.com/ps/info1
>
>
>



  • Prev by Date: Re: shuffling a deck of cards
  • Next by Date: RE: shuffling a deck of cards
  • Previous by thread: Path finding in graph theory, Lookig for your help,
  • Next by thread: "Incremental Integration"?