Fully dynamic highway labelling (FulHL)

This is an implementation of the paper

Muhammad Farhan, Qing Wang, Yu Lin, and Brendan McKay, Fast fully dynamic labelling for distance queries.

Sample data format

The format of the dataset text file is as follows:
Line 1 : |V| |E|
Line 2 : vertex_u deg_u v1 ... vn, where v1 to vn are neighbors of u. Note that the vertex id are from 0 to (V-1), where V is the number of vertices. There are no self loops in the graph, i.e., no edge from any vertex to itself.

To see the accepted format for graphs, updates and query pairs, you may refer to the Sample Data folder. After the test inputs are ready, please use the following commands to test FulHL.

1 - Compile source files

$ g++ -O3 -std=c++11 main.cpp -o run

2 - Construct Labelling

./run construct_labelling @1 @2 @3
@1: name of the dataset
@2: number of landmarks
@3: file to store labelling

Example:
./run construct_labelling graph.txt 20 graph_labelling

3 - Update Labelling

./run update_labelling @1 @2 @3 @4 @5
@1: name of the dataset
@2: number of landmarks
@3: file to load the labelling from
@4: file containing updates
@5: method parameter for incremental updates (0 - not to prune or 1 - to prune)

Example:
./run update_labelling graph.txt 20 graph_labelling updates.txt 0

4 - Perform distance queries

./run query-dis @1 @2 @3 @4 @5
@1: name of the dataset
@2: number of landmarks
@3: file to load the labelling from
@4: file containing query pairs
@5: file to write query results

Example:
./run query_labelling graph.txt 20 graph_labelling query_pairs.txt query_results.txt