The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

The Stanford GraphBase

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.

  • Download Files (local site)
  • Download CWEB Files
  • Donald E. Knuth's Homepage
  • Download GraphBase Files

    Problem Links

    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 .