History of dimacs10_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/dimacs10_roads/__init__.py b/entries/dimacs10_roads/__init__.py
index feef8dd..a5b3b8d 100644
--- a/entries/dimacs10_roads/__init__.py
+++ b/entries/dimacs10_roads/__init__.py
@@ -119,6 +119,6 @@ def parse(alts=None):
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/dimacs10_roads/__init__.py b/entries/dimacs10_roads/__init__.py
index 446920d..feef8dd 100644
--- a/entries/dimacs10_roads/__init__.py
+++ b/entries/dimacs10_roads/__init__.py
@@ -35,7 +35,7 @@ url = ['https://sites.cc.gatech.edu/dimacs10/archive/streets.shtml',
'https://www.openstreetmap.org']
citation = [('D. A. Bader, H. Meyerhenke, P. Sanders, D. Wagner (eds.), "Graph Partitioning and Graph Clustering. 10th DIMACS Implementation Challenge Workshop." Contemporary Mathematics 588, American Mathematical Society (2013)', 'https://doi.org/10.1090/conm/588')]
upstream_license = None
-icon_hash = None
+date_added = '2026-10-27'
upstream_prefix = 'https://sites.cc.gatech.edu/dimacs10/archive/data/streets'
regions = ["europe", "asia", "belgium", "germany", "great-britain", "italy",
"luxembourg", "netherlands"]
[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/dimacs10_roads/__init__.py b/entries/dimacs10_roads/__init__.py
index d45cf0b..446920d 100644
--- a/entries/dimacs10_roads/__init__.py
+++ b/entries/dimacs10_roads/__init__.py
@@ -29,7 +29,7 @@ A node is a point of a road (an OSM node: an intersection, or a point along the
The networks have the following properties:
-- `latitude` and `longitude`: the geographical position of the node (the coordinate files of the challenge give them in units of $10^{-5}$ degrees, with the latitudes shifted by one degree, which is corrected here; e.g. the end of the road at the North Cape, at 71.169° N, appears at 72.169°)."""
+- (Node) `latitude` and `longitude`: the geographical position of the node (the coordinate files of the challenge give them in units of $10^{-5}$ degrees, with the latitudes shifted by one degree, which is corrected here; e.g. the end of the road at the North Cape, at 71.169° N, appears at 72.169°)."""
tags = ['Transportation', 'Roads', 'Spatial', 'Unweighted']
url = ['https://sites.cc.gatech.edu/dimacs10/archive/streets.shtml',
'https://www.openstreetmap.org']
[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/dimacs10_roads/__init__.py b/entries/dimacs10_roads/__init__.py
index f05c548..d45cf0b 100644
--- a/entries/dimacs10_roads/__init__.py
+++ b/entries/dimacs10_roads/__init__.py
@@ -99,7 +99,6 @@ def read_coords(f, N, chunk=1 << 24):
@coerce_props()
@annotate()
def parse(alts=None):
- global files
name = __name__.split(".")[-1]
for fnames, alt, fmt in files:
if alts is not None and alt not in alts:
[entries] New entry: dimacs10_roads bc529c1
diff --git a/entries/dimacs10_roads/__init__.py b/entries/dimacs10_roads/__init__.py
new file mode 100644
index 0000000..f05c548
--- /dev/null
+++ b/entries/dimacs10_roads/__init__.py
@@ -0,0 +1,125 @@
+#! /usr/bin/env python
+# -*- coding: utf-8 -*-
+#
+# Copyright (C) 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
+# 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 Affero General Public License for more
+# details.
+#
+# 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 bz2
+import io
+import itertools
+
+from .. import *
+
+title = "OpenStreetMap road networks of Europe and Asia (DIMACS10, 2010)"
+description = """Road networks of Europe, Asia and six European countries, extracted from OpenStreetMap (OSM) by M. Kobitzsch (Karlsruhe Institute of Technology) for the 10th DIMACS Implementation Challenge on graph partitioning and graph clustering (2011–2012). The OSM data were downloaded from Geofabrik on March 23–24, 2010; all routable streets were extracted (the OSM ways tagged `motorway`, `trunk`, `primary`, `secondary` and `tertiary`, with their links, and `residential`, `unclassified`, `road`, `living_street` and `service`), and the largest strongly connected component of the resulting directed road graph was kept, without self-loops and parallel edges. The networks are the undirected and unweighted versions of these components (a one-way street becomes an undirected edge).
+
+A node is a point of a road (an OSM node: an intersection, or a point along the course of a road), and an edge is a road segment between two consecutive points. Since the points along the course of roads are kept, most nodes have degree two. There is one network for each region: `europe`, `asia`, `belgium`, `germany`, `great_britain`, `italy`, `luxembourg` and `netherlands`; the countries are separate extracts, which overlap with the `europe` network.
+
+The networks have the following properties:
+
+- `latitude` and `longitude`: the geographical position of the node (the coordinate files of the challenge give them in units of $10^{-5}$ degrees, with the latitudes shifted by one degree, which is corrected here; e.g. the end of the road at the North Cape, at 71.169° N, appears at 72.169°)."""
+tags = ['Transportation', 'Roads', 'Spatial', 'Unweighted']
+url = ['https://sites.cc.gatech.edu/dimacs10/archive/streets.shtml',
+ 'https://www.openstreetmap.org']
+citation = [('D. A. Bader, H. Meyerhenke, P. Sanders, D. Wagner (eds.), "Graph Partitioning and Graph Clustering. 10th DIMACS Implementation Challenge Workshop." Contemporary Mathematics 588, American Mathematical Society (2013)', 'https://doi.org/10.1090/conm/588')]
+upstream_license = None
+icon_hash = None
+upstream_prefix = 'https://sites.cc.gatech.edu/dimacs10/archive/data/streets'
+regions = ["europe", "asia", "belgium", "germany", "great-britain", "italy",
+ "luxembourg", "netherlands"]
+files = [((f"{r}.osm.graph.bz2", f"{r}.osm.xyz.bz2"), r.replace("-", "_"), None)
+ for r in regions]
+
+def fetch_upstream(force=False):
+ return fetch_upstream_files(__name__.split(".")[-1], upstream_prefix, files,
+ force)
+
+def read_metis(f, g, chunk=1 << 22):
+ """Read the undirected graph in the METIS format (adjacency lists, one
+ line per vertex, 1-based) from the text stream `f` into `g`, streaming it
+ in chunks of lines; each edge is added once (from its lower endpoint)."""
+ line = f.readline()
+ while line.startswith("%"):
+ line = f.readline()
+ header = line.split()
+ N, E = int(header[0]), int(header[1])
+ if len(header) > 2 and header[2] not in ("0", "00", "000"):
+ raise ValueError(f"unsupported METIS format: {header[2]}")
+ g.add_vertex(N)
+ v = 0
+ while v < N:
+ lines = f.readlines(chunk)
+ if not lines:
+ break
+ lines = [l for l in lines if not l.startswith("%")]
+ lines = lines[:N - v]
+ parts = [l.split() for l in lines]
+ deg = numpy.fromiter((len(p) for p in parts), dtype="int64",
+ count=len(parts))
+ tgt = numpy.array(list(itertools.chain.from_iterable(parts)),
+ dtype="int64") - 1
+ src = numpy.repeat(numpy.arange(v, v + len(lines), dtype="int64"), deg)
+ mask = src < tgt
+ g.add_edge_list(numpy.column_stack((src[mask], tgt[mask])))
+ v += len(lines)
+ if v != N or g.num_edges() != E:
+ raise ValueError(f"expected {N} vertices and {E} edges, got {v} and "
+ f"{g.num_edges()}")
+
+def read_coords(f, N, chunk=1 << 24):
+ "Read the coordinates of the N vertices (one 'x y z' line each)."
+ x = numpy.empty(N)
+ y = numpy.empty(N)
+ i = 0
+ while True:
+ lines = f.readlines(chunk)
+ if not lines:
+ break
+ a = numpy.array(" ".join(lines).split(), dtype="float").reshape(-1, 3)
+ x[i:i + len(a)] = a[:, 0]
+ y[i:i + len(a)] = a[:, 1]
+ i += len(a)
+ if i != N:
+ raise ValueError(f"expected {N} coordinates, got {i}")
+ return x, y
+
+@cache_network()
+@coerce_props()
+@annotate()
+def parse(alts=None):
+ global files
+ name = __name__.split(".")[-1]
+ for fnames, alt, fmt in files:
+ if alts is not None and alt not in alts:
+ continue
+ g = Graph(directed=False)
+ with open_upstream_file(name, fnames[0], "rb") as fb:
+ with io.TextIOWrapper(bz2.open(fb), "ascii") as f:
+ read_metis(f, g)
+ with open_upstream_file(name, fnames[1], "rb") as fb:
+ with io.TextIOWrapper(bz2.open(fb), "ascii") as f:
+ x, y = read_coords(f, g.num_vertices())
+ # The coordinates are in units of 1e-5 degrees, and the latitudes are
+ # shifted by one degree (e.g. the North Cape, at 71.169 N, 25.783 E,
+ # is at x = 2578311, y = 7216923)
+ g.vp.latitude = g.new_vp("double", vals=y * 1e-5 - 1)
+ g.vp.longitude = g.new_vp("double", vals=x * 1e-5)
+ yield alt, 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)