%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%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.2 final) package for calculating automorphism groups of
(possibly vertex-coloured) graphs and for testing graph isomorphism (see
\cite{Nau90}). To use a function described in this chapter, which depends
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 `canonicalLabelling' components are used, which was the behaviour
in versions of {\GRAPE} before 4.0.  However, since canonical labellings
can depend on the version of {\nauty}, the version of {\GRAPE}, parameter
settings of {\nauty}, 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.

See also "GraphIsomorphism".  For pairwise isomorphism testing of three
or more graphs, see "GraphIsomorphismClassRepresentatives".

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GraphIsomorphismClassRepresentatives}

\>GraphIsomorphismClassRepresentatives( <L> )
\>GraphIsomorphismClassRepresentatives( <L>, <firstunbindcanon> )

Given a list <L> of graphs, this function uses {\nauty} to return a list
consisting of pairwise non-isomorphic elements of <L>, representing all
the isomorphism classes of elements of <L>.

The optional boolean parameter <firstunbindcanon> determines whether
or not the `canonicalLabelling' components of all elements of <L>
are first unbound before proceeding.  If <firstunbindcanon> is `true'
(the default, safe and possibly slower option) then these components
are first unbound.  If <firstunbindcanon> is `false', then any existing
`canonicalLabelling' components of elements of <L> are used.  However,
since canonical labellings can depend on the version of {\nauty}, the
version of {\GRAPE}, parameter settings of {\nauty}, and the compiler
and computer used, you must be sure that if <firstunbindcanon>=`false'
then the `canonicalLabelling' component(s) which may already exist for
elements of <L> were created in exactly the same environment in which
you are presently computing.

\beginexample 
gap> A:=JohnsonGraph(5,2);
rec( isGraph := true, order := 10, 
  group := Group([ (1,5,8,10,4)(2,6,9,3,7), (2,5)(3,6)(4,7) ]), 
  schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 ], 
  adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], representatives := [ 1 ], 
  names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], 
      [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], isSimple := true )
gap> B:=JohnsonGraph(5,3);
rec( isGraph := true, order := 10, 
  group := Group([ (1,7,10,6,3)(2,8,4,9,5), (4,7)(5,8)(6,9) ]), 
  schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 2, 1, 1 ], 
  adjacencies := [ [ 2, 3, 4, 5, 7, 8 ] ], representatives := [ 1 ], 
  names := [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 3, 5 ], 
      [ 1, 4, 5 ], [ 2, 3, 4 ], [ 2, 3, 5 ], [ 2, 4, 5 ], [ 3, 4, 5 ] ], 
  isSimple := true )
gap> R:=GraphIsomorphismClassRepresentatives([A,B,ComplementGraph(A)]);;
gap> Length(R);
2
gap> List(R,VertexDegrees);
[ [ 6 ], [ 3 ] ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GraphIsomorphism}

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

If graphs <gamma1> and <gamma2> are isomorphic, then this function
uses {\nauty} to return an isomorphism from <gamma1> to <gamma2>. This
isomorphism will be a permutation of `[1..<gamma1>.order]' which maps
the edge-set of <gamma1> to that of <gamma2>. If <gamma1> and <gamma2>
are not isomorphic then this function  returns `fail'.

The optional boolean parameter <firstunbindcanon> determines whether or
not the `canonicalLabelling' components of both <gamma1> and <gamma2>
are first unbound before proceeding.  If <firstunbindcanon> is `true'
(the default, safe and possibly slower option) then these components
are first unbound.  If <firstunbindcanon> is `false', then any existing
`canonicalLabelling' components are used.  However, since canonical
labellings can depend on the version of {\nauty}, the version of
{\GRAPE}, parameter settings of {\nauty}, 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.

See also "IsIsomorphicGraph".

\beginexample
gap> A:=JohnsonGraph(5,2);
rec( isGraph := true, order := 10, 
  group := Group([ (1,5,8,10,4)(2,6,9,3,7), (2,5)(3,6)(4,7) ]), 
  schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 ], 
  adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], representatives := [ 1 ], 
  names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], 
      [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], isSimple := true )
gap> B:=JohnsonGraph(5,3);
rec( isGraph := true, order := 10, 
  group := Group([ (1,7,10,6,3)(2,8,4,9,5), (4,7)(5,8)(6,9) ]), 
  schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 2, 1, 1 ], 
  adjacencies := [ [ 2, 3, 4, 5, 7, 8 ] ], representatives := [ 1 ], 
  names := [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 3, 5 ], 
      [ 1, 4, 5 ], [ 2, 3, 4 ], [ 2, 3, 5 ], [ 2, 4, 5 ], [ 3, 4, 5 ] ], 
  isSimple := true )
gap> GraphIsomorphism(A,B);
(3,4,7,8,6,5)
gap> GraphIsomorphism(A,ComplementGraph(A));
fail
\endexample