[Boost-users] [BGL] SPPRC variant

Subject: [Boost-users] [BGL] SPPRC variant
From: Adam Spargo (aws_at_[hidden])
Date: 2010-08-04 09:20:05

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_at_[hidden]
Wellcome Trust Sanger Institute   Tel: [phone] x7728
Hinxton, Cambridge CB10 1SA       Fax: [phone]
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_at_[hidden]
> 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.