[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