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
>