
Boost Users : 
Subject: Re: [Boostusers] BGL: interrupting breadth_first_search() at a certain distance/predicate?
From: Louis Lavery (Louis_at_[hidden])
Date: 20100804 01:49:14
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 exceptionthrowing
> visitor or my own depthlimited 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 computeraidedmanufacturing toolpath calculation I am
> producing planar graphs like this:
> http://tinyurl.com/377lvt8
> red edges go in the Xdirection, blue edges in the Ydirection.
> 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 donutshaped 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.
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net