MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

code efficiency

  • To: mathgroup at
  • Subject: [mg64708] code efficiency
  • From: John Dickman <johndickmann at>
  • Date: Tue, 28 Feb 2006 01:49:40 -0500 (EST)
  • Sender: owner-wri-mathgroup at

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).


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