[Nauty] lexicografic ordered canonical form

[Angela Jo Pignotti]

HI Brendan,
	I need to write a C code interface for nauty.  Is there a set of options 
to find the canonical ordering for a given graph ordering??
	
My thoughts are to build a graph using :
    gv = GRAPHROW(g,0,m);
    EMPTYSET(gv,m);
    ADDELEMENT(gv,2);ADDELEMENT(gv,3);ADDELEMENT(gv,4);
... commands, and then call nauty with a set of 
    options.writeautoms = FALSE;
    options.getcanon = TRUE;
    options.writemarkers = FALSE;
    options.digraph = FALSE;
    options.defaultptn = TRUE;
options that will produce the canonical ordering output.

-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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/x-sun-c-file
Size: 1466 bytes
Desc: automorph.c
Url : http://mailman.anu.edu.au/mailman/private/nauty/attachments/20030816/27990bd9/attachment.bin