| Graph algorithms typically need great flexibility in traversing and visiting vertices and edges of a graph. BGL, the Boost Graph Library developed at the University of Notre Dame, achieves the requisite flexibility through advanced generic programming techniques, including provision for several kinds of iteration through vertices, edges, adjacent vertices, etc. It also provides for selectively applying several different operations on each visited vertex or edge, as is commonly needed in graph algorithms, via a novel Visitor Concept that extends the Function Object Concept of STL. The main Web site for BGL contains tutorials and reference documentation and permits downloading of the code (header files and test programs) and html documentation. Some of the main links that may be examined in upcoming lectures include A Quick Tour of the Boost Graph Library, the adjacency_list class template, and Visitor Concepts. These links contain material similar, but not identical, to material in the BGL textbook. Some of the class discussion will focus on a few of the many small example programs in the libs/graph/example/ subdirectory of the Boost libraries distribution. Some acquaintance with elementary graph theory will be assumed; see Section 1.1 of the BGL textbook and Review of Elementary Graph Theory; or, for a more thorough treatment, the Cormen, Leiserson, and Rivest textbook. [Added 9/13/2001: The files used interactively in class: quick_tour0.cpp (original version), quick_tour1.cpp (modified version), Makefile.] |