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 >