Goals
Papers
Competition
Photos
Organizers
File formats
Download
Workshop
Mailing list
Links
9th DIMACS Implementation Challenge - Shortest Paths

Download

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.

Challenge benchmarks

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 <goldberg at microsoft dot com> or <demetres at dis dot uniroma1 dot it>

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


Page maintained by Camil Demetrescu - last revised on June 14, 2010