Menu
CTAN
Comprehensive TeX Archive Network
Home Upload Browse

Direc­tory tex-archive/support/graphbase

The Stanford GraphBase is copyright 1992 by Stanford University

These files may be freely copied and distributed, provided that
no changes whatsoever are made. All users are asked to help keep
the Stanford GraphBase sources consistent and ``uncorrupted,''
identical everywhere in the world. Changes are permissible only
if the changed file is given a new name, different from the names of
existing files listed below, and only if the changed file is
clearly identified as not being part of the Stanford GraphBase.
The author has tried his best to produce correct and useful programs,
in order to help promote computer science research, but no warranty
of any kind should be assumed.

FILES INCLUDED IN STANDARD GRAPHBASE DISTRIBUTION

The standard Stanford GraphBase consists of the following files:

1) Data files
      anna.dat     Anna Karenina (used by gb_books)
      david.dat    David Copperfield (used by gb_books)
      econ.dat     US economic input and output (used by gb_econ)
      games.dat    College football scores, 1990 (used by gb_games)
      homer.dat    The Iliad (used by gb_books)
      huck.dat     Huckleberry Finn (used by gb_books)
      jean.dat     Les Miserables (used by gb_books)
      miles.dat    Mileage between North American cities (used by gb_miles)
      mona.dat     Mona Lisa pixels (used by gb_mona)
      roget.dat    Cross references in Roget's Thesaurus (used by gb_roget)
      words.dat    Five-letter words of English (used by (gb_words)
2) CWEB program files
  a) Kernel routines
      gb_flip.w    System-independent random number generator
      gb_graph.w   Data structures for graphs
      gb_io.w      Input/output routines
      gb_sort.w    Sorting routine for linked lists
  b) Graph generating routines
      gb_basic.w   Standard building blocks and graph operations
      gb_books.w   Graphs based on world literature
      gb_econ.w    Graphs based on US inter-industry flow
      gb_games.w   Graphs based on college football games
      gb_gates.w   Graphs based on combinational logic
      gb_miles.w   Graphs based on highway distances
      gb_mona.w    Graphs based on Leonardo's Mona Lisa
      gb_plane.w   Planar graphs
      gb_raman.w   Ramanujan graphs (expanders)
      gb_rand.w    Random graphs
      gb_roget.w   Graphs based on Roget's Thesaurus
      gb_words.w   Graphs based on 5-letter words of English
   c) Demonstration routines
      assign_mona.w      The assignment problem, using Mona Lisa
      book_components.w  Biconnected components, using the plots of books
      econ_order.w       Heuristic solution to an optimum permutation problem
      football.w         Heuristic solution to a longest-path problem
      girth.w            Empirical study of Ramanujan graphs
      ladders.w          Shortest paths in word graphs
      miles_span.w       Comparison of algorithms for minimum spanning tree
      multiply.w         Using a parallel multiplication circuit
      queen.w            Graphs based on queen moves
      roget_components.w Strong components of a directed graph
      take_risc.w        Using a simple RISC computer circuit
      word_components.w  Connected components of word graphs
   d) Miscellaneous routines
      boilerplate.w      Legalese incorporated into all GraphBase programs
      gb_dijk.w          Variants of Dijkstra's algorithm for shortest paths
      gb_save.w          Converting graphs to ASCII files and vice versa
      test_sample.w      Test routine for GraphBase installation
3) Miscellaneous files
      Makefile           Instructions to build everything with UNIX
      README             What you're now reading
      abstract.plaintex  Short explanation of what it's all about
      cities.texmap      TeXable map of the 128 cities in miles.dat
      queen_wrap.ch      Demonstration changefile
      sample.correct     Correct primary output of test_sample
      test.correct       Correct secondary output of test_sample
      test.dat           Weird data used to test gb_io

TO INSTALL THESE PROGRAMS

First install CWEB (version 2.4 or greater), which can be found in
various archives; the master files reside at labrea.stanford.edu.
Then, on a UNIX-like system, edit the Makefile as instructed there,
and "make install".

Complete instructions will appear in a book by D. E. Knuth entitled
  The Stanford GraphBase: A Platform for Combinatorial Algorithms.

Note: The system is presently in alpha-test state, meaning that everything
appears to work on at least one system; but experience on a broad range
of computers is lacking. Please communicate all suggested improvements to
winkler@sunburn.stanford.edu, with subject line "GraphBase Alpha Test".

Files

Name Size Date Notes
Makefile 3359 1992-07-05 02:00:00
README 4705 1992-07-05 02:00:00
abstract.pdf 57807 2007-12-06 12:56:00
abstract.plaintex 12042 1992-07-05 02:00:00
anna.dat 9860 1992-07-05 02:00:00
assign_mona.w 29800 1992-07-05 02:00:00
boilerplate.w 1821 1992-07-05 02:00:00
book_components.w 22409 1992-07-05 02:00:00
cities.texmap 6172 1992-07-05 02:00:00
david.dat 6717 1992-07-05 02:00:00
econ.dat 21749 1992-07-05 02:00:00
econ_order.w 11504 1992-07-05 02:00:00
football.w 25577 1992-07-05 02:00:00
games.dat 14296 1992-07-05 02:00:00
gb_basic.w 98658 1992-07-05 02:00:00
gb_books.w 23546 1992-07-05 02:00:00
gb_dijk.w 16582 1992-07-05 02:00:00
gb_econ.w 27934 1992-07-05 02:00:00
gb_flip.w 10840 1992-07-05 02:00:00
gb_games.w 19601 1992-07-05 02:00:00
gb_gates.w 76781 1992-07-05 02:00:00
gb_graph.w 36137 1992-07-05 02:00:00
gb_io.w 21174 1992-07-05 02:00:00
gb_miles.w 16551 1992-07-05 02:00:00
gb_mona.w 26783 1992-07-05 02:00:00
gb_plane.w 39494 1992-07-05 02:00:00
gb_raman.w 31192 1992-07-05 02:00:00
gb_rand.w 23457 1992-07-05 02:00:00
gb_roget.w 8993 1992-07-05 02:00:00
gb_save.w 33048 1992-07-05 02:00:00
gb_sort.w 7440 1992-07-05 02:00:00
gb_words.w 21894 1992-07-05 02:00:00
girth.w 13326 1992-07-05 02:00:00
homer.dat 29960 1992-07-05 02:00:00
huck.dat 4219 1992-07-05 02:00:00
jean.dat 8469 1992-07-05 02:00:00
ladders.w 15693 1992-07-05 02:00:00
miles.dat 41568 1992-07-05 02:00:00
miles_span.w 66410 1992-07-05 02:00:00
mona.dat 184237 1992-07-05 02:00:00
multiply.w 10413 1992-07-05 02:00:00
queen.w 2107 1992-07-05 02:00:00
queen_wrap.ch 4393 1992-07-05 02:00:00
roget.dat 33116 1992-07-05 02:00:00
roget_components.w 17332 1992-07-05 02:00:00
sample.correct 3939 1992-07-05 02:00:00
take_risc.w 6808 1992-07-05 02:00:00
test.correct 837 1992-07-05 02:00:00
test.dat 389 1992-07-05 02:00:00
test_sample.w 10028 1992-07-05 02:00:00
word_components.w 4622 1992-07-05 02:00:00
words.dat 70211 1992-07-05 02:00:00

Down­load the con­tents of this pack­age in one zip archive (513.8k).

GraphBase – A plat­form for com­bi­na­to­rial al­go­rithms

A cweb pro­gram de­vel­oped (pre­sum­ably) in pur­suit of work on ‘The Art of Com­puter Pro­gram­ming’.

Doc­u­men­ta­tion
Li­censeKnuth Li­cense
Main­tainerDon­ald E. Knuth
Topics graph­ics gen­er­a­tor whose out­put is good for use with TeX
Guest Book Sitemap Contact 2014-04-24 13:05 CEST