Re: search overlap paths

I'd put the pairs into a hash of arrays with start as key and end as values and then I'll search with a backtracking algorithm hopping from start to start.

Best algorithm depends on many factors you didn't explained.

motivation
data size (speed matters?)
data source (unique starts?)

FWIW: I'm pretty sure this can be solved with one of the graph modules.

And last but not least: what did you try so far? (we are not to keen doing other peoples homework)

Cheers Rolf

(addicted to the Perl Programming Language)

Comment on Re: search overlap paths

Replies are listed 'Best First'.
Re^2: search overlap paths by Anonymous Monk on Jun 13, 2014 at 02:26 UTC
Hi Rolf. I tried putting a hash as you suggested. However for some of the paths the starts are the same while the end is different. Also I am new to graphs. Can you maybe direct me to a backtracking algorithm or graph module that will do this trick. I have tried answering your question below. motivation: This is not a homework. I am trying to stitch together alignments from strings. I know the start and end of the positions of the strings that i can recover from my data. And from this I have to generate the full string in the quickest way possible. data size: the data size can vary greatly depending on the size of my input string. data source: The starts are not unique. Even in my example, there are two chunks starting with 0 (0-200) and 90-1800). hope this answers your question	[reply]
Re^3: search overlap paths by LanX (Saint) on Jun 13, 2014 at 06:17 UTC
Sorry I don't seem to understand your question. For instance there is no 1800-2000 link, such that your last two "solutions" don't make much sense to me. I'm only realizing it now because you didn't use any recommended formatting. And since you are posting anonymously, you can't correct it. :( Cheers Rolf (addicted to the Perl Programming Language)	[reply]
Re^4: search overlap paths by Laurent_R (Canon) on Jun 13, 2014 at 07:24 UTC
Yes, there is no 1800-2000 link, but, if I understood the OP correctly, there is an overlapping path (1000-2000) so that the 1800-2000 itinary can be done through this path. I was first thinking of a simple (possibly recursive) tree-walking algorithm, but given the possibility of crossing the 1800-2000 gap using the 1000-2000 link, the right solution is probably quite different.	[reply]