Re: [Boost-users] BGL: interrupting breadth_first_search() at a certain distance/predicate?

Subject: Re: [Boost-users] BGL: interrupting breadth_first_search() at a certain distance/predicate?
From: Louis Lavery (Louis_at_[hidden])
Date: 2010-08-04 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 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.