Boost logo

Boost Users :

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

-- Jeremiah Willcock

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at