25 releases (11 breaking)
✓ Uses Rust 2018 edition
|0.12.1||Mar 28, 2020|
|0.11.1||Mar 12, 2020|
|0.6.1||Dec 3, 2019|
|0.6.0||Sep 22, 2019|
#51 in Parser implementations
231 downloads per month
Welcome to the
Goal of this repo is parsing openstreetmap-data to calculate traffic-routes and different related use-cases on it.
This repo will be involved in dealing with the analysis of selfish routing and learning metrics for balancing load in street-networks.
All calculations should be done effectively on a single desktop instead of an expensive cluster.
I'm currently building this library for my master-thesis, leading to interface-changes with breaking changes (at least) every few weeks, why version
1.0.0 is not supported yet.
However, the underlying parser and graph-structure are working very stable, efficiently, tested with different maps (see
resources/), and will be used in
April 2020 to simulate different routing-scenarios, so version
1.0.0 should be reached soon.
Rust has a build-tool called
cargo, which can be used to run everything except scripts in
# Just executing some easy cargo-build-commands ./scripts/build.sh # Parse isle-of-man ./target/release/osmgraphing --config resources/config/isle-of-man.pbf.yaml
Downloaded osm-data is provided in xml (
osm) or binary (
pbf), where nodes are related to location in latitude and longitude.
Problems will be the size-limit when downloading from openstreetmap, but there are other osm data providers like geofabrik for instance.
For testing, some simple text-based format
fmi is used.
Since they are created manually for certain tasks, parsing them - generally speaking - is unstable.
However, this repository has a generator, which can create such
pbf- or other
fmi-files (e.g. for different metric-order).
mapgenerator (binaries are in
target/release after release-building) helps with generating proper config-files, but have a look at
resources/configs/blueprint to get further explanations.
A tool for creating
fmi-map-files, which contain graphs contracted via contraction-hierarchies, is multi-ch-constructor.
In general, the requirements depend on the size of the parsed map (also same map of different dates) and your machine.
Following numbers base on an 8-core-CPU and the
March 14th, 2020 running on
archlinux with 16 GB RAM.
Basing on the numbers below, without doing further detailled benchmarks, the memory-usage scales linearly with the graph-size with a growth-factor of
Hence you could expect around
4x graph-size (meaning
4x node- and
In the module
defaults, you should change the number of inlined metrics (for
SmallVec) according to your needs.
Several GB can be saved by doing so.
Germany.pbf(4 metrics, ~51 million nodes, ~106 million edges) needs around 14 GB of RAM at peak. After parsing, the memory-needs are much lower due to the optimized graph-structure.
Germany.pbf(including parsing) needs less than 4 minutes.
- A routing query on
Germany.pbfof distance around
600 kmtakes around 22 seconds with
bidirectional Dijkstra, highly depending on the specific src-dst-pair (and its search-space). This could be improved by removing intermediate nodes (like
a->b->c), but they are kept for now. Maybe, they are needed for precise/realistic traffic-simulation. An
Astaris not used anymore, because its only purpose is reducing the search-space, which can be reduced much more using
Contraction Hierarchies. Further,
Astarhas issues when it comes to multiple or custom metrics, because of the metrics' heuristics.
Small maps like
Isle-of-Man.pbf (~50_000 nodes, ~107_000 edges) run on every machine and are parsed in less than a second.
The German state
Baden-Württemberg.pbf (~9 million nodes, ~18 million edges) needs less than 5 GB RAM at peak and around 30 seconds to parse.
For speedup, this repository supports graphs contracted via contraction-hierarchies.
lesstat/multi-ch-constructor generates contracted graphs from
fmi-files of a certain format.
osmgraphing, uses the
bec548c1a1ebeae7ac19d3250d5473199336d6fe) for its ch-graphs.
For reproducability, the used steps are listed below.
First of all, the tool
multi-ch needs an
fmi-map-file of specific format as input.
To generate such a
fmi-map-file in the correct format, the
osmgraphing can be used with the
generator-config shown below, following the defined requirements.
Ignores are important, because the
multi-ch-constructor needs the placeholders.
Besides that, the
multi-ch-constructor uses node-indices as ids, leading to errors when the mapping
node -> indices [0; n] is not surjective.
parser: map-file: 'resources/maps/isle-of-man_2020-03-14.osm.pbf' vehicles: category: 'Car' are-drivers-picky: false nodes: - category: 'NodeId' - category: 'Latitude' - category: 'Longitude' edges: - category: 'SrcId' - category: 'DstId' - category: 'Meters' is-provided: false - category: 'KilometersPerHour' - category: 'Seconds' is-provided: false calc-rules: ['Meters', 'KilometersPerHour'] - category: 'Ignore - SrcIdx' id: 'SrcIdx' - category: 'Ignore - DstIdx' id: 'DstIdx' generator: map-file: 'resources/maps/isle-of-man_2020-03-14.fmi' nodes: - category: 'NodeIdx' - category: 'NodeId' - category: 'Latitude' - category: 'Longitude' - category: 'Ignore' # height - category: 'Ignore' # level for contraction-hierarchies edges: - id: 'SrcIdx' - id: 'DstIdx' - id: 'Meters' - id: 'Seconds' - id: 'Ignore' # shortcut-edge-0 - id: 'Ignore' # shortcut-edge-1
multi-ch-tool needs 3 counts at the file-beginning: metric-count (dimension), node-count, edge-count.
mapgenerator does add these counts in this order.
multi-ch-tool can be used, it has to be built.
For the sake of optimization, you have to set the metric-count as dimension in multi-ch-constructor/src/multi_lib/graph.hpp, line 49.
Set this dimension according to the dimension in the previously generated
git clone --recursive https://github.com/lesstat/multi-ch-constructor cd multi-ch-constructor cmake -Bbuild cmake --build build ./build/multi-ch --text path/to/fmi/graph --percent 99.85 --stats --write path/to/new/fmi/graph
Note that the multi-ch-constructor is not deterministic (March 12th, 2020). Using it does only speedup your queries, but due to a different resulting order in the priority or rounding-errors, it could lead to different paths of same weight.
The project started in the mid of 2019 as a student project. This page honors the workers and helpers of this project, sorted by their last names.
is the supervisor of the project since beginning and is always helping immediately with his experience and advice.
Dominic Parga Cacheiro
has been part of the project's first weeks when project-planning and learning Rust was on the scope. He continues the work and is writing and improving the simulation.
has been part of the project's first weeks when project-planning and learning Rust was on the scope. He has implemented the first (and running) approach of the