[Nauty] Nauty implementation files
Paul T. Darga
pdarga at umich.edu
Thu Jun 30 00:39:02 EST 2005
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
> 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.
You can safely ignore all the CNF and sparsity-specific stuff; the
tutorial is in the middle of the presentation.
More information about the Nauty