Hi, Are there any experts on the list that would give me some advice on a shortest path with resource constraints type problem. In brief: I have a graph with tangles. The tangles are due to spurious edges which arise due to repeats in genomes. If the underlying genome didn't have any repeats, then I could just find the Euler path (which would coincide with the Hamilton path) and I'd be done. I have extra data which can be interpretted as the distance between pairs of nodes, which I hope to use to remove as many of the spurious edges as possible, but having read some papers this sounds like the SPPRC. The trouble is that the distances aren't exact, they come from a distribution, which is only approximately known. However my graph will have lots of untangled regions from which I can make a better approximation, iteratively maybe. -- Dr Adam Spargo High Performance Assembly Group email: aws@sanger.ac.uk Wellcome Trust Sanger Institute Tel: +44 (0)1223 834244 x7728 Hinxton, Cambridge CB10 1SA Fax: +44 (0)1223 494919 On Wed, 4 Aug 2010, Louis Lavery wrote:
On 03/08/2010 17:51, Anders Wallin wrote:
I was thinking to reset the filtered graph at every source vertex. Roughly equivalent to keeping track of depth, without having to write the code.
thanks for all replies, I will try writing an exception-throwing visitor or my own depth-limited bfs.
I should probably describe my application, since there might be a much better solution than the one I am trying. As part of a computer-aided-manufacturing toolpath calculation I am producing planar graphs like this: http://tinyurl.com/377lvt8 red edges go in the X-direction, blue edges in the Y-direction. the vertices I am interested in are drawn as blue/red dots(the color does not matter here), and the problem is to find the correct order of these vertices which creates a "silhouette" or "contour" of the graph. A naive solution would just hop from one dot to the closest one, but in more complicated cases this is not correct, so I would prefer traversing the graph to the next dot.
sometimes the graph has many disconnected components: (no colored dots in this pic, and nevermind the white triangulated surface...) http://tinyurl.com/3aefpgn and note that the donut-shaped component of the graph has two of these "loops" I am interested in, one on the outside, one on the inside.
I've been thinking about two approaches: 1) start at one vertex, search in the neighbourhood of this vertex for the next one, figure out which one of the found points is the correct next vertex. iterate. 2) something based on the idea of surface tension, or some kind of relaxation/removal/addition of edges. start in the middle of the graph and work your way towards the outside and when we are finished only the correct edges remain.
any ideas?
Yes.
1. Remove (or filter out) all vtx of deg 1 together with their edges.
2. Mark all vtx of deg < 4 with p.
3. Starting at, and working away from, the p vtxs of deg 2[1], join with the adjacent p vtx.
4. Now any p vtx of pdeg < 2 will be adjacent to a non p vtx that is adjacent to another p vtx of pdeg < 2, make the non p vertex a p vertex and join with the two adjacent p vtxs. (pdeg is the number of adjacent p vtxs, of course).
5. That's it, bar sticking the loose threads back on etc.
No shadow of a proof, so may contain bugs!
Louis.
[1] Looks like you need to move away from the deg 2 vtxs in step, in case you're on a strip 2 vtxs wide, in which case there'll be two adjacent p vtxs you could join with. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- 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.