Prev Up Next
Go backward to 9/28/2001   Algorithm Concepts for Standard Libraries
Go up to News Archive
Go forward to 9/21/2001   BGL Tutorial Sheds Light on How Generic Algorithms Are Designed

9/25/2001   How BGL Provides Generic Breadth First Search and Depth First Search Algorithms

 AP Wire Service
The actual code implementing generic breadth first search and depth first search algorithms in BGL is the most advanced example of generic algorithm design we've seen to date. Looking at the code in boost_1_24_0/boost/graph/depth_first_search.hpp, for example, we see how many of the abstract concepts and C++ techniques we've talked about come together. (There are also some hairy details--about named parameters and work-arounds for deficiencies of certain compilers--that partially obscure the main ideas and need not concern us at this point. The discussion of these algorithms in Chapter 4 of the BGL book properly ignores some of these details.) Chapter 8 of Accelerated C++ also talks about how generic algorithms are designed, at a more elementary level with examples from STL, with particular emphasis on the iterator concepts (called iterator categories there) that provide the interface between generic algorithms and containers. For a good test of your understanding of this material, try Exercises 8-3, 8-4, 8-6, 8-7, and 8-8 (not to turn in).

 

Prev Up Next