This is the implementation of the GLL-based context-free path querying (CFPQ) algorithm. It is based on a high-performance GLL parsing algorithm implemented in Iguana project. Then, it was modificated to support graph-structured input data. Proposed solution solves both reachability and all paths problems for all pairs and multiple sources cases.

The proposed solution has been evaluated on several real-world graphs for both the all pairs and the multiple sources scenarios. The evaluation shows that the proposed solution is more than 45 times faster than the previous solution for Neo4j and is comparable, in some scenarios and cases, with the linear algebra based solution.

Machine configuration: PC with Ubuntu 20.04, Intel Core i7-6700 3.40GHz CPU, DDR4 64Gb RAM.

Enviroment configuration:

• Java HotSpot(TM) 64-Bit server virtual machine (build 15.0.2+7-27, mixed mode, sharing).
• JVM heap configuration: 55Gb both xms and xmx.
• Neo4j 4.0.3 is used. Almost all configurations are default except two:
  • total off-heap transaction memory (tx_state_max_off_heap_memory parameter) is set to 24Gb
  • pagecache_warmup_enabled is set to true.

The graph data is selected from CFPQ_Data dataset. There are two types of graph:

• Graphs related to RDF analysis problems
• Graphs related to static code analysis problems

A detailed description of the graphs is listed bellow.

RDF analysis

Static code analysis

All queries used in evaluation are variants of same-generation query. The inverse of an x relation and the respective edge is denoted as x_r.

Grammars used for RDF graphs:

G₁

S -> subClassOf_r S subClassOf | subClassOf_r subClassOf 
     | type_r S type | type_r type

G₂

S -> subClassOf_r S subClassOf | subClassOf

Geo

S -> broaderTransitive S broaderTransitive_r
     | broaderTransitive broaderTransitive_r 

Grammar used for static code analysis graphs:

PointsTo

M -> d_r V d
V -> (M? a_r)* M? (a M?)* 

The results of the all pairs reachability queries evaluation on graphs related to RDF analysis are listed below.

The sign ’–’ in cells means that the respective query is not applicable to the graph, so time is not measured.

The evaluation results for single source CFPQ for graphs related to RDF analysis and G₁, G₂, Geo grammars respectively in reachability and all paths scenarious:

The results for graphs related to static code analysis are compared to results of Azimov’s CFPQ algorithm based on matrix operations. The implementation from CFPQ_PyAlgo was taken as the implementation of the matrix CFPQ algorithm. This library contains the implementation for both scenarios, all pairs reachability and single source reachability. To perform matrix operations pygraphblas is used. Pygraphblas is a python wrapper over the SuiteSparse library, which based on the GraphBLAS framework.

The results of the all pairs reachability queries evaluation on graphs related to static code analysis are listed below.

The sign ’–’ in cells means that the respective query and graph require a considerable amount of memory during algorithm execution that leads to unpredictable time to get the result.

The evaluation results for single source CFPQ for graphs related to static code analysis and pointsTo grammar in reachability and all paths scenarious:

The project is build with Maven.

git clone https://github.com/JetBrains-Research/GLL4Graph
cd GLL4Graph
mvn compile

To replicate experiments:

• make the directory to save results

mkdir results

• run the following command with arguments

mvn exec:java -Dexec.mainClass="benchmark.Neo4jBenchmark" -Dexec.args="arg1 arg2 arg3 arg4 arg5 agr6 agr7 arg8"

Here is an example which can be run right after project is downloaded and results directory is created without any additional preparation.

To run experiments on Core graph on G₁ grammar use the following command:

mvn exec:java -Dexec.mainClass="benchmark.Neo4jBenchmark" -Dexec.args="st 1323 2 5 <ABS_PATH_TO_PROJECT>/data/core/ test/resources/grammars/graph/g1/grammar.json core g1"

To get more graph data examples use Python script:

graph_loader.py --graph {graph_name} --relationships {comma_separated_relationships_list}

For example:

graph_loader.py --graph core --relationships subClassOf,type

This project is licensed under OpenBSD License. License text can be found in the license file.