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.


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.


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.


Parallel Computation of Combinatorial Symmetries.

Markus Anders, Pascal Schweitzer.
ESA 2021.


Search Problems in Trees with Symmetries: near optimal traversal strategies for individualization-refinement algorithms.

Markus Anders, Pascal Schweitzer.
ICALP 2021.


Engineering a Fast Probabilistic Isomorphism Test.

Markus Anders, Pascal Schweitzer.
ALENEX 2021.



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: