Re: [boost] [BGL] Why not bf and df iterators (graphs vs trees)?

From: me22 (me22.ca_at_[hidden])
Date: 2006-06-23 15:37:28

On 6/23/06, nicola <vitacolo_at_[hidden]> wrote:
> One design choice in the BGL is that there are "visitor" functions, e.g.
> breadth_first_search() and depth_first_search(), but there are no
> "bfs_iterator" or "dfs_iterator". What are the motivations that lead to
> such choice? Might they be applied to trees as well?
>
My guess for that would be that iterators are intended to be cheap to
copy but duplicating the stacks, queues, or sets of visited/pending
nodes would be very expensive.

It might be possible to take advantage of the special characteristics
of trees to solve this, however.  I think a dfs_iterator shouldn't be
that different to implement from the usual iterators, since an
in-order iterator already walks the tree in a way similar to DFS, just
skipping nodes at different times.

~ Scott McMurray