Skip to content
forked from mufarhan/FulHL

Fully Dynamic Labelling For Answering Exact Distance Queries

Notifications You must be signed in to change notification settings

maxdemarzi/FulHL

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

35 Commits
 
 
 
 
 
 

Repository files navigation

Fully dynamic highway labelling (FulHL)

This is the 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 @6
@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 batch.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

About

Fully Dynamic Labelling For Answering Exact Distance Queries

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C++ 100.0%