Prev Up Next
Go backward to 9/25/2001   How BGL Provides Generic Breadth First Search and Depth First Search Algorithms
Go up to News Archive
Go forward to 9/18/2001   BGL Illustrates Generic Programming and C++ Issues

9/21/2001   BGL Tutorial Sheds Light on How Generic Algorithms Are Designed

 AP Wire Service
Generic software component design typically starts with algorithms, focussing on what they require for efficient execution. One looks first at non-generic solutions to similar algorithmic problems, to try to see commonalities. Chapter 3 of the BGL book starts this way, with examples of topological sorting and cycle detection, both of which are expressed in terms of a depth first search of a graph. In generalizing these solutions towards a generic depth first search algorithm, the authors show how a Visitor concept allows the generic algorithm to be parameterized so that it can be easily instantiated with appropriate visitors to obtain topological sorting and cycle detection as special cases. Code discussed in class:
  • topo_sort3.cpp, complete program from BGL book, section 3.3, augmented by code to output the input and trace the algorithm.
  • topo_sort4.cpp. This version (discussed first in class), differs from the above in the way the output is stored in the vector: it uses vector push_back operations and reverse, rather than pointer operations on the vector (which are trickier to program and aren't legal according to the C++ standard anyway).
  • Makefile
  • Added 9/27/2001: makefile-dependencies.dat, an input data file used in creating the test graph.
  • Added 9/27/2001, updated 10/9/2001: makefile-target-names.dat, another input data file used to obtain string names of vertices for output.
Recommended exercises (not to turn in): construct a complete program containing the cycle-detection code in section 3.4. Do the same for the generalized depth first search algorithm in section 3.5.


 

Prev Up Next