Reading, MA: Addison-Wesley Publishing Company. vii, 576 p. (1994).
The Stanford GraphBase: A Platform for Combinatorial Computing is a book that is entertaining and instructive. It is partly a book about programming style and partly a book about combinatorial algorithms. Its use of some sophisticated algorithms will appeal to many theoreticians; and its constant theme that “Good programs are good literature” makes it of interest and importance to all computer scientists.
The GraphBase is built in the CWEB programming environment. It adds a library of CWEB programs and an extensive set of data, such as the graph of five letter English words with adjacency defined as differing in a single position; a graph of distances between American cities; graphs of relationships among characters in novels; and the like. It contains an extensive set of graph generators.
While its primary goal is not to treat all combinatorial algorithms, it deals with a large number of interesting ones: shortest paths, spanning trees, matching, strongly connected components and biconnected components, and De Launey triangulations are a few examples. It also treats basic combinatorial generation algorithms for partitions, combinations and permutations. In fact, second and third readings turn up more and more interesting algorithms and data structures.
I believe that the primary contribution of this book is to promote a certain style. Knuth interweaves clever program design, clear documentation, sophisticated algorithms, powerful data structures, and interesting applications – and he succeeds in making it fun.
Chapter 1 (Overview) describes the main modules of the GraphBase, and Chapter 2 (Technicalities) gives more detailed information about the problems addressed. Chapter 3 (Installation and Use) gives an introduction to CWEB and step-by-step instructions for its use and the installation of GraphBase.
The majority of the book is the actual code for the GraphBase. True to the author’s promise, the code is readable with ordinary effort. It is chock full of good ideas, and provides numerous useful techniques. The appendices then give some technical information.
This is not a conventional book about programming or about combinatorial algorithms. In Knuth’s presentation, both are shown by example. Consequently, it is a very valuable addition to the literature on both subjects.