%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%A  cnauty.tex              GRAPE documentation              Leonard Soicher
%
%
%
\def\GRAPE{\sf GRAPE}
\def\nauty{\it nauty}
\def\G{\Gamma}
\def\Aut{{\rm Aut}\,}
\def\x{\times}
\Chapter{Automorphism groups and isomorphism testing for graphs}

{\GRAPE} provides a basic interface to B.D.~McKay{\pif}s {\nauty}
(Version~2.0b5) package for calculating automorphism groups of
(possibly vertex-coloured) graphs and for testing graph isomorphism
(see \cite{Nau90}). To use functions depending on {\nauty}, {\GRAPE}
must be fully installed on a computer running UNIX (see "Installing the
GRAPE Package").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{AutGroupGraph}

\>AutGroupGraph( <gamma> )
\>AutGroupGraph( <gamma>, <colourclasses> )

The first version of this function returns the automorphism group of the
(directed) graph <gamma>, using {\nauty} (this can also be accomplished
by typing `AutomorphismGroup(<gamma>)'). The *automorphism group*
$\Aut(<gamma>)$ of <gamma> is the group consisting of the permutations
of the vertices of <gamma> which preserve the edge-set of <gamma>.

In the second version, <colourclasses> is an ordered partition of
the vertices of <gamma> (into *colour-classes*), and the subgroup
of $\Aut(<gamma>)$ preserving this ordered partition is returned. The
ordered partition should be given as a list of sets, although the last
set in the list may be omitted.  Note that we do not require that adjacent
vertices be in different colour-classes.

\beginexample
gap> gamma := JohnsonGraph(4,2);                   
rec( isGraph := true, order := 6, 
  group := Group([ (1,4,6,3)(2,5), (2,4)(3,5) ]), 
  schreierVector := [ -1, 2, 1, 1, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5 ] ], 
  representatives := [ 1 ], 
  names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ], 
  isSimple := true )
gap> Size(AutGroupGraph(gamma)); 
48
gap> Size(AutGroupGraph(gamma,[[1,2,3],[4,5,6]])); 
6
gap> Size(AutGroupGraph(gamma,[[1,6]]));          
16
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsIsomorphicGraph}

\>IsIsomorphicGraph( <gamma1>, <gamma2> )
\>IsIsomorphicGraph( <gamma1>, <gamma2>, <firstunbindcanon> )

This boolean function uses the {\nauty} package to test whether graphs
<gamma1> and <gamma2> are isomorphic. The value `true' is returned if
and only if the graphs are isomorphic (as directed, uncoloured
graphs).

The optional boolean parameter <firstunbindcanon> determines whether or
not the `canonicalLabelling' components of both <gamma1> and <gamma2>
are first unbound before testing isomorphism.  If <firstunbindcanon>
is `true' (the default, safe and possibly slower option) then these
components are first unbound.  If <firstunbindcanon> is `false', then any
existing canonical labelling is used, which was the behaviour in versions
of {\GRAPE} before 4.0.  However, since canonical labellings can depend on
the version of {\nauty} (currently 2.0b5), certain parameters of {\nauty}
(always set the same for a given graph by {\GRAPE}~4.1), and the compiler
and computer used, you must be sure that if <firstunbindcanon>=`false'
then the `canonicalLabelling' component(s) which may already exist
for <gamma1> or <gamma2> were created in exactly the same environment
in which you are presently computing. We remark that {\GRAPE}~4.1 now
sets {\nauty} parameters differently than before for non-simple graphs
(and so canonical labellings may be different than before), in order to
avoid a performance problem with certain sparse directed graphs.

\beginexample
gap> gamma := JohnsonGraph(7,4);;
gap> delta := JohnsonGraph(7,3);;
gap> IsIsomorphicGraph( gamma, delta );
true 
\endexample
