Finite Graph Theory and its Applications

Semester project for the Graph Theory course in St. Petersburg State University.

Description

Using data from the nonprofit mapping project OpenStreetMap, build a routing graph of one of Russian megalopolises.

For our project we have chosen the city of Nizhny Novgorod.

M random infrastructure facilities (e.g., hospitals) and N random houses in the chosen city are selected.

Each task should have a description in either assessment.cpp or planning.cpp.

Dependencies

Dynamic libraries:

• osmcode/libosmium
• mapbox/protozero
• fmtlib/fmt

Static libraries:

• p-ranav/argparse
• nlohmann/json
• d99kris/rapidcsv

Build

$ mkdir build; cd build
$ cmake -Release ..
$ make

With Release build type, maximum optimization level is set.

Successfully built with Clang 10 and GCC 10 under Linux.

Usage

Default launch:

$ graphs 15 30

File with map could be specified explicitly (default is NNMap.pbf):

$ graphs 15 30 --file NNMap.pbf

The first and the second arguments denote number of houses and facilities accordingly.

With the first launch, map is created (approx. 3 minutes). With succeeding launches, cache is used (saved at .cache). Map could be re-cached (e.g., if different map is used):

$ graphs 15 30 --recache

Graph could be exported to .csv (both as an adjacency matrix and as a list):

$ graphs 15 30 --export