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