[Nauty] Nauty implementation files

Edward Turner ent03r at ecs.soton.ac.uk
Wed Jun 29 23:42:02 EST 2005

I would like to implement in prolog the algorithm for computing a canonical
form of a graph - to aid in detecting isomorphic graphs (as part of our
symmetry detection module of our ProB Model Checker). We understand that
this implementation language will not be as efficient as the C
implementation of nauty (due to lack of certain data structures), but
believe that the overhead of interfacing prolog with C thousands of times
per second (or more) would outweigh this.

Currently I am reading "Practical Graph Isomorphism", which Brendan McKay
directed me to (thanks!) but am finding it fairly hard going (having a
Formal Methods background). Is there a more practical description of how
this algorithm works that anyone could point me towards? If anyone has any
more help that would be much appreciated.



More information about the Nauty mailing list