CPQ Keys is a project that aims to compare existing graph canonization algorithms on their suitability to canonize query graphs of conjunctive path queries (CPQ). This repository aims to provide a framework based on gMark that can be used to easily evaluate and compare various canonization algorithms. More details about the project and codebase can be found in my technical report titled CPQ Keys: a survey of graph canonization algorithms. A list of canonization algorithms set up for evaluation in this repository is given below, information for adding your own algorithms is in a section near the end of this readme.
- Bliss (v0.77, released 2021-02-18)
- Nauty (v2.7 from 2.7r4, released 2022-07-01)
- Nishe (36b97d3, released 2010-07-20)
- Scott (01d26aa, released 2020-05-10)
- Traces (v2.2 from 2.7r4, released 2022-07-01)
Running the project can be done either by using docker or by compiling the project from source. Here docker is primarily provided to offer an easy way to run the project without having to worry about any dependencies. Configuring the settings used to run the evaluation should be done by changing the constants in the main class.
The repository contains a docker configuration that can be used to build an image and run it. The docker image can be built be running the following command:
docker build -t cpqkeys .
You can then run the created image as follows:
docker run --rm cpqkeys
At the moment running the project is only supported on Linux. Docker can be used to run the project on other operating systems. To compile and run the project from source it is first required to install various dependencies. The following dependencies are required:
- Java 8 or higher: required to run the framework, make sure to install the JDK and not only a JRE.
- CMake: required to compile Bliss, Nauty, Nishe, and Traces.
- A compiler for C: e.g.
gcc
is required to compile Nauty and Traces. - A compiler for C++: e.g.
g++
is required to compile Bliss and Nishe. - Python: python 3 is required to run Scott.
On a system with apt
the following command can be used to install all dependencies:
apt install default-jdk cmake g++ gcc python3
After installing all the dependencies the JNI natives for the project can be compiled and installed by going into the CPQKeys folder and running the following script:
./compileNatives.sh
Finally, the project as a whole can be compiled and executed using Gradle by running the following command:
./gradlew run
This repository contain an Eclipse & Gradle project with gMark as the only dependency. Development work can be done using the Eclipse IDE or using any other Gradle compatible IDE. A hosted version of the javadoc for this repository can be found at cpqkeys.docs.roanh.dev and the javadoc for gMark can be found at gmark.docs.roanh.dev. Both documentation pages should be useful when implementing your own algorithms. For compiling and running the project refer to the section on compiling from source.
Adding an algorithm to be evaluated is a fairly straightforward process and essentially comes down to implementing the Algorithm interface and adding it to the list of algorithms in the main class. For more information refer to the technical report or one of the existing algorithm implementations. An example template is also given below. Feel free to submit pull requests to add more algorithms to this repository.
public class MyAlgorithm{
/**
* Algorithm instance, using static instances makes it easier
* to have multiple variants of the same algorithm (e.g., see nauty).
*/
public static final Algorithm INSTANCE = new Algorithm("MyAlgorithm", MyAlgorithm::computeCanon);
/**
* Runs the algorithm on the given input graph.
* @param input The input graph.
* @return An array of time measurements containing in the first
* index the graph transform time, in the second index the
* native setup time (graph construction) and in the third
* index the canonization time. All times are in nanoseconds.
*/
private static long[] computeCanon(Graph<Vertex, Predicate> input){
return new long[]{
0, //setup time in nanoseconds
0, //native setup in nanoseconds
0 //canonization time in nanoseconds
};
}
}
Project development started: 28th of April, 2022.