Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net