[Nauty] Nauty implementation files
Roger Ting
rogermht at cs.mu.OZ.AU
Thu Jun 30 12:56:01 EST 2005
I am having similar experience as well. I supposed we need to understand
group theory properly first before fully understand the
algorithm. I am wondering is there anymore resources available for
beginner who like to understand the algorithm?
Paul T. Darga wrote:
>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
>
>
>_______________________________________________
>This is the nauty mailing list
>Post messages to nauty-list at cs.anu.edu.au
>nauty page: http://cs.anu.edu.au/~bdm/nauty/
>list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list
>
>
>
More information about the Nauty
mailing list