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.

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.

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

Goals | Papers | Competition | Photos | Organizers | File formats | Download | Workshop | Mailing list | Links