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.

State

Nodes

Edges

AK 69082 78100
AL 566843 661487
AR 483175 563036
AZ 545111 665827
CA 1613325 1989149
CO 448253 539295
CT 153011 187318
DC 9559 14909
DE 49109 60512
FL 1048506 1330551

State

Nodes

Edges

GA 738879 869890
HI 64892 76809
IA 390002 502269
ID 271450 318761
IL 793336 1012817
IN 497458 629750
KS 474015 607391
KY 467967 525995
LA 413574 499254
MA 308401 385164

State

Nodes

Edges

MD 265912 317624
ME 194505 214921
MI 673534 845087
MN 547028 670443
MO 675407 807892
MS 413250 483306
MT 317905 360936
NC 887630 1009846
ND 210801 260902
NE 308157 392008

State

Nodes

Edges

NH 116920 133415
NJ 330386 436036
NM 467529 567084
NV 261155 311043
NY 716215 897451
OH 676058 842872
OK 540981 664215
OR 536236 628167
PA 874843 1088296
RI 53658 69213

State

Nodes

Edges

SC 463652 553599
SD 212313 259622
TN 583484 676080
TX 2073870 2584159
UT 248730 295763
VA 630639 714809
VT 97975 107558
WA 575860 675049
WI 519157 635436
WV 300146 328858
WY 253077 304014

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.


Based on a page written by Dominik Schultes - Layout revised by Camil Demetrescu
Last revised on February 19, 2006