[Nauty] lexicografic ordered canonical form

Angela Jo Pignotti pignotti at email.arc.nasa.gov
Sat Aug 16 07:06:02 EST 2003


Hi Bill,
	Now, I'm trying to decipher the message I received from the
author of nauty.  It sounds as if I can compare graphs by looking
at the orbits (which node labels change to produce an isomorphism). 
I haven't tried to code this algorithm, but have been trying another
approach. I'd like to try this approach with 2 graphs that are
isomorphic to each other and see if the code can identify this. 

-Angela

>From: Brendan McKay <bdm at cs.anu.edu.au>
>To: nauty-list at cs.anu.edu.au
>Subject: Re: [Nauty] lexicografic ordered canonical form
>Mime-Version: 1.0
>Content-Disposition: inline
>User-Agent: Mutt/1.4i
>X-BeenThere: nauty-list at cs.anu.edu.au
>X-Mailman-Version: 2.0.11
>List-Help: <mailto:nauty-list-request at cs.anu.edu.au?subject=help>
>List-Post: <mailto:nauty-list at cs.anu.edu.au>
>List-Subscribe: <http://cs.anu.edu.au/mailman/listinfo/nauty-list>, 
<mailto:nauty-list-request at cs.anu.edu.au?subject=subscribe>
>List-Id: Announcements and discussion about nauty <nauty-list.cs.anu.edu.au>
>List-Unsubscribe: <http://cs.anu.edu.au/mailman/listinfo/nauty-list>, 
<mailto:nauty-list-request at cs.anu.edu.au?subject=unsubscribe>
>List-Archive: <http://cs.anu.edu.au/pipermail/nauty-list/>
>X-Original-Date: Thu, 7 Aug 2003 17:48:07 +1000
>Date: Thu, 7 Aug 2003 17:48:07 +1000
>X-Keywords: 
>
>* Joost Winne <Joost.Winne at UGent.be> [030807 16:24]:
>> 
>> 
>> >    for each row i+1 compatible with D[i]
>> >       form D[i+1]
>> >       apply nauty to find the orbits of points
>> >           and a canonical order of the points
>> >       reject D[i+1] if point i+1 is not in the same orbit
>> >           as the point which is last in the canonical order
>> 
>> This would mean (after calling nauty for D[i+1]) compare orbits[i+1] with
>> orbits[lab[i+1]] (with getcanon true) ?
>
>Actually orbits[i] and orbits[lab[i]].
> 
>Lets say that I(D) is the set of all designs isomorphic to design D.
>
>The basic explanation: you want to make each isomorphism type I(D[i+1])
>exactly once, by adding a row to some D[i].  Because we are thinking
>about isomorphism types and not labelled designs, the rows are not in a
>special order.  So I(D[i+1]) could in fact be made from i+1 different
>smaller designs (though some of them may be the same due to rows of
>D[i+1] being equivalent).  The main step in isomorph rejection is to
>choose which I(D[i]) you want to make I(D[i+1]) from and reject it if
>you make it in any other way.  The algorithm above says that D[i+1] must
>be made from D[i+1]-row[j], where j is the row that nauty labels last
>(i.e. j = lab[i].  The use of nauty ensures that if you meet another
>design D isomorphic to D[i+1] then the smaller design you want to make
>D from is isomorphic to the smaller design you want to make D[i+1] from.
>
>So when you make D[i+1] you reject it if the row you just added is not
>row j, or, more correctly, if the row you just added is not equivalent
>to row j.
>
>This eliminates the possibility that members of the same I(D[i+1])
>are made (and accepted) from more than one D[i].  This leaves only the
>possibility that several different members of I(D[i+1]) are made and
>accepted from the same D[i].  It is not hard to see that this can only
>happen due to automorphisms of D[i].
>
>Cheers,
>Brendan.
>
>_______________________________________________
>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

Angela Pignotti
Graduate Student Intern
Mission Critical Technologies
located at NASA-Ames Research Ctr.
Bldg. 258 Rm. 201
ph: 415-604-4313





More information about the Nauty mailing list