osmgraphing

[![Build Status nightly][github/self/actions/badge]][github/self/actions]

[![Tag][github/self/tags/badge]][github/self/tags] [![Crates.io][crates.io/self/badge]][crates.io/self] [![Docs][docs.rs/self/badge]][docs.rs/self]

[![Changelog][github/self/blob/changelog/badge]][github/self/blob/changelog] [![Last commit][github/self/last-commit/badge]][github/self/last-commit]

[![License][github/self/license/badge]][github/self/license]

<img title="Balancing Saarland" src="resources/saarland_2020-07-30/balancing/workloads.gif" alt="Balancing Saarland" />

This GIF shows, how the balancing improves the spread of 10,000 paths over the network of the German state Saarland. New paths from s to t are guaranteed being not worse than 25 % than the optimal path from s to t, with respect to travel-duration (so 55 min becomes under 1 h 10 min in the worst-case).

Welcome to the osmgraphing-repo! :) Goal of this repo is parsing [openstreetmap][osm]-data to calculate traffic-routes and different related use-cases on it. This repo is involved in dealing with the analysis of selfish routing and learning metrics for balancing load in street-networks. See [my master-thesis][github/dominicparga/master-thesis] for more details. However, if a self-written parser-module does exist, every map-format supported by this module (e.g. own csv-like formats) can be used, which doesn't need to be a street-network.

All calculations will be optimized for a single desktop instead of a more expensive cluster. The current machine (August 2020) uses an AMD Ryzen 7 3700X 8-Core Processor and has 32 GB of RAM.

Reason for version above 1.0.0 <a name="version"></a>

This repository is my first project in Rust :). Some interface-decisions might be open for discussion (like the public helpers-module) and the graphbuilder has some quite long functions. The resources consume too much memory due to the graph- and routing-files (fresh clone around 20 MB). However, the code works very solid. Large design-decisions are described nicely in my [master-thesis][github/dominicparga/master-thesis], which bases on this repository. This was a student-project, a master-thesis, a learning-project and fulfilled these purposes perfectly. Because of this, version 1.1.1 has been published in October 2020 without many further refactoring.

Copyright and License <a name="copyright_and_license"></a>

Please refer to LICENSE.md for details. Copyright-owner is Parga Cacheiro, Dominic. In short, this repository and generated binaries are licensed under the Apache-2.0-license as long as you are not using the cargo-feature gpl. Using this cargo-feature adds some code and binaries, which depend on code licensed under the GPL-3.0. Thus, the resulting binaries are licensed under the GPL-3.0.

Table of contents <a name="toc"></a>

1. [Reason for version above 1.0.0][self/version]
2. [Copyright and License][self/copyright_and_license]
3. [Table of contents][self/toc]
4. [Setup and usage][self/setup-and-usage]
   1. [Long story short][self/long-story-short]
   2. [Downloading and generating maps][self/downloading-and-generating]
   3. [Editing the config][self/editing-the-config]
   4. [Inlined metrics][self/inlined-metrics]
   5. [Requirements for large maps (e.g. countries)][self/large-maps]
   6. [Contraction-Hierarchies][self/contraction-hierarchies]
5. [Balancing][self/balancing]
6. [Credits][self/credits]

Setup and usage <a name="setup-and-usage"></a>

Please find instructions and info below.

Long story short <a name="long-story-short"></a>

Execute the following for a (verbose) routing-example.

# Further execution-info
cargo run --release --bin osmgraphing -- --help

# Build the binary for parsing maps and do routing
# and parse isle-of-man.
cargo run --release --bin osmgraphing -- --config resources/isle_of_man_2020-03-14/osm.pbf.yaml --routing

You can download pbf-files from [geofabrik][geofabrik] and cast them to other formats. When editing the config, take [resources/blueprint.yaml][github/self/blob/blueprint.yaml] as guide.

To use the balancer, a [clone][github/dominicparga/multi-ch-constructor] of [multi-ch-constructor-repo][github/lesstat/multi-ch-constructor] is used as submodule, written in c++. This osmgraphing-repo is wrapping the submodule as Rust-module, using configs for its execution-parameters. To get it run, please install the dependencies according to the [workflow-file][github/self/workflow] (working successfully in August 2020). Please note that the balancer bases on code, that is licensed under the GPL-3.0. Therefore, you have to enable features (via cargo).

# Update git-submodules, because they are used in the balancer
git submodule update --init --recursive

# Build also features licensed under the `GPL-3.0`.
# Build with GRAPH_DIM=6.
GRAPH_DIM=6 cargo run --release --features='gpl' --bin osmgraphing -- --config resources/isle_of_man_2020-03-14/balancing/config.yaml --balancing

# After finishing, you may visualize the data
# (the results-dir, excluding the utc-stamp, is specified in the config)
py ./scripts/balancing/visualizer --results-dir 'custom/results/<map-name>/utc_<date_and_time>

As mentioned above, you may find a detailled config-blueprint in resources/ and a balancing-example in resources/isle_of_man/. As defined in the config.yaml, the results can be found in custom/results/isle_of_man and may be visualized with the python-module in scripts/. The python-tool has a help-msg, but the balancer also prints the respective command after finishing.

Note: The reources/blueprint.yaml is correct and complete. Configs of the maps might be slightly broken due to missing or old keywords, because they are not used very often. Since this repository is used by just a very few people, these configs are still kept as helping example.

Overview of all features

The following table shows all features of this repository. The cargo-features are needed to build the respective feature. Some cargo-features are optional for the feature, meaning that the cargo-feature adds extra-functionality. You can build with cargo-features using cargo build --features='F0,F1,...' (cargo run builds implicitly).

| cargo-feature | Notes | |:---------------:|:------| | 'gpl' | This feature is needed for every part of the code, that is licensed under the GPL-3.0. Even if you are using this cargo-feature, it doesn't force you to license data under the GPL-3.0, that has been created with the gpl-code. | | 'custom' | This repository ships with small maps, like handmade maps or Isle-of-Man, but larger maps like the German state Saarland, parts of German states like Stuttgart-Regierungsbezirk or countires like Germany consume multiple 100 MB and more memory. Although, some tests are using these maps and configs may be useful, which is the reason for this cargo-feature. To get this feature working, simply download the maps, move them into the respective map-directory in resources/, and name them according to other map-directories. |

Downloading and generating maps <a name="downloading-and-generating"></a>

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][osm], but there are other osm data providers like [geofabrik][geofabrik] for instance. For now, without a parser-module for osm-data, only binary osm.pbf-data is supported.

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 fmi-files from pbf- or other fmi-files (e.g. for different metric-order) based on a config.

A tool for creating fmi-map-files, containing graphs contracted via contraction-hierarchies, is [multi-ch-constructor][github/lesstat/multi-ch-constructor], which is used in the balancer and hence a submodule of this repo. Further, this repo has a wrapping binary multi-ch-constructor for the submodule, using a config as well.

Editing the config <a name="editing-the-config"></a>

Every possible option of a config is described in [resources/blueprint.yaml][github/self/blob/blueprint.yaml]. The binaries (osmgraphing, multi-ch-constructor) (binaries are in target/release after release-building) use the config for different use-cases.

Inlined metrics <a name="inlined-metrics"></a>

Metrics are inlined using [SmallVec][github/servo/rust-smallvec]. This improves performance and can save several GB of RAM. If your config uses less metrics than you have compiled to, you will receive a warning. Further, if the compiled number of inlined metrics is less than the number of your config's metrics, the graph can't be used efficiently and throws an error. In this case, you must change the number of inlined metrics according to your needs, and rebuild. The command cargo build simply becomes GRAPH_DIM=6 cargo build. The default is quite small (~4), but may change over time.

Requirements for large maps (e.g. countries) <a name="large-maps"></a>

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 pbf-maps from 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 0.5. Hence you could expect around 2x RAM-usage for 4x graph-size (meaning 4x node- and 4x edge-count).

• Parsing Germany.pbf (4 metrics, `