[Nauty] Nauty implementation files
Roger Ting
rogermht at cs.mu.OZ.AU
Thu Jun 30 13:49:01 EST 2005
Hi Noah,
Any reference is helpful. Thanks for your response.
Roger
Noah Giansiracusa wrote:
> Roger,
>
> I tried responding to the list earlier, but my message didn't seem to
> get posted. I'm not sure if this will help or not, but I suppose it
> is worth a try. A couple years ago I wrote a term paper on the Nauty
> algorithm (the part about isomorphism detection via canonical
> labeling) for an undergraduate math class (I hadn't had any algebra
> prior to it, so the background shouldn't be too much). I just looked
> at the slides from th previous message and they go much further, but
> don't have as much text.
>
> Anyway, if you are curious you can look at my paper here:
>
> staff.washington.edu/~noahgian/Isomorphism.pdf
>
> Hope this helps!
>
> Noah
>
>
> On Thu, 30 Jun 2005, Roger Ting wrote:
>
>> 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
>>>
>>>
>>
>>
>>
>> _______________________________________________
>> 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