Boost Users :
From: David Abrahams (dave_at_[hidden])
Date: 2008-06-27 02:23:34
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.
> On Fri, Jun 27, 2008 at 11:38 AM, David Abrahams <dave_at_[hidden]> wrote:
>> diojenez wrote:
>>> 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
>> and the reference to time_stamper, which is at
>> 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.
>> Dave Abrahams
>> BoostPro Computing
>> Boost-users mailing list
> Boost-users mailing list
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net