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