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