MathGroup Archive 2007

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

Search the Archive

Re: Finding paths in graphs

  • To: mathgroup at smc.vnet.net
  • Subject: [mg72538] Re: Finding paths in graphs
  • From: dh <dh at metrohm.ch>
  • Date: Fri, 5 Jan 2007 02:26:15 -0500 (EST)
  • References: <eniov4$heo$1@smc.vnet.net>


Hi,

assume your graph does not have circles. We want all pathes from Start 

to End. Nodes are represented by Integers and edges by rules and paths 

by list of integers. In the rules representing the graph, replace all 

edges away from End and replace them by a rule: End->e, where e is some 

symbol. E.g.

rules = {1 -> 2, 2 -> 3, 2 -> 4, 4 -> 3, 1 -> 3, 3 -> end};

We now define a new rule, that takes a path one step further:

r1=a:{b___,c_Integer}\[RuleDelayed] Sequence @@( Append[a,#]&/@ 

ReplaceList[c,rules]);

If we repeatedly apply r1 to the Start: {{1}} we get all pathes from 

Start to End:

{{1}}//.r1

this gives in our case: {{1,2,3,end},{1,2,4,3,end},{1,3,end}}



Replacement rules are certainly not the speediest approach, but it 

depends of the size of the graph if this is  reasonable or not.

Daniel



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

> 



  • Prev by Date: Re: List representation using element position
  • Next by Date: Re: Re: Re: Re: programming problem about elements
  • Previous by thread: Re: Finding paths in graphs
  • Next by thread: Re: Finding paths in graphs