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 ... Yes, the path should be simple.
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.
Thanks, I will implement a simple example and try to build up to the real problem. Best, Adam. -- The Wellcome Trust Sanger Institute is operated by Genome Research Limited, a charity registered in England with number 1021457 and a company registered in England with number 2742969, whose registered office is 215 Euston Road, London, NW1 2BE.