dejavu

A probabilistic, parallel graph automorphism and isomorphism solver

dejavu is a software package containing a graph automorphism and isomorphism solver. Both are based on probabilistic strategies and are able to exploit parallelism. However, they use tailored strategies for their respective task.

Download

The version of dejavu which includes the precise experimental setup used for publications is available here. A newer version is available here. Instructions on how to build and run the solvers are included.

Graphs

The solvers read graphs in the DIMACS format. A large library of graphs can be found here. In our benchmarks we used some additional graphs, namely large CFI graphs (by Moritz Lichter) and large complete graphs.

Publications

Img
M. Anders, P. Schweitzer,
Engineering a Fast Probabilistic Isomorphism Test.

2021 Proceedings of the Symposium on Algorithm Engineering and Experiments. ALENEX2021
[arXiv]


Feedback

We are committed to improve upon the provided solver. If you encounter any bugs or other issues, please let us know. However, we want to stress that at this point we consider the tool ''experimental software''. The tool also currently includes POSIX specific code for core affinity management. Thus, parallelization might not work as well as expected under Windows operating systems. We intend to keep maturing the software package. If you are looking for a more robust alternative, we recommend the following excellent, mature tools which have stood the test of time: