On Wed, 4 Aug 2010, Adam Spargo wrote:
Hi, Are there any experts on the list that would give me some advice on a shortest path with resource constraints type problem.
In brief: I have a graph with tangles. The tangles are due to spurious edges which arise due to repeats in genomes. If the underlying genome didn't have any repeats, then I could just find the Euler path (which would coincide with the Hamilton path) and I'd be done. I have extra data which can be interpretted as the distance between pairs of nodes, which I hope to use to remove as many of the spurious edges as possible, but having read some papers this sounds like the SPPRC.
The trouble is that the distances aren't exact, they come from a distribution, which is only approximately known. However my graph will have lots of untangled regions from which I can make a better approximation, iteratively maybe.
There is a resource-constrained shortest paths algorithm in BGL, although I have never used it. There is someone working on a newer version, but I don't know about the recent progress of that. Do you have a more precise description of what you are trying to accomplish, especially in graph terms? -- Jeremiah Willcock