Re^2: Short Circuiting DFS Graph Traversal

Replies are listed 'Best First'.
Re^3: Short Circuiting DFS Graph Traversal by LanX (Saint) on Oct 29, 2010 at 15:29 UTC
> 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 2C(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	[reply] [d/l]
Re^3: Short Circuiting DFS Graph Traversal by LanX (Saint) on Oct 30, 2010 at 00:09 UTC
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.	[reply] [d/l]
Re^3: Short Circuiting DFS Graph Traversal by LanX (Saint) on Nov 01, 2010 at 13:53 UTC
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	[reply] [d/l] [select]
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]