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

Alex Dow wrote:

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.

I'm afraid I don't. I suggest you ask on the list.

Thanks, Alex

On Fri, Jun 27, 2008 at 11:38 AM, David Abrahams 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

diojenez wrote: 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

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