On Wed, 29 Sep 2010, Adam Spargo wrote:
Hi, thanks for your reply
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)?
Sorry ... each edge has a length, and pairs of vertices have a distance between them (called the insert size), depending on how well the DNA library is made the insert size of the pairs has a distribution. All we get is the size they were aiming for - we usually assume a normal distribution with this size as mean and s.d. of 20% - but this is completely arbitrary and is often wrong. I was planning to approximate the distribution from parts of my graph without cycles. BUT in the first instance implementing a SPPRC with exact insert size could be seen as progress ...
Is there a description somewhere of what you're trying to do at a high level? I still don't completely understand the actual problem you're trying to solve. Are you just looking for paths that minimize the total vertex distances, or are there more limitations or objectives that you have?
Yes, the path should be simple.
Could you ever have a situation similar to a negative-weight cycle where the "best" overall (not necessarily simple) path is not simple? -- Jeremiah Willcock