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: Anders Wallin (anders.e.e.wallin_at_[hidden])
Date: 2010-08-03 12:51:19

> 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?

AW