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