Re: [Boost-users] [BGL] SPPRC variant

Subject: Re: [Boost-users] [BGL] SPPRC variant
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-08-04 16:04:09

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