The Stanford GraphBase is a collection of programs and datasets which generate and manipulate graphs and networks. This package is the work of Donald Knuth at Stanford University, and the most recent version of this software is always available by anonymous ftp from the Computer Science Department at Stanford (see previous page for link information).

The programs themselves are written in **CWEB**, which is
a mix of the C programming language and Knuth's **TEX**
typesetting language. To install and use this package, therefore, it is
necessary to first download and install **CWEB** on your
system. We have made **CWEB** and the GraphBase available
on this site, as well as providing links to the original sites.

Files in GraphBase which have the **.dat** extension are
data files, including dictionary-type data, map distance data, data for
reconstructing the painting of the Mona Lisa, football score data, and so
on. Much of the emphasis in the example GraphBase programs is on novel
uses for graphs (for instance constructing word ladders: "flour - floor -
flood - blood - brood - broad - bread"), while implementing efficient
algorithmic methods to manipulate graphs and networks in general.

The text *The Stanford GraphBase: A Platform for Combinatorial
Computing* is available from Addison-Wesley Publishing Company (ISBN
0-201-54275-7), and is a helpful overview of the system. This book shows
the recreational approach of the author to the field of algorithms while
providing a useful GraphBase reference.

Generating Graphs (10) |
Minimum Spanning Tree (7) |
Feedback Edge/Vertex Set (5) |

Generating Partitions (5) |
Graph Data Structures (5) |
Hamiltonian Cycle (5) |

Connected Components (4) |
Generating Permutations (4) |
Matching (4) |

Random Number Generation (4) |
Cryptography (3) |
Edge and Vertex Connectivity (3) |

Topological Sorting (3) |
Priority Queues (2) |
Shortest Path (2) |

Voronoi Diagrams (2) |

This page last modified on 2008-07-10 . www.algorist.com