next up previous contents index CD CD Algorithms
Next: Combinatorica Up: Software systems Previous: Collected Algorithms of the

The Stanford GraphBase


The Stanford GraphBase is an interesting program for several reasons. First, it was composed as a ``literate program'', meaning that it was written to be read. If anybody's programs deserve to be read, it is Knuth's, and [Knu94] contains the full source code of the system. The programming language/environment is CWEB, which permits the mixing of text and code in particularly expressive ways.

The GraphBase contains implementations of several important combinatorial algorithms, including matching, minimum spanning trees, and Voronoi diagrams, as well as specialized topics like constructing expander graphs and generating combinatorial objects. Finally, it contains programs for several recreational problems, including constructing word ladders (flour-floor-flood-blood-brood-broad-bread) and establishing dominance relations among football teams.        

Although the GraphBase is more fun to play with than LEDA, it is not really suited for building general applications on top of. The GraphBase is perhaps most useful as an instance generator for constructing a wide variety of graphs to serve as test data. It incorporates graphs derived from interactions of characters in famous novels, Roget's thesaurus, the Mona Lisa, and the economy of the United States. Further, because of its machine-independent random number generators, the GraphBase provides a way to construct random graphs that can be reconstructed elsewhere, making them perfect for experimental comparisons of algorithms.     

The Stanford GraphBase can be obtained by anonymous ftp from in the directory pub/sgb. It may be used freely, but the files may not be modified. Installing the GraphBase requires CWEB, which can be obtained by anonymous ftp from in the directory pub/cweb.

GraphBase Implementation

Mon Jun 2 23:33:50 EDT 1997