       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