GARP

generate representative path sets from graphs and calculate important nodes from path sets

How to use

required: Rust, tested for version 1.57.

To calculate a list of important nodes:

1. Create (or download) a CH graph in FMI text file format
2. Build with cargo build --release
3. Run the wspd binary (target/release/wspd -g <graph.fmi> -d <max tree depth> -e <wspd separation> -o <output: paths file>)
4. Run the hittingset binary (target/release/hittingset -g <graph.fmi> -p <paths file> -o <output: node list>)

There will be some cache files stored in the directory of your graph file. These will be used in subsequent runs to skip the preprocessing steps and reduce runtimes. They may be deleted but will be recalculated on the next run.

Output File Formats

• The wspd binary creates a list of weighted paths (weight, edgeId1, edgeId2, ..., edgeIdN), one per line. Edges are named by their id as they are listed in the graph file.
• The hittingset binary creates a list of NodeIds, one per line. These Ids are the NodeId given in the graph file.

Binaries

This project contains multiple binaries. To create path sets or find important nodes, you will need the WSPD and hittingset binaries. If you are looking for details on the implementation, take a look at project-overview.md

WSPD

Generates a WSPD and samples each pair for a weighted shortest path, then stores all of them to file.
Requires a .fmi graph file and parameters d (max tree depth) and epsilon (wspd separation). See wspd --help for all parameters.

Hittingset

Calculates a hitting set based on paths provided.
Requires a .fmi graph file and a set of paths (generated by the wspd binary). Optionally, one can limit the resulting set size. See hittingset --help for all parameters.

Analysis tools

Pathgen

For testing, random shortest paths can be generated using this binary. This will pick random point pairs and find a shortest path using the ch dijkstra search.

Visualizations

Map drawing utility, producing either a .png file or a geojson object that can be viewed on geojson.io or similar websites. Drawing options include:

• Drawing some (or all) cells of the QuadTree
• Drawing all WSPD pairs of a specific cell
• Drawing paths between cell pairs
• Drawing (some) points contained in a cell

Additional analysis binaries

These calculate additional data or print detailed progress information for all algorithms. Take a look at the run_analysis.sh script for details.