A toolbox of basic data structures and algorithms. If you heard of OSRM, please draw your own conclusions. 😁
A tool to normalize graphs from various input formats into a normalized intermediate representation that is easily understood by the tool set.
A tool to bisect graphs in the DIMACS, (unweighted) METIS or DDSG format using an implementation of the Inertial Flow method. Example graphs can be downloaded on the website of the 9th DIMACS implemenation challenge. Chipper reproduces the runtime and quality numbers reported by Schild and Sommer (2015). Currently, a balance factor of 0.25 is the default, and can be overridden via the command line.
A tool to generate run-time data structures from pre-process graph. At this point it supports visualizing cells by their convex hulls. The result of this is stored in GeoJSON format which can be easily visualized, e.g. on Kepler.gl.
$ cargo r --release --bin scaffold -- -p /path/to/USA-r20-m100.assignment.bin -c /path/to/USA-road-d.USA.co --convex-cells-geojson /path/to/bbox.geojson
The complete work flow is as follows. First, the input data is converted into a normalized format, then the tools are run for processing.
Convert file to intermediate format:
$ cargo r --release --bin graph_plier -- -i dimacs -g /path/to/USA-road-d.USA.gr -c /path/to/USA-road-d.USA.co
Partition the graph recursively up to 30 times or until a cell has less than a hundred nodes:
$ cargo r --release --bin chipper -- -g /path/to/USA-road-d.USA.gr.toolbox -c /path/to/USA-road-d.USA.co.toolbox -o /path/to/result.txt -r30 -m100 -p /path/to/USA-r30-m100.assignment.bin
Generate GeoJSON file visualizing the cells:
$ cargo r --release --bin scaffold -- -c /path/to/USA-road-d.USA.co.toolbox -g /path/to/USA-road-d.USA.gr.toolbox -p /path/to/USA-r30-m100.assignment.bin --convex-cells-geojson /path/to/bbox.geojson
