Goals Papers Competition Schedule Organizers File formats Download Workshop Mailing list Links

9th DIMACS Implementation Challenge - Shortest Paths

United States Road Networks (TIGER/Line)

Assembled by
Dominik Schultes <mail@dominik-schultes.de>
Universität Karlsruhe (TH), Germany
October 2005

Source

UA Census 2000 TIGER/Line Files
U.S. Census Bureau, Washington, DC
Geography Division
Created: May 3, 2002
Last revised: Monday, 18-Nov-2002 10:26:40 EST
http://www.census.gov/geo/www/tiger/tigerua/ua_tgr2k.html

Files

The road networks of the 50 US States and the District of Columbia. Graphs are undirected.

File format

The format of the uncompressed file is very simple. It is a whitespace-separated list of numbers:

	Number of nodes
	For each node:
	id
	longitude
	latitude
	Number of edges
	For each edge:
	id of the source node
	id of the target node
	travel time
	spatial distance in meters
	road category

Notes

	The id is a number between 0 and "number of nodes"-1
	Longitude/latitude are given in the format used in the TIGER/Line files (see technical documentation). Excerpt: Coordinates are decimal degrees expressed in Federal Information Processing Standard (FIPS) notation, where a positive latitude represents the Northern Hemisphere and a negative longitude represents the Western Hemisphere. All coordinates are expressed as a signed integer with six decimal places of precision implied. Actual TIGER/Line file Latitude 15 Deg. S to 72 Deg. N -15000000 to +72000000 Longitude 64 Deg. W to 131 Deg. E -64000000 to -180000000 +179999999 to +131000000
	road category is adopted directly from the TIGER/Line files (refer to the documentation).
	spatial distance in meters is the great circle distance from source to target node
	travel time is the spatial distance divided by some average speed that depends on the road category: Category code Category name Average speed A1 Primary Highway With Limited Access (e.g. interstates) 1.0 A2 Primary Road Without Limited Access (e.g. US highways) 0.8 A3 Secondary and Connecting Road (e.g. state highways) 0.6 A4 Local, Neighborhood, and Rural Road 0.4 Note that the unit of the average speed is somewhat arbitrarily chosen and does not correspond to any usual unit (like km/h or mph).

Merging of two or more files

The C++ program merge can be used to merge the road networks of two or more states. Compile it with g++ -o merge merge.cpp using, for instance, g++ (GCC) 3.3.5.
There are two different ways to use the program:

Merging two files. Three arguments: file1.tmp file2.tmp fileResult.tmp Reads file1.tmp and file2.tmp. Writes fileResult.tmp.

Merging more than two files. One argument: fileResult.tmp Reads a space-separated list of input filenames from standard in. Reads all files on the list. Writes fileResult.tmp. Example: If you have got the tmp files of Connecticut, Maine, Massachusetts, New Hampshire, Rhode Island, and Vermont, you can merge them in order to obtain the road network of New England: echo "CT.tmp ME.tmp MA.tmp NH.tmp RI.tmp VT.tmp" | ./merge NewEngland.tmp

Converting TIGER/Line files into the Standard Challenge 9 Format

TIGER/Line files in the collection can be converted into files in the Standard Challenge 9 Format using the simple Perl script tiger2edimacs.pl. The script can be executed using command:

perl tiger2edimacs.pl [-T] filename1.tmp filename2.tmp ...

For each input file filenameX.tmp in TIGER/Line format, the program creates a file filenameX.gr that stores the graph topology and the arc weights, and a file filenameX.co that stores the node coordinates in the plane. If option -T is given in the command line, then arc weights in the resulting graph are travel times, otherwise they are spatial distances in meters between the endpoints.

Notice: road category information is ignored in the translation.

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