On Jun 23, 2006, at 3:37 PM, me22 wrote:
On 6/23/06, nicola <vitacolo@dimi.uniud.it> 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