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
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:
![[logo of the department of CS]](/en/logos/logo_fbi_167x60.png){kind=logo}
