9th DIMACS Implementation Challenge: Shortest Paths (original) (raw)

Challenge benchmarks
Contributions by Challenge participants

Unless otherwise stated, the files available at this page contain data/software in the public domain and can be freely downloaded.

We have prepared a suite of benchmarks for the Challenge that includes synthetic input generators, real-world inputs, shortest path solvers, scripts for generating benchmark performance reports, and detailed documentation. The platform includes selected contributions by Challenge participants. For feeback, bug reports or comments please send mail to or Download the Challenge 9 benchmarks - vs. 1.1 [ch9-1.1.tar.gz, 372 KB] View README file The following table lists the 12 USA road networks that are part of the challenge core instances. Each graph comes in two versions: physical distance and transit time arc lengths. The node coordinates file is the same. For space reasons, this collection is not included in the experimental package, but it can be downloaded by the installer script. Known issues: the data has numerous errors, in particular gaps in major highways and bridges. This may result in routes that are very different from real-life ones. One should take this into consideration when experimenting with the data. chronograph
Name Description # nodes # arcs Longitude Latitude Distance graph Travel time graph Coordinates
USA Full USA 23,947,347 58,333,344 - - gr.gz file, 335 MB gr.gz file, 342 MB co.gz file, 218 MB
CTR Central USA 14,081,816 34,292,496 [25.0; 50.0] [79.0; 100.0] gr.gz file, 195 MB gr.gz file, 198 MB co.gz file, 139 MB
W Western USA 6,262,104 15,248,146 [27.0; 50.0] [100.0; 130.0] gr.gz file, 86 MB gr.gz file, 88 MB co.gz file, 57 MB
E Eastern USA 3,598,623 8,778,114 [24.0; 50.0] [-infty; 79.0] gr.gz file, 49 MB gr.gz file, 50 MB co.gz file, 32 MB
LKS Great Lakes 2,758,119 6,885,658 [41.0; 50.0] [74.0; 93.0] gr.gz file, 38 MB gr.gz file, 39 MB co.gz file, 24 MB
CAL California and Nevada 1,890,815 4,657,742 [32.5; 42.0] [114.0; 125.0] gr.gz file, 26 MB gr.gz file, 26 MB co.gz file, 16 MB
NE Northeast USA 1,524,453 3,897,636 [39.5, 43.0] [-infty; 76.0] gr.gz file, 21 MB gr.gz file, 21 MB co.gz file, 13 MB
NW Northwest USA 1,207,945 2,840,208 [42.0; 50.0] [116.0; 126.0] gr.gz file, 15 MB gr.gz file, 16 MB co.gz file, 11 MB
FLA Florida 1,070,376 2,712,798 [24.0; 31.0] [79; 87.5] gr.gz file, 14 MB gr.gz file, 14 MB co.gz file, 8.6 MB
COL Colorado 435,666 1,057,066 [37.0; 41.0] [102.0; 109.0] gr.gz file, 5.5 MB gr.gz file, 5.6 MB co.gz file, 3.8 MB
BAY San Francisco Bay Area 321,270 800,172 [37.0; 39.0] [121; 123] gr.gz file, 3.9 MB gr.gz file, 4.0 MB co.gz file, 2.5 MB
NY New York City 264,346 733,846 [40.3; 41.3] [73.5; 74.5] gr.gz file, 3.5 MB gr.gz file, 3.6 MB co.gz file, 2.0 MB

Contributions by Challenge participants

Instances, generators, and tools contributed by Challenge participants are listed below. The format used by real-world files and synthetic generators contributed by participants may differ from the standard Challenge 9 file format and may require additional translators. Available translators are listed in the 'Translator' column in the tables below. Missing translators will be added with the help of volunteers.

Collection Description Data source Contributors Date Translator
Rome99 Large portion of the directed road network of the city of Rome, Italy, from 1999. The graph contains 3353 vertices and 8870 edges. Vertices correspond to intersections between roads and edges correspond to roads or road segments. The file is given in the standard Challenge 9 format. University of Rome "La Sapienza" Gianni Storchi, Paolo Dell'Olmo, Monica Gentili March 2006 not required
PTV Europe Road networks of 17 european countries: aut, bel, che, cze, deu, dnk, esp, fin, fra, gbr, irl, ita, lux, nld, nor, prt, swe (~19 million nodes, ~23 million edges). Data available to Challenge Participants subject to signing a License Agreement. PTV company, Karlsruhe Dorothea Wagner, Algorithmics Group - Universität Karlsruhe Germany December 2005 not available
TIGER/Line The (undirected) road networks of the 50 US States and the District of Columbia. Text files contain node coordinates, edge lengths, travel time, and road category. The package contains tools for merging files. Merging all files yields a graph with about 24 million nodes and 29 million edges. U.S. Census Bureau, Washington, DC Peter Sanders and Dominik Schultes, ITI Algorithmics II - Universität Karlsruhe Germany October 2005 available
Generators Description Contributors Date Translator
EM-BFS Graph generator tools for external memory BFS algorithms. The generators produce files in the standard Challenge 9 format. Deepak Ajwani, Roman Dementiev, Ulrich Meyer April 2006 not required
GTgraph A suite of three synthetic graph generators: 1) SSCA2: generates graphs used as input instances for the DARPA High Productivity Computing Systems SSCA#2 graph theory benchmark. 2) Scale-free: generates graphs power-law degree distributions and small-world characteristics. 3) Generates random graphs. The generators produce files in the standard Challenge 9 format. Kamesh Madduri and David A. Bader, College of Computing - Georgia Institute of Technology February 2006 not required
Randgraph Command line tools generating various families of random graphs (e.g, bullseye, hierarchical) in a simple text format. Seth Pettie, Algorithms and Complexity Group - Max Planck Institut für Informatik and Vijaya Ramachandran, Department of Computer Sciences - The University of Texas at Austin February 2006 not available
Gengraph Command line tools generating graphs in the GraphML format, along with a Postscript converter for visualisation. Dorothea Wagner, Algorithmics Group - Universität Karlsruhe Germany December 2005 not available