Re^3: Short Circuiting DFS Graph Traversal

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

Comment on Re^3: Short Circuiting DFS Graph Traversal Select or Download Code

Replies are listed 'Best First'.
Re^4: Short Circuiting DFS Graph Traversal by Limbic~Region (Chancellor) on Nov 01, 2010 at 15:47 UTC
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	[reply]
Re^5: Short Circuiting DFS Graph Traversal by LanX (Saint) on Nov 01, 2010 at 16:12 UTC
After some observation I think neversaint want's to find possible combinations DNA-snippets. That naturally means an upper bound for the length of the DNA, nobody expects a string reaching to the moon. Making the problem much easier to handle with a weighted graph, if he was able to express his task! Theoretically speaking: IMHO a really good solution would imply to analyze and (de)compose combinations of graphs. eg: `Subgraph X \ / 0 - N4 - a - b - N4 - ` [download] all paths from 0 to will be P(0->a) x P(a->b) x P(b->*), i.e. combinations of paths thru N4 times paths from a to b thru Subgraph X times N4.š As already sketched a BFS should be able to handle your "short-circuit problem" by assigning a simple distance degree to each vertex at a first phase. No big memory problem... Cheers Rolf 1) IMHO it's not unlikely that DNA-snippets could be clustered in different groups...	[reply] [d/l]