This algorithm tests whether two graphs are isomorphic. The first version of the algorithm is part of the PhD thesis of José Luis López-Presa.
The current version (conauto-2.03 [15-01-2013]) source code is available: conauto-2.03.zip or conauto-2.03.tar.gz This version adds automorphism group computation. The functionalities of this version are described here (paper presented at SEA 2013). Relevant changes since version 2.02: - Now it supports DIMACS graph file format.
- Nodes and bad nodes information is showed for automorphism group computation.
- It is possible to set an explored nodes limit in the search tree (flag '-N=X', where X is the maximum number of explored nodes).
The earlier version (conauto-1.02) source code is available here. An early version of conauto has been included in LEDA 5.1. You can find our benchmark here.The following are papers describing early versions of conauto: José Luis López-Presa, Antonio Fernández. "Graph Isomorphism Testing Without Full Automorphism Group Computation,"
Reports on Systems and Communications, vol. IV, no. 4, may 2004. [PDF] José Luis López-Presa, Antonio Fernández Anta. "Fast Algorithm for Graph Isomorphism Testing," The 8th International Symposium on Experimental Algorithms, SEA 2009,
Dortmund, Germany,
June 2009. [PDF]José Luis López-Presa, Antonio Fernández Anta. "Fast Isomorphism Testing of Graphs with Regularly-Connected Components", ArXiv e-prints 1106.4489, 2011. José Luis López-Presa, Antonio Fernández Anta, Luis Núñez Chiroque. "Conauto-2.0: Fast Isomorphism Testing and Automorphism Group Computation", ArXiv e-prints 1108.1060, 2011. Authors: José Luis López Presa (e-mail), Antonio Fernández Anta, Luis Núñez Chiroque (e-mail) |