[Date Index]
[Thread Index]
[Author Index]
Re: Re: Finding paths in graphs
*To*: mathgroup at smc.vnet.net
*Subject*: [mg72550] Re: [mg72542] Re: Finding paths in graphs
*From*: John Dickmann <jqd at mit.edu>
*Date*: Sat, 6 Jan 2007 23:23:04 -0500 (EST)
*References*: <enkrvm$9k0$1@smc.vnet.net> <200701060830.DAA02594@smc.vnet.net>
Arek,
this looks like it works (see addition in bold below).
john
>> << DiscreteMath`Combinatorica`
>> << DiscreteMath`GraphPlot`;
>> AllPaths[g_Graph, {a_, b_}] :=
>> Module[{s = {a}, done, npath = 0, e = ToAdjacencyLists[g], x,
>> v, ind, n = V[g], c = 0}, 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, s = {s, x}; s = Flatten[s]; If[(x ==
>> b), Print[s]; npath = npath + 1;(*If[npath == c +
>> 1000, Print["npath: ", npath]; c = npath];*)If[Length[s] >= 0,
>> s =
>> Drop[s, -1]]],
>> If[Length[s] > 0, s = Drop[s, -1]]; ind[[v]] =
>> 1]]; Print["Start node: ", a, "; End node: ", b, ";
>> Number of Paths: ", npath]]
On Jan 6, 2007, at 3:30 AM, Arkadiusz.Majka at gmail.com wrote:
> Great!
>
> John, could you please rewrite a bit your and Andrzej's code and print
> all pathes (not only their number)
>
> Thanks,
>
> Arek
>
>
> John Dickmann napisal(a):
>> OT,
>>
>> this works for me, courtesy of Andrezj Koslowski from a 1996 posting,
>> modified to improve speed some.
>>
>> If there's anybody else out there who has a faster way to do this,
>> I'd really like to see it.
>>
>> << DiscreteMath`Combinatorica`
>> << DiscreteMath`GraphPlot`;
>> AllPaths[g_Graph, {a_, b_}] :=
>> Module[{s = {a}, done, npath = 0, e = ToAdjacencyLists[g], x,
>> v, ind, n = V[g], c = 0}, 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, s = {s, x}; s = Flatten[s]; If[(x ==
>> b), npath = npath + 1;(*If[npath == c +
>> 1000, Print["npath: ", npath]; c = npath];*)If[Length[s] >= 0,
>> s =
>> Drop[s, -1]]],
>> If[Length[s] > 0, s = Drop[s, -1]]; ind[[v]] =
>> 1]]; Print["Start node: ", a, "; End node: ", b, ";
>> Number of Paths: ", npath]]
>>
>> john
>>
>> On Jan 4, 2007, at 7:00 AM, 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
>>>
>>
>> John Q. Dickmann
>> Research Assistant
>> Lean Aerospace Initiative
>> Massachusetts Institute of Technology
>> Bldg 41-205
>> 77 Massachusetts Ave.
>> Cambridge, MA 02139
>>
>> jqd at mit.edu
>> 401-225-3511
>
John Q. Dickmann
Research Assistant
Lean Aerospace Initiative
Massachusetts Institute of Technology
Bldg 41-205
77 Massachusetts Ave.
Cambridge, MA 02139
jqd at mit.edu
401-225-3511
Prev by Date:
**Re: Re: A pattern matching problem**
Next by Date:
**conversion from DensityGraphics to Graphics ignores ColorFunctionScaling->False in Mathematica 5.2**
Previous by thread:
**Re: Finding paths in graphs**
Next by thread:
**Orderless attribute for named functions and function arguments**
| |