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

• Prev by Date: Re: Limit
• Next by Date: Gabor wavelet decomposition
• Previous by thread: solid of revolution
• Next by thread: Gabor wavelet decomposition