Graph Isomorphism Algorithm conauto

Algorithm conauto for Graph Isomorphism Testing and automorphism group computation

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: 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)