code efficiency
- To: mathgroup at smc.vnet.net
- Subject: [mg64708] code efficiency
- From: John Dickman <johndickmann at cox.net>
- Date: Tue, 28 Feb 2006 01:49:40 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
I found the code below, which was posted here a few years ago.
----
<< DiscreteMath`Combinatorica`
AllPaths[g_Graph, {a_, b_}] :=
Module[{s = {a}, all = {}, done, adj = Edges[g], e = ToAdjacencyLists[
g], x,
v, ind, n = V[g]}, 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, AppendTo[s, x]; If[(x == b), AppendTo[all, s];
If[Length[s] >= 0, s = Drop[s, -1]]], If[Length[
s] > 0, s = Drop[s, -1]]; ind[[v]] = 1; all])]
];
all; Print["Start node: ", a, "; End
node: ", b, "; Number of Paths: ", Length[all]]]
------
It does what i want: find all the possible paths in a graph between
two nodes.
The trouble is, when the number of edges gets to be large, it
consumes a ton of computational time, on the order of hours for a 35
node, 87 edge graph.
Is there an easy way to get it to run faster?
(note the code was modified a bit from what was posted in order to
get it to give me complete paths in all cases).
thanks,
john