**************************************************************************************************************** ******************************************* GRAIL (multithreaded) ****************************************** ******************************* Authors: Federico MARESCA, Alessandro IPPOLITO. ****************************** **************************************************************************************************************** ################################################################################################################ ########### DISCLAIMER: This program has been modified from the original version by Hilmi YILDIRIM ########### ##################### The original code is available at https://github.com/zakimjz/grail ##################### ################################################################################################################ The code is associated with the following papers: 1) Grail: scalable reachability index for large graphs (VLDB'10 paper) Detailed usage is explained below, here we give sample usage --------------------------------------------------------------- ./grail sample.gra 2 sample.test --------------------------------------------------------------- The code is written in C++. To compile : make To run with instructions: ./grail -h Usage: grail [-h] <filename> [dim] <testfilename> Description: -h Optional, print this help message. <filename> The name of the input graph in gra format. dim Optional, set the number of traversals to be performed. The default value is 2. Algorithm type: Bidirectional Search. -> o alla fine abbiamo adottato la DFS normale? Labeling type: Completely randomized traversals. INPUT GRAPH FORMAT: (see sample.gra) Note: First line gives the number of nodes n. The node ids should be in [0,n-1]. TEST FILE FORMAT: (see sample.que) If the file is in "Quer" format (means no ground truth): - Each line contains tuple (<source> <target>) If the file is in standard format: - Each line contains triples (<source> <target> <reachability>) - The program compares its output with <reachability> value of each query and prints a success ratio which is supposed to be 1. Selection of Dimensionality: For sparse graphs (avg. degree up to 3): dim 2 is quite optimal. For denser graphs, you can increase it up to 5. The program reports the construction time, labeling time and query time. If testfilename contains ground truth, also success rate is printed.
AleIppolito/SdP_project_Q2
GRAIL project from Zaki, but sped up and multithreaded. Has less options, uses only bidirectional reach and random labeling
C++