[Nauty] Nauty implementation files

[Paul T. Darga]

On Wed, 2005-06-29 at 14:40 +0100, Edward Turner wrote:
> 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).

Surely anybody who has looked at nauty has had that experience.  No
worries.  :)

> 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.

My PowerPoint slides from DAC 2004 provide a description of the
high-level concepts (partition refinement and the search tree), but
don't go into the group-theoretic guts (specifically, the process of
orbit pruning that is essential to good performance when there are a lot
of symmetries).  But what the slides do give you should be enough for a
head start on your implementation, and understanding of the Practical
Graph Isomorphism paper.

http://www.eecs.umich.edu/~pdarga/pub/auto/saucy-dac04.ppt

You can safely ignore all the CNF and sparsity-specific stuff; the
tutorial is in the middle of the presentation.

Paul