MathGroup Archive 2001

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

Search the Archive

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

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

It has been pointed out to me that my usage of the words "Hamiltonian" 
and "Eulerian" in answering this question was non-standard and 
misleading, since it in the usual meaning of these phrases  a 
Hamiltonian path visits all vertices and and Eulerian path all edges 
exactly once. What I referred to as "Hamiltonion paths" are just paths 
that visit each vertex only once but do not necessarily pass through all 
vertices. Usually in graph theory various words are used to distinguish 
paths that are allowed or not allowed to go through the same vertex or 
edge: words like path, trail, walk and so on. But the difference between 
these seems to me quite arbitrary and I can never remember which is 
which. So I prefer to use the word "Hamiltonian path" for that does not 
go through the same vertex more than once and "full Hamiltonian path" 
for one that goes through all the vertices exactly once. While I do not 
think anyone else uses this nomenclature it seems to me that it has the 
advantage of being easy to remember.

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

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}}
>

>
> 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: coloring eveerything outside a circle
  • Next by Date: Re: can Mathematica generate itself a function?
  • Previous by thread: Re: Re: Re: scope all wrong? in Mathematica 4.1
  • Next by thread: how to round value in matrixs