History of us_roads
The changes to the source code of this entry in the repository, newest first, each with the differences it made to the entry's files. They are also listed on GitLab.
[entries] Lay out the spatial networks with hfd_layout() instead of cfd_layout() cc3bcb0
Changed: none
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index 3c2bf72..0216451 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -350,6 +350,6 @@ def parse_graph(f):
def get_pos(g, sbm_fit):
- # Spatial network: laid out with the default parameters of cfd_layout(),
+ # Spatial network: laid out with the default parameters of hfd_layout(),
# without the partition of the SBM fit
- return cfd_layout(g)
+ return hfd_layout(g)
[entries] Add the date when each entry was added, and remove icon_hash beff7c9
The dates are those of the commits that first added the entries' files (2020-08-11 for the entries of the initial commit); renamed entries keep the date of their first name. Changed: none
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index 5682805..3c2bf72 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -54,7 +54,7 @@ url = ['http://www.dis.uniroma1.it/challenge9/data/tiger/',
'https://www2.census.gov/geo/tiger/']
citation = [('"9th DIMACS Implementation Challenge - Shortest Paths"', 'http://www.dis.uniroma1.it/challenge9/data/tiger/'),
('U.S. Census Bureau, "TIGER/Line Shapefiles: All Lines (EDGES)." Datasets of 2008 to 2026', 'https://www.census.gov/geographies/mapping-files/time-series/geo/tiger-line-file.html')]
-icon_hash = '5723ecbf461efe0c7a675c6e'
+date_added = '2020-08-11'
# the TIGER networks need about 200 GB of downloads (19 annual releases)
huge = True
[entries] Prefix the properties in the descriptions with (Node), (Edge) or (Graph) bc3dbbd
The lists of properties at the end of the descriptions marked edge properties with "Edge" but left node properties unmarked, or grouped them in "Nodes: `a`, ...; `b`, ..." items, so the kind of a property was often unclear. Every item now starts with (Node), (Edge) or (Graph), followed by the property names, a colon and the explanation, one item per property or group of properties; qualifications (kinds of nodes, networks) follow the names in parentheses. Properties that were only named got a short explanation, and a few items that named the wrong kind of property were corrected.
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index b3af999..5682805 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -31,14 +31,23 @@ description = """Road networks of the 50 U.S. states and the District of Columbi
The networks have the following properties:
-- `la`, `lo`: the latitude and longitude of the node, in degrees.
-- `distance`: the length of the road segment, and `travel_time`: the estimated travel time along it, both as given in the DIMACS files (the units are not documented there).
-- `road_category`: the road category, given by the numerical part of the TIGER census feature class code (CFCC) of the road (e.g. 11–18 for primary highways with limited access, 21–28 for primary roads without limited access, 31–38 for secondary and connecting roads, and 41–48 for local, neighborhood and rural roads).
+- (Node) `la`, `lo`: the latitude and longitude of the node, in degrees.
+- (Edge) `distance`, `travel_time`: the length of the road segment and the estimated travel time along it, both as given in the DIMACS files (the units are not documented there).
+- (Edge) `road_category`: the road category, given by the numerical part of the TIGER census feature class code (CFCC) of the road (e.g. 11–18 for primary highways with limited access, 21–28 for primary roads without limited access, 31–38 for secondary and connecting roads, and 41–48 for local, neighborhood and rural roads).
The networks `tiger_2008` to `tiger_2026` are the national road networks of the annual releases of the TIGER/Line Shapefiles of the Census Bureau, from the first one (2008) to the latest one (2026), one network per release, built directly from their "All Lines" (EDGES) files, one per county (about 3,235). These files contain all the linear features of the TIGER database (roads, railroads, hydrography, boundaries, ...) as topological edges between nodes (`TNIDF` and `TNIDT`), with the same node ids across counties; only the road edges (those flagged as roads, with MAF/TIGER feature class codes S1100 to S1830) are included, and an edge is a road segment between two nodes (intersections, ends of roads, and points where the road crosses other linear features, e.g. boundaries or streams). The networks are undirected and cover the 50 states, the District of Columbia, Puerto Rico and the Island Areas; they have parallel edges and self-loops (e.g. roads forming loops). Not included are the house number ranges of the edges, their geometries, and the railroads and hydrography of the EDGES files. These networks have the following properties:
-- Nodes: `tnid`, the TIGER node id; `la` and `lo`, the latitude and longitude of the node (NAD83, in degrees).
-- Edges: `tlid`, the permanent TIGER/Line id of the edge; `name`, the full name of the road (e.g. `Ingomar St NW`; empty if unnamed); `mtfcc`, the MAF/TIGER feature class code (e.g. `S1100` primary road, `S1200` secondary road, `S1400` local neighborhood road, rural road or city street, `S1500` vehicular trail, `S1630` ramp, `S1640` service drive, `S1710` walkway, `S1720` stairway, `S1730` alley, `S1740` private road, `S1750` internal census use, `S1780` parking lot road, `S1820` bike path or trail); `county`, the FIPS code of the state and county; `zip_left` and `zip_right`, the ZIP codes on the two sides of the road; `length`, the length of the edge along its geometry (km); `decked`, whether the road is double-decked; `artificial_path`, whether the edge is an artificial path; in the networks until `tiger_2016` also `divided`, whether the road is divided (a field left out of the later releases)."""
+- (Node) `tnid`: the TIGER node id.
+- (Node) `la` and `lo`: the latitude and longitude of the node (NAD83, in degrees).
+- (Edge) `tlid`: the permanent TIGER/Line id of the edge.
+- (Edge) `name`: the full name of the road (e.g. `Ingomar St NW`; empty if unnamed).
+- (Edge) `mtfcc`: the MAF/TIGER feature class code (e.g. `S1100` primary road, `S1200` secondary road, `S1400` local neighborhood road, rural road or city street, `S1500` vehicular trail, `S1630` ramp, `S1640` service drive, `S1710` walkway, `S1720` stairway, `S1730` alley, `S1740` private road, `S1750` internal census use, `S1780` parking lot road, `S1820` bike path or trail).
+- (Edge) `county`: the FIPS code of the state and county.
+- (Edge) `zip_left`, `zip_right`: the ZIP codes on the two sides of the road.
+- (Edge) `length`: the length of the edge along its geometry (km).
+- (Edge) `decked`: whether the road is double-decked.
+- (Edge) `artificial_path`: whether the edge is an artificial path.
+- (Edge) `divided` (networks until `tiger_2016`): whether the road is divided (a field left out of the later releases)."""
tags = ['Transportation', 'Roads', 'Spatial', 'Unweighted']
url = ['http://www.dis.uniroma1.it/challenge9/data/tiger/',
'https://www.census.gov/geographies/mapping-files/time-series/geo/tiger-line-file.html',
[entries] Remove unneeded code from the entries 2c69f19
Unneeded "global files" statements, unused imports and variables, f-strings without placeholders, duplicate keys in foodweb_little_rock (keeping the order and the values used), and the second definition of get_lines() in twitter_higgs. Nothing changes in the networks or descriptions. Changed: none
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index 858444b..b3af999 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -277,7 +277,6 @@ def parse_tiger(name, y):
#@coerce_props()
@annotate()
def parse(alts=None):
- global files
name = __name__.split(".")[-1]
for fname, alt, fmt in files:
if alts is not None and alt not in alts:
[entries] us_roads: add the national road networks of all TIGER/Line releases since 2008 6a8b589
The entry had only the road networks of the 2000 census of the DIMACS challenge. It now also has the national road networks of the 19 annual releases of the TIGER/Line shapefiles (2008 to 2026), built from their "All Lines" (EDGES) files, one per county, keeping the road edges, with the TIGER node ids and positions. The releases of 2008 and 2009 have a directory per state and county, whose listings give their files. With about 200 GB of downloads, the entry is now huge. Changed: upstream us_roads
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index 83e400d..858444b 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -16,23 +16,39 @@
# You should have received a copy of the GNU Affero General Public License along
# with this program. If not, see <http://www.gnu.org/licenses/>.
+import array
+import re
import shutil
+import sys
+import struct
import subprocess
import tempfile
from .. import *
+import process_entry
-title = "United States roads (2000)"
+title = "United States roads (2000, 2008–2026)"
description = """Road networks of the 50 U.S. states and the District of Columbia, derived from the TIGER/Line files of the U.S. Census Bureau for the 2000 Census. The data were prepared by D. Schultes for the 9th DIMACS Implementation Challenge on shortest paths. Nodes are road intersections and endpoints, and undirected edges are road segments between them. There is one network for each state (named by its two-letter postal code, e.g. `CA`), and the network `merged` combines all states into a single network, as produced by the merging program distributed with the data.
The networks have the following properties:
- `la`, `lo`: the latitude and longitude of the node, in degrees.
- `distance`: the length of the road segment, and `travel_time`: the estimated travel time along it, both as given in the DIMACS files (the units are not documented there).
-- `road_category`: the road category, given by the numerical part of the TIGER census feature class code (CFCC) of the road (e.g. 11–18 for primary highways with limited access, 21–28 for primary roads without limited access, 31–38 for secondary and connecting roads, and 41–48 for local, neighborhood and rural roads)."""
-tags = ['Transportation', 'Roads', 'Unweighted']
-url = 'http://www.dis.uniroma1.it/challenge9/data/tiger/'
-citation = [('"9th DIMACS Implementation Challenge - Shortest Paths"', 'http://www.dis.uniroma1.it/challenge9/data/tiger/')]
+- `road_category`: the road category, given by the numerical part of the TIGER census feature class code (CFCC) of the road (e.g. 11–18 for primary highways with limited access, 21–28 for primary roads without limited access, 31–38 for secondary and connecting roads, and 41–48 for local, neighborhood and rural roads).
+
+The networks `tiger_2008` to `tiger_2026` are the national road networks of the annual releases of the TIGER/Line Shapefiles of the Census Bureau, from the first one (2008) to the latest one (2026), one network per release, built directly from their "All Lines" (EDGES) files, one per county (about 3,235). These files contain all the linear features of the TIGER database (roads, railroads, hydrography, boundaries, ...) as topological edges between nodes (`TNIDF` and `TNIDT`), with the same node ids across counties; only the road edges (those flagged as roads, with MAF/TIGER feature class codes S1100 to S1830) are included, and an edge is a road segment between two nodes (intersections, ends of roads, and points where the road crosses other linear features, e.g. boundaries or streams). The networks are undirected and cover the 50 states, the District of Columbia, Puerto Rico and the Island Areas; they have parallel edges and self-loops (e.g. roads forming loops). Not included are the house number ranges of the edges, their geometries, and the railroads and hydrography of the EDGES files. These networks have the following properties:
+
+- Nodes: `tnid`, the TIGER node id; `la` and `lo`, the latitude and longitude of the node (NAD83, in degrees).
+- Edges: `tlid`, the permanent TIGER/Line id of the edge; `name`, the full name of the road (e.g. `Ingomar St NW`; empty if unnamed); `mtfcc`, the MAF/TIGER feature class code (e.g. `S1100` primary road, `S1200` secondary road, `S1400` local neighborhood road, rural road or city street, `S1500` vehicular trail, `S1630` ramp, `S1640` service drive, `S1710` walkway, `S1720` stairway, `S1730` alley, `S1740` private road, `S1750` internal census use, `S1780` parking lot road, `S1820` bike path or trail); `county`, the FIPS code of the state and county; `zip_left` and `zip_right`, the ZIP codes on the two sides of the road; `length`, the length of the edge along its geometry (km); `decked`, whether the road is double-decked; `artificial_path`, whether the edge is an artificial path; in the networks until `tiger_2016` also `divided`, whether the road is divided (a field left out of the later releases)."""
+tags = ['Transportation', 'Roads', 'Spatial', 'Unweighted']
+url = ['http://www.dis.uniroma1.it/challenge9/data/tiger/',
+ 'https://www.census.gov/geographies/mapping-files/time-series/geo/tiger-line-file.html',
+ 'https://www2.census.gov/geo/tiger/']
+citation = [('"9th DIMACS Implementation Challenge - Shortest Paths"', 'http://www.dis.uniroma1.it/challenge9/data/tiger/'),
+ ('U.S. Census Bureau, "TIGER/Line Shapefiles: All Lines (EDGES)." Datasets of 2008 to 2026', 'https://www.census.gov/geographies/mapping-files/time-series/geo/tiger-line-file.html')]
icon_hash = '5723ecbf461efe0c7a675c6e'
+# the TIGER networks need about 200 GB of downloads (19 annual releases)
+huge = True
+
upstream_prefix = 'http://www.dis.uniroma1.it/challenge9/data/tiger/'
files = [(f'{s}.tmp.gz', f'{s}',None) for s in ["AK", "AL", "AR", "AZ", "CA",
"CO", "CT", "DC", "DE", "FL",
@@ -46,10 +62,216 @@ files = [(f'{s}.tmp.gz', f'{s}',None) for s in ["AK", "AL", "AR", "AZ", "CA",
"VA", "VT", "WA", "WI", "WV",
"WY"]] + \
[("merge.cpp", "merged", None)]
+state_files = files[:-1]
+
+# The road edges of the TIGER/Line "All Lines" (EDGES) shapefiles of the
+# Census Bureau, one zip file per county, for every annual release since the
+# first one (2008). The list of files of each year is taken from the
+# directory listing, which is stored as an upstream file. The releases of
+# 2008 and 2009 have a directory per state, with one per county, instead of
+# a directory per kind of file: their list (the paths of the county files)
+# is made from the listings of the state directories.
+tiger_years = list(range(2008, 2027))
+tiger_nested = (2008, 2009)
+tiger_base = "https://www2.census.gov/geo/tiger/TIGER{}"
+tiger_prefix = tiger_base + "/EDGES"
+
+def tiger_index(y):
+ return (f"tiger{y}_edges_index.txt" if y in tiger_nested else
+ f"tiger{y}_edges_index.html")
+
+files += [((tiger_index(y),), f"tiger_{y}", None) for y in tiger_years]
+
+def tiger_paths(name, y):
+ """The county files of TIGER year `y`, from the stored directory listing,
+ as (directory, file name) pairs (the directory relative to the base of
+ the release)."""
+ with open_upstream_file(name, tiger_index(y), "r") as f:
+ text = f.read()
+ if y in tiger_nested:
+ return sorted(tuple(l.strip().rsplit("/", 1)) for l in text.splitlines()
+ if l.strip())
+ return [("EDGES", z) for z in
+ sorted(set(re.findall(rf"tl_{y}_\d{{5}}_edges\.zip", text)))]
+
+def tiger_files(name, y):
+ "The county files of TIGER year `y`."
+ return [z for d, z in tiger_paths(name, y)]
+
+def list_nested(y):
+ """The paths of the county EDGES files of TIGER year `y` (2008 or 2009),
+ from the listings of the state directories."""
+ base = tiger_base.format(y)
+ states = re.findall(r'href="(\d\d_[A-Z_]+)/"',
+ retry_download(lambda: open_url(f"{base}/").read()).decode())
+ paths = []
+ for state in sorted(set(states)):
+ listing = retry_download(lambda: open_url(f"{base}/{state}/").read()).decode()
+ for county in sorted(set(re.findall(r'href="(\d{5}_[^"/]+)/"', listing))):
+ paths.append(f"{state}/{county}/tl_{y}_{county[:5]}_edges.zip")
+ return paths
def fetch_upstream(force=False):
- return fetch_upstream_files(__name__.split(".")[-1], upstream_prefix, files,
- force)
+ name = __name__.split(".")[-1]
+ fetch_upstream_files(name, upstream_prefix, files[:len(state_files) + 1],
+ force)
+ for y in tiger_years:
+ index = tiger_index(y)
+ if process_entry._check_health:
+ if y in tiger_nested:
+ base = tiger_base.format(y)
+ with open_url(f"{base}/") as r:
+ state = re.findall(r'href="(\d\d_[A-Z_]+)/"', r.read().decode())[0]
+ with open_url(f"{base}/{state}/") as r:
+ county = re.findall(r'href="(\d{5}_[^"/]+)/"', r.read().decode())[0]
+ url = f"{base}/{state}/{county}/tl_{y}_{county[:5]}_edges.zip"
+ else:
+ prefix = tiger_prefix.format(y)
+ with open_url(f"{prefix}/") as r:
+ fnames = re.findall(rf"tl_{y}_\d{{5}}_edges\.zip", r.read().decode())
+ url = f"{prefix}/{fnames[0]}"
+ with open_url(url) as r:
+ r.read(1)
+ continue
+ if force or not upstream_file_exists(name, index):
+ if y in tiger_nested:
+ data = "\n".join(list_nested(y)).encode() + b"\n"
+ else:
+ prefix = tiger_prefix.format(y)
+ data = retry_download(lambda: open_url(f"{prefix}/").read())
+ with open_upstream_file(name, index, "wb") as out:
+ out.write(data)
+ paths = tiger_paths(name, y)
+ if len(paths) < 3000:
+ raise ValueError(f"only {len(paths)} county files listed for {y}")
+ for d, z in paths:
+ fetch_upstream_files(name, f"{tiger_base.format(y)}/{d}",
+ [(z, None, None)], force)
+
+def iter_dbf(f):
+ """Iterate over the records of a dBase (DBF) file, read as a stream, as
+ dicts of strings (stripped); deleted records are None."""
+ head = f.read(32)
+ n, hlen, rlen = struct.unpack("<IHH", head[4:12])
+ rest = f.read(hlen - 32)
+ fields = []
+ pos = 0
+ while rest[pos] != 0x0D:
+ d = rest[pos:pos + 32]
+ fields.append((d[:11].split(b"\0")[0].decode(), d[16]))
+ pos += 32
+ for i in range(n):
+ r = f.read(rlen)
+ if len(r) < rlen:
+ raise ValueError("truncated DBF file")
+ if r[0:1] == b"*":
+ yield None
+ continue
+ p = 1
+ row = {}
+ for fname, l in fields:
+ x = r[p:p + l]
+ try:
+ row[fname] = x.decode("utf8").strip()
+ except UnicodeDecodeError:
+ row[fname] = x.decode("latin1").strip()
+ p += l
+ yield row
+
+def iter_shp_lines(f):
+ """Iterate over the records of a shapefile of lines, read as a stream,
+ yielding the first and last points (longitude, latitude) and the length
+ along the great circles (km) of each."""
+ f.read(100)
+ while True:
+ h = f.read(8)
+ if len(h) < 8:
+ return
+ n, length = struct.unpack(">ii", h)
+ c = f.read(2 * length)
+ stype = struct.unpack("<i", c[:4])[0]
+ if stype == 0:
+ yield None
+ continue
+ if stype not in (3, 13, 23):
+ raise ValueError(f"unexpected shape type: {stype}")
+ nparts, npoints = struct.unpack("<ii", c[36:44])
+ parts = list(struct.unpack(f"<{nparts}i", c[44:44 + 4 * nparts])) + [npoints]
+ pts = numpy.frombuffer(c, dtype="<f8", count=2 * npoints,
+ offset=44 + 4 * nparts).reshape(-1, 2)
+ total = 0
+ for a, b in zip(parts[:-1], parts[1:]):
+ q = numpy.radians(pts[a:b])
+ lon, lat = q[:, 0], q[:, 1]
+ h2 = (numpy.sin(numpy.diff(lat) / 2) ** 2 + numpy.cos(lat[:-1]) *
+ numpy.cos(lat[1:]) * numpy.sin(numpy.diff(lon) / 2) ** 2)
+ total += (2 * 6371.0088 * numpy.arcsin(numpy.sqrt(h2))).sum()
+ yield pts[0], pts[-1], total
+
+def parse_tiger(name, y):
+ "The road network of the TIGER/Line EDGES files of year `y`."
+ # numbers in compact arrays, and repeated strings interned, to save memory
+ tnids = array.array("q")
+ pos = array.array("d")
+ tlids = array.array("q")
+ lengths = array.array("d")
+ eprops = defaultdict(list)
+ seen = set()
+ intern = sys.intern
+ for zname in tiger_files(name, y):
+ base = zname[:-4]
+ with open_upstream_file(name, f"{zname}:{base}.dbf", "rb") as fd, \
+ open_upstream_file(name, f"{zname}:{base}.shp", "rb") as fs:
+ for row, shp in zip(iter_dbf(fd), iter_shp_lines(fs)):
+ if row is None or row["ROADFLG"] != "Y":
+ continue
+ tlid = int(row["TLID"])
+ if tlid in seen:
+ continue
+ seen.add(tlid)
+ tnids.extend((int(row["TNIDF"]), int(row["TNIDT"])))
+ pos.extend((float(shp[0][0]), float(shp[0][1]),
+ float(shp[1][0]), float(shp[1][1])))
+ tlids.append(tlid)
+ lengths.append(float(shp[2]))
+ eprops["mtfcc"].append(intern(row["MTFCC"]))
+ eprops["name"].append(intern(row["FULLNAME"]))
+ eprops["county"].append(intern(row["STATEFP"] + row["COUNTYFP"]))
+ eprops["zip_left"].append(intern(row["ZIPL"]))
+ eprops["zip_right"].append(intern(row["ZIPR"]))
+ # (DIVROAD is only in the releases until 2016; a flag missing
+ # from a file is None, and taken as false below)
+ for k, c in [("divided", "DIVROAD"), ("decked", "DECKEDROAD"),
+ ("artificial_path", "ARTPATH")]:
+ eprops[k].append(row[c] == "Y" if c in row else None)
+ del seen
+ for k in ("divided", "decked", "artificial_path"):
+ if all(x is None for x in eprops[k]):
+ del eprops[k]
+ else:
+ eprops[k] = [x is True for x in eprops[k]]
+ eprops["tlid"] = tlids
+ eprops["length"] = lengths
+ tnids = numpy.frombuffer(tnids, dtype="int64").reshape(-1, 2)
+ pos = numpy.frombuffer(pos, dtype="float").reshape(-1, 2, 2)
+ ids, first, inv = numpy.unique(tnids.ravel(), return_index=True,
+ return_inverse=True)
+ g = Graph(directed=False)
+ g.add_vertex(len(ids))
+ g.add_edge_list(inv.reshape(-1, 2))
+ del tnids, inv
+ g.vp.tnid = g.new_vp("int64_t", vals=ids)
+ # the position of a node is the end point of the first edge at it
+ pts = pos.reshape(-1, 2)[first]
+ g.vp.la = g.new_vp("double", vals=pts[:, 1])
+ g.vp.lo = g.new_vp("double", vals=pts[:, 0])
+ del pos, pts
+ for k, vals in eprops.items():
+ t = ("int64_t" if k == "tlid" else "double" if k == "length" else
+ "bool" if k in ("divided", "decked", "artificial_path") else "string")
+ g.ep[k] = g.new_ep(t, vals=vals)
+ eprops.clear()
+ return g
@cache_network()
#@coerce_props()
@@ -60,7 +282,9 @@ def parse(alts=None):
for fname, alt, fmt in files:
if alts is not None and alt not in alts:
continue
- if alt == "merged":
+ if alt.startswith("tiger_"):
+ g = parse_tiger(name, int(alt.split("_")[1]))
+ elif alt == "merged":
with tempfile.TemporaryDirectory(suffix="us_roads",
dir="./cache/temp") as tdir:
with open_upstream_file(name, fname, "r") as rf:
@@ -69,7 +293,7 @@ def parse(alts=None):
subprocess.run(["g++", "-O3", "merge.cpp", "-o", "merge"],
cwd=tdir, check=True)
fnames = []
- for f, *_ in files[:-1]:
+ for f, *_ in state_files:
with open_upstream_file(name, f, "r") as rf:
fnames.append(f.replace('.gz',''))
with open(f"{tdir}/{fnames[-1]}", "w") as wf:
[entries] Lay out spatial networks with cfd_layout() without the SBM partition 9db8d77
Road, power grid, public transport, water and river networks and physical meshes override get_pos() with the default parameters of cfd_layout(), without grouping by the partition of the SBM fit.
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index 5cd72d5..83e400d 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -115,3 +115,9 @@ def parse_graph(f):
g.ep.distance[e] = float(vals[1])
g.ep.road_category[e] = vals[2]
return g
+
+
+def get_pos(g, sbm_fit):
+ # Spatial network: laid out with the default parameters of cfd_layout(),
+ # without the partition of the SBM fit
+ return cfd_layout(g)
[entries] Fix parse bugs and improve descriptions and metadata 6bb6851
- parse fixes from the review of the descriptions, e.g. us_patents (directed), celegans_2019 (synapse direction), ecoli_transcription and yeast_transcription (regulator to target), bitcoin (direction, phantom node), ego_social (Google+ features and circles), scotus_majority, arxiv_authors and social_location (as in SNAP), caida_as, dnc, dom, mist, reuters and bibsonomy (names on the right nodes), uci_zoo - every description now states explicitly what the nodes and edges represent; corrected titles, years, tags, citations and licences - the "Hypergraph" tag is removed; very large entries are marked `huge = True` (see --skip-huge) - ICON ids of partial duplicates added (hiv_transmission, congress_bills, openflights, dutch_school)
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index 3aff635..5cd72d5 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -22,8 +22,13 @@ import tempfile
from .. import *
title = "United States roads (2000)"
-description = """The road networks of the 50 US States and the District of Columbia based on UA Census 2000 TIGER/Line Files. Edges are stretches of road and vertices are intersections of roads. The data sets were assembled by Dominik Schultes. The 'merged' network contains all the states merged together.[^icon]
-[^icon]: Description obtained from the [ICON](https://icon.colorado.edu) project."""
+description = """Road networks of the 50 U.S. states and the District of Columbia, derived from the TIGER/Line files of the U.S. Census Bureau for the 2000 Census. The data were prepared by D. Schultes for the 9th DIMACS Implementation Challenge on shortest paths. Nodes are road intersections and endpoints, and undirected edges are road segments between them. There is one network for each state (named by its two-letter postal code, e.g. `CA`), and the network `merged` combines all states into a single network, as produced by the merging program distributed with the data.
+
+The networks have the following properties:
+
+- `la`, `lo`: the latitude and longitude of the node, in degrees.
+- `distance`: the length of the road segment, and `travel_time`: the estimated travel time along it, both as given in the DIMACS files (the units are not documented there).
+- `road_category`: the road category, given by the numerical part of the TIGER census feature class code (CFCC) of the road (e.g. 11–18 for primary highways with limited access, 21–28 for primary roads without limited access, 31–38 for secondary and connecting roads, and 41–48 for local, neighborhood and rural roads)."""
tags = ['Transportation', 'Roads', 'Unweighted']
url = 'http://www.dis.uniroma1.it/challenge9/data/tiger/'
citation = [('"9th DIMACS Implementation Challenge - Shortest Paths"', 'http://www.dis.uniroma1.it/challenge9/data/tiger/')]
@@ -91,8 +96,9 @@ def parse_graph(f):
continue
vals = line.split()
v = g.vertex(int(vals[0]))
- g.vp.la[v] = float(vals[1]) / 1e6
- g.vp.lo[v] = float(vals[2]) / 1e6
+ # the coordinates are given as (longitude, latitude)
+ g.vp.lo[v] = float(vals[1]) / 1e6
+ g.vp.la[v] = float(vals[2]) / 1e6
if i == N:
break
g.ep.travel_time = g.new_ep("double")
Update copyright information 73a4f0d
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index 6867143..3aff635 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -1,7 +1,7 @@
#! /usr/bin/env python
# -*- coding: utf-8 -*-
#
-# Copyright (C) 2020-2024 Tiago de Paula Peixoto <tiago@skewed.de>
+# Copyright (C) 2020-2026 Tiago de Paula Peixoto <tiago@skewed.de>
#
# This program is free software: you can redistribute it and/or modify it under
# the terms of the GNU Affero General Public License as published by the Free
Update copyright information 3d288ea
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index 991d129..6867143 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -1,7 +1,7 @@
#! /usr/bin/env python
# -*- coding: utf-8 -*-
#
-# Copyright (C) 2020-2023 Tiago de Paula Peixoto <tiago@skewed.de>
+# Copyright (C) 2020-2024 Tiago de Paula Peixoto <tiago@skewed.de>
#
# This program is free software: you can redistribute it and/or modify it under
# the terms of the GNU Affero General Public License as published by the Free
Update copyright information 8d005ae
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index ba491f3..991d129 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -1,7 +1,7 @@
#! /usr/bin/env python
# -*- coding: utf-8 -*-
#
-# Copyright (C) 2021 Tiago de Paula Peixoto <tiago@skewed.de>
+# Copyright (C) 2020-2023 Tiago de Paula Peixoto <tiago@skewed.de>
#
# This program is free software: you can redistribute it and/or modify it under
# the terms of the GNU Affero General Public License as published by the Free
Update copyright info db2efcc
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index 49c3201..ba491f3 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -1,7 +1,7 @@
#! /usr/bin/env python
# -*- coding: utf-8 -*-
#
-# Copyright (C) 2020 Tiago de Paula Peixoto <tiago@skewed.de>
+# Copyright (C) 2021 Tiago de Paula Peixoto <tiago@skewed.de>
#
# This program is free software: you can redistribute it and/or modify it under
# the terms of the GNU Affero General Public License as published by the Free
Update citations to use DOIs e878874
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index 8d85463..49c3201 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -26,7 +26,7 @@ description = """The road networks of the 50 US States and the District of Colum
[^icon]: Description obtained from the [ICON](https://icon.colorado.edu) project."""
tags = ['Transportation', 'Roads', 'Unweighted']
url = 'http://www.dis.uniroma1.it/challenge9/data/tiger/'
-citation = [('9th DIMACS Implementation Challenge - Shortest Paths', 'http://www.dis.uniroma1.it/challenge9/data/tiger/')]
+citation = [('"9th DIMACS Implementation Challenge - Shortest Paths"', 'http://www.dis.uniroma1.it/challenge9/data/tiger/')]
icon_hash = '5723ecbf461efe0c7a675c6e'
upstream_prefix = 'http://www.dis.uniroma1.it/challenge9/data/tiger/'
files = [(f'{s}.tmp.gz', f'{s}',None) for s in ["AK", "AL", "AR", "AZ", "CA",
Change license from GPLv3 to AGPLv3 d754be5
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index 77d7bff..8d85463 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -3,18 +3,18 @@
#
# Copyright (C) 2020 Tiago de Paula Peixoto <tiago@skewed.de>
#
-# This program is free software: you can redistribute it and/or modify
-# it under the terms of the GNU General Public License as published by
-# the Free Software Foundation, either version 3 of the License, or
-# (at your option) any later version.
+# This program is free software: you can redistribute it and/or modify it under
+# the terms of the GNU Affero General Public License as published by the Free
+# Software Foundation, either version 3 of the License, or (at your option) any
+# later version.
#
-# This program is distributed in the hope that it will be useful,
-# but WITHOUT ANY WARRANTY; without even the implied warranty of
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-# GNU General Public License for more details.
+# This program is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+# FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
+# details.
#
-# You should have received a copy of the GNU General Public License
-# along with this program. If not, see <http://www.gnu.org/licenses/>.
+# You should have received a copy of the GNU Affero General Public License along
+# with this program. If not, see <http://www.gnu.org/licenses/>.
import shutil
import subprocess
Add explicit attribution to descriptions obtained from ICON 1645314
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
index 9f4a944..77d7bff 100644
--- a/entries/us_roads/__init__.py
+++ b/entries/us_roads/__init__.py
@@ -22,7 +22,8 @@ import tempfile
from .. import *
title = "United States roads (2000)"
-description = "The road networks of the 50 US States and the District of Columbia based on UA Census 2000 TIGER/Line Files. Edges are stretches of road and vertices are intersections of roads. The data sets were assembled by Dominik Schultes. The 'merged' network contains all the states merged together."
+description = """The road networks of the 50 US States and the District of Columbia based on UA Census 2000 TIGER/Line Files. Edges are stretches of road and vertices are intersections of roads. The data sets were assembled by Dominik Schultes. The 'merged' network contains all the states merged together.[^icon]
+[^icon]: Description obtained from the [ICON](https://icon.colorado.edu) project."""
tags = ['Transportation', 'Roads', 'Unweighted']
url = 'http://www.dis.uniroma1.it/challenge9/data/tiger/'
citation = [('9th DIMACS Implementation Challenge - Shortest Paths', 'http://www.dis.uniroma1.it/challenge9/data/tiger/')]
Initial commit cc85872
diff --git a/entries/us_roads/__init__.py b/entries/us_roads/__init__.py
new file mode 100644
index 0000000..9f4a944
--- /dev/null
+++ b/entries/us_roads/__init__.py
@@ -0,0 +1,110 @@
+#! /usr/bin/env python
+# -*- coding: utf-8 -*-
+#
+# Copyright (C) 2020 Tiago de Paula Peixoto <tiago@skewed.de>
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program. If not, see <http://www.gnu.org/licenses/>.
+
+import shutil
+import subprocess
+import tempfile
+from .. import *
+
+title = "United States roads (2000)"
+description = "The road networks of the 50 US States and the District of Columbia based on UA Census 2000 TIGER/Line Files. Edges are stretches of road and vertices are intersections of roads. The data sets were assembled by Dominik Schultes. The 'merged' network contains all the states merged together."
+tags = ['Transportation', 'Roads', 'Unweighted']
+url = 'http://www.dis.uniroma1.it/challenge9/data/tiger/'
+citation = [('9th DIMACS Implementation Challenge - Shortest Paths', 'http://www.dis.uniroma1.it/challenge9/data/tiger/')]
+icon_hash = '5723ecbf461efe0c7a675c6e'
+upstream_prefix = 'http://www.dis.uniroma1.it/challenge9/data/tiger/'
+files = [(f'{s}.tmp.gz', f'{s}',None) for s in ["AK", "AL", "AR", "AZ", "CA",
+ "CO", "CT", "DC", "DE", "FL",
+ "GA", "HI", "IA", "ID", "IL",
+ "IN", "KS", "KY", "LA", "MA",
+ "MD", "ME", "MI", "MN", "MO",
+ "MS", "MT", "NC", "ND", "NE",
+ "NH", "NJ", "NM", "NV", "NY",
+ "OH", "OK", "OR", "PA", "RI",
+ "SC", "SD", "TN", "TX", "UT",
+ "VA", "VT", "WA", "WI", "WV",
+ "WY"]] + \
+ [("merge.cpp", "merged", None)]
+
+def fetch_upstream(force=False):
+ return fetch_upstream_files(__name__.split(".")[-1], upstream_prefix, files,
+ force)
+
+@cache_network()
+#@coerce_props()
+@annotate()
+def parse(alts=None):
+ global files
+ name = __name__.split(".")[-1]
+ for fname, alt, fmt in files:
+ if alts is not None and alt not in alts:
+ continue
+ if alt == "merged":
+ with tempfile.TemporaryDirectory(suffix="us_roads",
+ dir="./cache/temp") as tdir:
+ with open_upstream_file(name, fname, "r") as rf:
+ with open(f"{tdir}/{fname}", "w") as wf:
+ shutil.copyfileobj(rf, wf)
+ subprocess.run(["g++", "-O3", "merge.cpp", "-o", "merge"],
+ cwd=tdir, check=True)
+ fnames = []
+ for f, *_ in files[:-1]:
+ with open_upstream_file(name, f, "r") as rf:
+ fnames.append(f.replace('.gz',''))
+ with open(f"{tdir}/{fnames[-1]}", "w") as wf:
+ shutil.copyfileobj(rf, wf)
+ subprocess.run(["./merge", "merged.tmp"],
+ input=" ".join(fnames).encode("utf8"),
+ cwd=tdir, check=True)
+ with open(f"{tdir}/merged.tmp", "r") as f:
+ g = parse_graph(f)
+ else:
+ with open_upstream_file(name, fname, "r") as f:
+ g = parse_graph(f)
+
+ yield alt, g
+
+def parse_graph(f):
+ g = Graph(directed=False)
+ g.vp.la = g.new_vp("double")
+ g.vp.lo = g.new_vp("double")
+ for i, line in enumerate(f):
+ if i == 0:
+ N = int(line.strip())
+ g.add_vertex(N)
+ continue
+ vals = line.split()
+ v = g.vertex(int(vals[0]))
+ g.vp.la[v] = float(vals[1]) / 1e6
+ g.vp.lo[v] = float(vals[2]) / 1e6
+ if i == N:
+ break
+ g.ep.travel_time = g.new_ep("double")
+ g.ep.distance = g.new_ep("double")
+ g.ep.road_category = g.new_ep("string")
+ for i, line in enumerate(f):
+ if i == 0:
+ continue
+ vals = line.split()
+ if i % 2 != 0:
+ e = g.add_edge(int(vals[0]), int(vals[1]))
+ else:
+ g.ep.travel_time[e] = float(vals[0])
+ g.ep.distance[e] = float(vals[1])
+ g.ep.road_category[e] = vals[2]
+ return g