Data Sources

It is often important to have interesting data to feed your algorithms, to serve as test data to ensure correctness or to compare different algorithms for raw speed.

Finding good test data can be surprisingly difficult. Here are some pointers:

• Combinatorica graphs - A modest collection of graphs is available from the Combinatorica ftp site. Particularly interesting are the 190 graphs of Graffiti [Faj87], a program that formulated conjectures in graph theory by studying the properties of these graphs. See Section for more information on Combinatorica.  
• TSPLIB - This well-respected library of test instances for the traveling salesman problem is available from Netlib (see Section ) and by anonymous ftp from softlib.cs.rice.edu. TSPLIB instances are large, real-world graphs, derived from applications such as circuit boards and networks.  
• Stanford GraphBase - Discussed in Section , this suite of programs by Knuth provides portable generators for a wide variety of graphs. These include graphs arising from distance matrices, arts, and literature, as well as graphs of more theoretical interest.
• DIMACS Challenge data - A series of DIMACS Challenge workshops have focused on evaluating algorithm implementations of graph, logic, and data structure problems. Instance generators for each problem have been developed, with the focus on constructing difficult or representative test data. The products of the DIMACS Challenges are available from http://dimacs.rutgers.edu/.  
• Algorithm Repository - The Algorithm Repository WWW site, http://www.cs.sunysb.edu/ algorith  (and enclosed CD-ROM) contain data sources for a few of the implementation challenge exercises. In particular, we provide an airline routes data set, and a collection of names labeled by ethnicity.