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