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

From: Alex Dow (alexdow_at_[hidden])
Date: 2008-06-27 01:54:46

Thanks David, that makes sense. I'm a bit of a noob, so I'm not too
comfortable writing my own graph adapters. Do you know of any good
online primers for this? I read "Converting Existing Graphs to BGL"
from the documentation, as well as the docs for several of the
existing graph adapters (subgraph, edge_list), but I'm still not
getting it. Any leads would be helpful.

Thanks,
Alex

On Fri, Jun 27, 2008 at 11:38 AM, David Abrahams <dave_at_[hidden]> wrote:
> 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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>