Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2006
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2006

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

Search the Archive

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