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

Subject: Re: [Boost-users] [BGL] SPPRC formulation
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-09-23 12:19:42

On Thu, 23 Sep 2010, Adam Spargo wrote:

> Hi,
> I would like to use the r_c_shortest_paths algorithm. My constraint is that 
> given pairs of vertices i, j (each i have a single mate j) must have a 
> distance between them which is consistent with a given distribution. I am 
> looking for the path which is most consistent with this distribution. Does 
> anybody have any experience of formulating such a constraint in BGL?

I'm not sure what you mean here.  What exactly does "consistent with this 
distribution" mean?  Is that referring to a probability distribution? 
Are you trying to find a path that maximizes some property of edge labels? 
If so, is the path required to be simple (contain each vertex at most 
once)?

> The second problem is that I am currently modelling the problem with an 
> undirected graph. The edges could be viewed as bi-directional, but only due 
> to the double stranded nature of DNA. Once I have started on a path I just 
> choose the label which is consistent with the direction I am going, but the 
> graph is essentially undirected, you can always go in either direction down 
> an edge. Could an undirected graph be used with this algorithm or must I use 
> a directed graph?

The documentation says that the graph needs to be directed.  However, have 
you tried it with an undirected graph?  I don't see a reason in the 
pseudocode that justifies the directedness requirement.

Note too that there is work going on to rewrite the r_c_shortest_paths 
code to be more generic; that may end up increasing its capabilities 
later.

-- Jeremiah Willcock