L     F       B
 / | \ /  \    / | \
R--J--X----D--Q  P  M
 \ | /         \ |  |
   Z             U--S
[download]

Let's say I am trying to find all paths between D and M. I have intentionally made a left hand side and a right hand side so all paths going to the left of D will be invalid because they will require coming back through D to get to M. Now, let's say I first start descending from D -> X and beyond and unwind back to D in failure. Now I go to D -> F -> X. I already determined that paths to X coming from D are bad so I can stop here.

Regarding your initial idea. That is called a bi-directional search and was my first inclination too assuming only the shortest path(s) were desired. Unfortunately, if there is a 3 node solution and a 7 node solution, neversaint wants both.

> Regarding your initial idea. That is called a bi-directional search and was my first inclination too assuming only the shortest path(s) were desired. Unfortunately, if there is a 3 node solution and a 7 node solution, neversaint wants both.

yes but IMHO it's still applicable for "all paths", you just have to test combinations of "half paths" that meet in a node.

IMHO that should already reduce the complexity C(n) of a uni-directional approach to 2*C(n/2) of bi-directional, which means a dramatical speed up!

> Here is an actual example - one that I tested with:

>      L     F       B
>    / | \ /  \    / | \
>   R--J--X----D--Q  P  M
>    \ | /         \ |  |
>      Z             U--S
[download]

The point here is that the (one element) set of edges {(D,Q)} is already a min-cut of the graph which separates start and stop.

Sorry it's been 15 years now since I heard (the basics) of graph theory at uni but IMHO calculating the shortest path should be a good start for identifying cuts.

Cheers Rolf

Hmm what about a three phase approach?

Finding "all paths" by backtracking is so expensive because of the power set of combinations of partial "subpaths"!

That's why nobody is interested to test all combinations in a dead track.

What about identifying the nodes/subpaths which can only be part of a solution in a first phase and later on trying to find all combinations.

Lets say in the first phase we mark each node in your example by the minimal distance from the start. (quite a trivial iterative algorithm of low complexity (IMHO O(n)), I already realized it)

   2    1        B2
 / | \ /  \    / | \
3--2--1---D0--Q1 P3 M*
 \ | /         \ |  |
   2             U2-S3
[download]

In the second phase we have to find all "short" paths by "stepping" down from M simply by always choosing a neighbour of lower degree.

I.e. M-B-Q-D or M-S-U-Q-D.

That means this left branch you wanted to avoid won't be visited again and will not cause any notable complexity.

Now finding "all" paths in a third phase could be done by combining "detours" to the shortest path. e.g. M-B-(P-U)-Q-D.

The latter is rather tricky, alternatively one could also simply try a brute force backtracker like already demonstrated, but much faster because it's restricted to step only thru nodes marked in phase 2!

Cheers Rolf

UPDATE: After some thoughts I have to admit that the process to identify "unreachable" parts of the graph as result of phase 2 is more complicated ... too complicated for a simple post, coz I really can't think of any reasonable application of calculating all(!) paths instead of just only the shortest.

Limbic~Region

> Now, let's say I first start descending from D -> X and beyond and unwind back to D in failure. Now I go to D -> F -> X. I already determined that paths to X coming from D are bad so I can stop here.

   L     F       B
 / | \ /  \    / | \
R--J--X----D--Q  P  M
 \ | /         \ |  |
   Z             U--S
[download]

I haven't investigated the "short circuit" heuristics you've implemented so far, but it's certainly not trivial.

Let the following show a search for paths from 0 to * and the numbers denote the first steps taken in a DFS.

  3
 / \
0   2
 \ / \
  1---4
  |
  *
[download]

Now avoiding edges or nodes "failuring" after passing 2 would hinder you finding 0->3->2->4->1->* after unwinding to 0.

IMHO you need a mechanism to detect loops ("cycles") to "earlier" nodes in your actual search path before cutting of a branch of the graph which isn't trivial for DFS, I'd rather prefer BFS.

But this involves already more mathematical proofs than most of our fellow monks are likely to tolerate.

Which brings me back to the suspicion that we are trying to launch a rocket, while the OP most likely needs a tutorial about how to throw stones!

As long as he isn't capable/willing to correctly express his needs it doesn't make much sense continuing! :(

HTH!

Cheers Rolf

LanX,
You are correct, I fail to find a valid path due to erroneous short circuiting. I, as well as others, have already provided neversaint with a working solution. This is more just a knowledge thing for me. Even if I were to "fix" the solution I don't believe it would be any quicker as a general solution. Moving to a BFS brings its own baggage (memory can become a problem). Oh well, at least I know one way that doesn't work :-)

Cheers - L~R