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

From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-06-27 09:56:55

On Jun 23, 2006, at 3:37 PM, me22 wrote:

> 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.

If the iterators stored a shared_ptr to all of the data needed to  
make the traversal work, the cost of copying the iterators would be  
greatly reduced.

I think BFS/DFS (and Dijkstra, A*, Prim, topological sort, etc)  
iterators would be extremely interesting for the BGL. They better  
support incremental uses of these algorithms, and offer an  
interesting alternative for simple visitors.

        Doug