Re^4: Short Circuiting DFS Graph Traversal

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

Comment on Re^4: Short Circuiting DFS Graph Traversal

Replies are listed 'Best First'.
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]

Replies are listed 'Best First'.

Re^5: Short Circuiting DFS Graph Traversal
by LanX (Saint) on Nov 01, 2010 at 16:12 UTC

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]