MathGroup Archive 2001

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

Search the Archive

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

  • To: mathgroup at smc.vnet.net
  • Subject: [mg31809] Re: [mg31804] Re: [mg31755] Path finding in graph theory, Looking for your help
  • From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
  • Date: Mon, 3 Dec 2001 01:44:57 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

Sorry, the last input should have been AllHamiltonianPaths[gr,{1,3}]. (I 
changed the name of the function to make it more truthful after pasting 
it into the message and forgot to alter it where when the function is 
called).

On Sunday, December 2, 2001, at 06:25  PM, Andrzej Kozlowski wrote:

> 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: Weird trigonometric integral and Simplification question
  • Next by Date: Running system commands.
  • Previous by thread: Re: coloring everything outside a circle
  • Next by thread: Running system commands.