Re: [Boost-users] Depth limited search in Boost

From: David Abrahams (dave_at_[hidden])
Date: 2008-06-26 22:38:53

diojenez wrote:
> Hello,
> 
> Is anyone aware of an implementation of depth-limited search
> (http://en.wikipedia.org/wiki/Depth-limited_search) in boost? I don't think
> it is possible to implement with the existing depth_first_search...

Yeah, there's a class of algorithms where the graph (sub-) structure
being traversed can only be discovered with respect to the algorithm's
progress.  BGL doesn't seem to support that class of algorithms very
easily.  However, I'm pretty sure it can be done; here's a sketch:

Take a look at the pseudocode at
http://www.boost.org/doc/libs/1_34_0/libs/graph/doc/depth_first_search.html
and the reference to time_stamper, which is at
http://www.boost.org/doc/libs/1_34_0/libs/graph/doc/time_stamper.html

It should be pretty easy to see how to a different visitor adaptor, sort
of like time_stamper, which increments a depth count when you discover a
vertex and decrements when you finish it.

Then you create a graph adaptor that refers to the depth count, and
returns an empty range for out_edges when the depth reaches your limit.
 This relies on knowing a lot about the structure of the DFS
implementation, but after all, the library documents it, so it should be
OK to take advantage of that.

HTH,

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com