[BGL] Why not bf and df iterators (graphs vs trees)?
Hi all, the following is just a curiosity of mine, about which I would like to get some comment. On browsing a few discussions about generic tree libraries, I got the impression that many people judge that pre-/in-/post-order iterators, and alike, are essential in any tree class or container (concept). My opinion is that a generic tree class (I refrain from calling it a "container", because in my mind a tree does not necessarily model a Container concept) should be designed much more after the BGL than after the STL containers. 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? As a simple example in favor of the former approach, a "BGL-like" tree data structure would allow a user to use a std::vector as a heap (by overloading the suitable functions). I know that for the SoC several tree libraries have been proposed. Is there no room or interest for other proposals any longer? Is it possible to take a look at those proposals? Regards Nicola
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. 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
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
participants (3)
-
Doug Gregor -
me22 -
nicola