%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  grape.tex                GAP documentation                Leonard Soicher
%%
%A  @(#)$Id: grape.tex,v 3.7 1994/07/06 09:03:31 vfelsch Rel $
%%
%Y  Copyright 1993-1995,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
%%
%H  $Log: grape.tex,v $
%H  Revision 3.7  1994/07/06  09:03:31  vfelsch
%H  including final changes for version 3.4
%H
%H  Revision 3.6  1994/07/01  08:21:12  fceller
%H  'Components' is now called 'ConnectedComponents'
%H
%H  Revision 3.5  1994/06/17  19:02:25  vfelsch
%H  examples adjusted to version 3.4
%H
%H  Revision 3.4  1994/06/10  04:41:46  vfelsch
%H  updated examples
%H
%H  Revision 3.3  1993/07/20  11:07:31  fceller
%H  final 3.3 version
%H
%H  Revision 3.2  1993/05/28  13:39:26  gap
%H  Initial revision
%%
\def\GRAPE{\sf GRAPE}
\def\nauty{\it nauty}
\def\G{\Gamma}
\def\Aut{{\rm Aut}\,}
\def\x{\times}
\Chapter{Grape}

This chapter describes the main functions  of the {\GRAPE}  (Version~2.2)
share  library  package  for  computing  with  graphs  and  groups.   All
functions  described  here are  written entirely in  the {\GAP} language,
except for the  automorphism  group and  isomorphism  testing  functions,
which   make   use   of   B.~McKay\'s   {\nauty}   (Version~1.7)  package
\cite{Nau90}.

{\GRAPE}  is primarily designed  for  the  construction and   analysis of
graphs  related  to permutation groups  and finite geometries.    Special
emphasis is placed on    the determination of regularity  properties  and
subgraph  structure.  The  {\GRAPE}  philosophy is  that a graph $\Gamma$
always  comes together with  a known  subgroup $G$ of $\Aut(\Gamma)$, and
that $G$ is  used to reduce  the  storage and CPU-time  requirements  for
calculations with $\Gamma$ (see \cite{Soi91}).   Of course $G$ may be the
trivial group, and in this  case {\GRAPE}  algorithms will  perform  more
slowly than strictly combinatorial  algorithms (although this degradation
in performance is hopefully never more than a fixed constant factor).

In general {\GRAPE}  deals with directed graphs which may have loops  but
have  no multiple edges. However, many {\GRAPE}  functions  only work for
*simple* graphs (i.e. no  loops, and whenever $[x,y]$ is an edge then  so
is $[y,x]$), but these functions will check if an input graph is simple.

In {\GRAPE},  a graph  $gamma$  is stored as   a  record,  with mandatory
components   'isGraph',    'order',        'group',     'schreierVector',
'representatives', and  'adjacencies'.   Usually, the  user  need  not be
aware  of  this record  structure,  and is  strongly  advised only to use
{\GRAPE} functions to construct and modify graphs.

The 'order' component  contains the number  of vertices of  $gamma$.  The
vertices of $gamma$  are always $1,..,gamma.order$, but  they may also be
given *names*, either  by  a  user or by  a function constructing a graph
(e.g.    'InducedSubgraph', 'BipartiteDouble',  'QuotientGraph').     The
'names' component, if  present,  records these  names.  If  the   'names'
component is  not present (the user may,  for  example, choose to  unbind
it),   then the names are taken   to be $1,...,gamma.order$.  The 'group'
component   records the  the  {\GAP}   permutation group associated  with
$gamma$  (this  group  must  be  a subgroup  of     $\Aut(gamma)$).   The
'representatives' component records a set  of  orbit representatives  for
$gamma.group$  on  the vertices  of  $gamma$, with $gamma.adjacencies[i]$
being the  set of vertices  adjacent to  $gamma.representatives[i]$.  The
only mandatory component  which may   change once  a graph is   initially
constructed  is 'adjacencies' (when  an  edge  orbit of $gamma.group$  is
added to, or removed from, $gamma$).  A graph  record  may also have some
of      the     optional    components   'isSimple',    'autGroup',   and
'canonicalLabelling', which record information about that graph.

{\GRAPE} has the  ability to make use of certain random group theoretical
algorithms, which can result  in time and store savings. The use of these
random methods may  be switched on and off by the global boolean variable
'GRAPE\_RANDOM',  whose  default  value  is  'false' (random  methods not
used).   Even if random methods are  used,  no function  described  below
depends  on the correctness of such a randomly computed result. For these
functions  the use of these random  methods only  influences the time and
store taken. All global variables used by {\GRAPE} start with 'GRAPE\_'.

The user who is interested in knowing more about the {\GRAPE} system, and
its advanced use,  should  consult  \cite{Soi91} and the {\GRAPE}  source
code.

Before using any of the functions described in this chapter you must load
the package by calling the statement

|    gap> RequirePackage( "grape" );

    Loading  GRAPE 2.2  (GRaph Algorithms using PErmutation groups),
    by L.H.Soicher@qmw.ac.uk. |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Functions to construct and modify graphs}

The  following sections describe  the functions  used to construct and
modify graphs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Graph}

'Graph( <G>, <L>, <act>, <rel> )'\\
'Graph( <G>, <L>, <act>, <rel>, <invt> )'

This  is the most  general  and  useful  way  of constructing a graph  in
{\GRAPE}.

First  suppose that the optional  boolean parameter <invt> is  unbound or
has value 'false'.  Then <L> should be a list of elements of a set $S$ on
which the group <G> acts (*operates* in {\GAP} language), with the action
given by  the function <act>.   The parameter <rel>   should be a boolean
function defining a <G>-invariant  relation on $S$ (so  that for  $g$  in
<G>,     $x,y$      in    $S$,     $<rel>(x,y)$   if     and    only   if
$<rel>(<act>(x,g),<act>(y,g))$).  Then  function 'Graph'  returns a graph
$gamma$ which has as vertex names
\begin{center}
    'Concatenation( Orbits( <G>, <L>, <act> ) )'
\end{center}
(the concatenation of the  distinct orbits  of the elements  in <L> under
<G>), and for vertices $v,w$  of $gamma$, $[v,w]$  is an edge if and only
if
\begin{center}
    '<rel>( VertexName( <gamma>, <v> ), VertexName( <gamma>, <w> ) )'
\end{center}

Now if the  parameter <invt> exists  and  has value 'true',  then  it  is
assumed  that <L> is invariant  under <G> with respect  to  action <act>.
Then the function 'Graph' behaves as above,  except that the vertex names
of $gamma$ become (a copy of) <L>.

The group associated with the graph $gamma$ returned is  the image of <G>
acting via <act> on $gamma.names$.

For example, suppose you have an $n\x n$ adjacency matrix $A$ for a graph
$X$, so that the vertices of $X$ are $\{1,\ldots,n\}$, and  $[i,j]$ is an
edge of $X$  if and only  if $A[i][j]=1$.  Suppose  also that  $G\le \Aut
(X)$ ($G$ may be trivial).  Then you can make a {\GRAPE} graph isomorphic
to $X$  via 'Graph( G,  [1..n], OnPoints, function(x,y) return A[x][y]=1;
end, true );'

|    gap> A := [[0,1,0],[1,0,0],[0,0,1]];
    [ [ 0, 1, 0 ], [ 1, 0, 0 ], [ 0, 0, 1 ] ]
    gap> G := Group( (1,2) );
    Group( (1,2) )
    gap> Graph( G, [1..3], OnPoints,
    >           function(x,y) return A[x][y]=1; end,
    >           true );
    rec(
      isGraph := true,
      order := 3,
      group := Group( (1,2) ),
      schreierVector := [ -1, 1, -2 ],
      adjacencies := [ [ 2 ], [ 3 ] ],
      representatives := [ 1, 3 ],
      names := [ 1 .. 3 ] ) |

We now construct the Petersen graph.

|    gap> Petersen := Graph( SymmetricGroup(5), [[1,2]], OnSets,
    >                 function(x,y) return Intersection(x,y)=[]; end );
    rec(
      isGraph := true,
      order := 10,
      group := Group( ( 1, 2)( 6, 8)( 7, 9), ( 1, 3)( 4, 8)( 5, 9),
        ( 2, 4)( 3, 6)( 9,10), ( 2, 5)( 3, 7)( 8,10) ),
      schreierVector := [ -1, 1, 2, 3, 4, 3, 4, 2, 2, 4 ],
      adjacencies := [ [ 8, 9, 10 ] ],
      representatives := [ 1 ],
      names := [ [ 1, 2 ], [ 2, 5 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ],
          [ 1, 3 ], [ 1, 4 ], [ 3, 5 ], [ 4, 5 ], [ 3, 4 ] ] ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{EdgeOrbitsGraph}

'EdgeOrbitsGraph( <G>, <E> )' \\
'EdgeOrbitsGraph( <G>, <E>, <n> )'

This is a common way of constructing a graph in {\GRAPE}.

This   function   returns   the   (directed)   graph  with   vertex   set
$\{1,...,<n>\}$,  edge  set  $\cup_{e\in <E>}\, e^<G>$,   and  associated
(permutation) group <G>, which  must  act naturally  on  $\{1,...,<n>\}$.
The  parameter  <E>  should  be a  list  of edges (lists of  length 2  of
vertices), although a  singleton edge  will be understood as an edge list
of length 1.  The parameter <n>  may be omitted, in which case the number
of vertices is the largest point moved by a generator of <G>.

Note  that <G> may  be  the trivial permutation group  ('Group( () )'  in
{\GAP}  notation), in which case  the  (directed) edges  of  <gamma>  are
simply those in the list <E>.

|    gap> EdgeOrbitsGraph( Group((1,3),(1,2)(3,4)), [[1,2],[4,5]], 5 );
    rec(
      isGraph := true,
      order := 5,
      group := Group( (1,3), (1,2)(3,4) ),
      schreierVector := [ -1, 2, 1, 2, -2 ],
      adjacencies := [ [ 2, 4, 5 ], [  ] ],
      representatives := [ 1, 5 ],
      isSimple := false ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{NullGraph}

'NullGraph( <G> )' \\
'NullGraph( <G>, <n> )'

This function  returns the  null  graph on <n>  vertices, with associated
(permutation) group <G>.  The parameter <n> may be omitted, in which case
the number of vertices is the largest point moved by a generator of <G>.

See also "IsNullGraph".

|    gap> NullGraph( Group( (1,2,3) ), 4 );
    rec(
      isGraph := true,
      order := 4,
      group := Group( (1,2,3) ),
      schreierVector := [ -1, 1, 1, -2 ],
      adjacencies := [ [  ], [  ] ],
      representatives := [ 1, 4 ],
      isSimple := true ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CompleteGraph}

'CompleteGraph( G )' \\
'CompleteGraph( G, <n> )' \\
'CompleteGraph( G, <n>, <mustloops> )'

This  function returns a complete graph  on <n> vertices with  associated
(permutation) group <G>. The parameter <n> may be  omitted, in which case
the number of vertices is the largest point moved by a  generator of <G>.
The   optional  boolean  parameter  <mustloops>  determines whether   the
complete graph has all loops present  or no loops (default\:\ 'false' (no
loops)).

See also "IsCompleteGraph".

|    gap> CompleteGraph( Group( (1,2,3), (1,2) ) );
    rec(
      isGraph := true,
      order := 3,
      group := Group( (1,2,3), (1,2) ),
      schreierVector := [ -1, 1, 1 ],
      adjacencies := [ [ 2, 3 ] ],
      representatives := [ 1 ],
      isSimple := true ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{JohnsonGraph}

'JohnsonGraph( <n>, <e> )'

This function  returns a graph  $gamma$ isomorphic to  the Johnson graph,
whose vertices are the <e>-subsets of $\{1,...,<n>\}$, with $x$ joined to
$y$ if  and only if $\|x  \cap y\| = <e>-1$.   The group  associated with
$gamma$  is image  of   the the symmetric   group $S_<n>$  acting  on the
<e>-subsets of $\{1,\ldots,<n>\}$.

|    gap> JohnsonGraph(5,3);
    rec(
      isGraph := true,
      order := 10,
      group := Group( ( 1, 8)( 2, 9)( 4,10), ( 1, 5)( 2, 6)( 7,10),
        ( 1, 3)( 4, 6)( 7, 9), ( 2, 3)( 4, 5)( 7, 8) ),
      schreierVector := [ -1, 4, 3, 4, 2, 3, 4, 1, 3, 2 ],
      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 ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{AddEdgeOrbit}

'AddEdgeOrbit( <gamma>, <e> )' \\
'AddEdgeOrbit( <gamma>, <e>, <H> )'

This procedure adds the edge orbit $<e>^<gamma.group>$ to the edge set of
graph <gamma>.   The  parameter  <e> must be a  sequence  of length 2  of
vertices of  <gamma>.  If the optional third parameter <H>  is given then
it is assumed that $<e>[2]$ has the same orbit under <H> as it does under
the  stabilizer  in <gamma.group>  of $<e>[1]$,  and  this knowledge  can
greatly speed up the procedure.

Note that if <gamma.group> is trivial then this procedure simply adds the
single edge <e> to <gamma>.

|    gap> gamma := NullGraph( Group( (1,3), (1,2)(3,4) ) );
    rec(
      isGraph := true,
      order := 4,
      group := Group( (1,3), (1,2)(3,4) ),
      schreierVector := [ -1, 2, 1, 2 ],
      adjacencies := [ [  ] ],
      representatives := [ 1 ],
      isSimple := true )
    gap> AddEdgeOrbit( gamma, [4,3] );
    gap> gamma;
    rec(
      isGraph := true,
      order := 4,
      group := Group( (1,3), (1,2)(3,4) ),
      schreierVector := [ -1, 2, 1, 2 ],
      adjacencies := [ [ 2, 4 ] ],
      representatives := [ 1 ],
      isSimple := true ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{RemoveEdgeOrbit}

'RemoveEdgeOrbit( <gamma>, <e> )' \\
'RemoveEdgeOrbit( <gamma>, <e>, <H> )'

This procedure removes the  edge  orbit $<e>^<gamma.group>$ from the edge
set of the graph <gamma>.  The parameter <e> must be a sequence of length
2 of vertices of <gamma>, but  if <e> is not an edge of <gamma> then this
procedure has no  effect. If the optional  third  parameter  <H> is given
then  it is assumed that $<e>[2]$ has the same orbit under <H> as it does
under the stabilizer in <gamma.group> of $<e>[1]$, and this knowledge can
greatly speed up the procedure.

|    gap> gamma := CompleteGraph( Group( (1,3), (1,2)(3,4) ) );
    rec(
      isGraph := true,
      order := 4,
      group := Group( (1,3), (1,2)(3,4) ),
      schreierVector := [ -1, 2, 1, 2 ],
      adjacencies := [ [ 2, 3, 4 ] ],
      representatives := [ 1 ],
      isSimple := true )
    gap> RemoveEdgeOrbit( gamma, [4,3] );
    gap> gamma;
    rec(
      isGraph := true,
      order := 4,
      group := Group( (1,3), (1,2)(3,4) ),
      schreierVector := [ -1, 2, 1, 2 ],
      adjacencies := [ [ 3 ] ],
      representatives := [ 1 ],
      isSimple := true ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{AssignVertexNames}

'AssignVertexNames( <gamma>, <names> )'

This function  allows  the  user to  give  new names  to the  vertices of
<gamma>, by specifying a list <names> of vertex names for the vertices of
<gamma>, such that $<names>[i]$ contains the user\'s name for  the $i$-th
vertex of <gamma>.

A copy of <names> is assigned to <gamma.names>. See also "VertexName".

|    gap> gamma := NullGraph( Group(()), 3 );
    rec(
      isGraph := true,
      order := 3,
      group := Group( () ),
      schreierVector := [ -1, -2, -3 ],
      adjacencies := [ [  ], [  ], [  ] ],
      representatives := [ 1, 2, 3 ],
      isSimple := true )
    gap> AssignVertexNames( gamma, ["a","b","c"] );
    gap> gamma;
    rec(
      isGraph := true,
      order := 3,
      group := Group( () ),
      schreierVector := [ -1, -2, -3 ],
      adjacencies := [ [  ], [  ], [  ] ],
      representatives := [ 1, 2, 3 ],
      isSimple := true,
      names := [ "a", "b", "c" ] ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Functions to inspect graphs, vertices and edges}

The next sections describe  functions to  inspect  graphs,  vertices  and
edges.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsGraph}

'IsGraph( <obj> )'

This boolean function  returns 'true' if  and only if <obj>, which can be
an object of arbitrary type, is a graph.

|    gap> IsGraph( 1 );
    false
    gap> IsGraph( JohnsonGraph( 3, 2 ) );
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{OrderGraph}

'OrderGraph( <gamma> )'

This  function returns  the  number  of  vertices  (order)  of the  graph
<gamma>.

|    gap> OrderGraph( JohnsonGraph( 4, 2 ) );
    6 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsVertex}

'IsVertex( <gamma>, <v> )'

This  boolean  function returns 'true' if  and  only if  <v> is vertex of
<gamma>.

|    gap> gamma := JohnsonGraph( 3, 2 );;
    gap> IsVertex( gamma, 1 );
    true
    gap> IsVertex( gamma, 4 );
    false |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{VertexName}

'VertexName( <gamma>, <v> )'

This function returns (a copy of) the name of the vertex <v> of <gamma>.

See also "AssignVertexNames".

|    gap> VertexName( JohnsonGraph(4,2), 6 );
    [ 3, 4 ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Vertices}

'Vertices( <gamma> )'

This  function returns  the  vertex  set $\{1,...,<gamma.order>\}$ of the
graph <gamma>.

|    gap> Vertices( JohnsonGraph( 4, 2 ) );
    [ 1 .. 6 ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{VertexDegree}

'VertexDegree( <gamma>, <v> )'

This  function  returns the  (out)degree  of the vertex <v> of  the graph
<gamma>.

|    gap> VertexDegree( JohnsonGraph( 3, 2 ), 1 );
    2 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{VertexDegrees}

'VertexDegrees( <gamma> )'

This function returns the set of vertex (out)degrees for the graph
<gamma>.

|    gap> VertexDegrees( JohnsonGraph( 4, 2 ) );
    [ 4 ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsLoopy}

'IsLoopy( <gamma> )'

This boolean function returns 'true' if and only if the graph <gamma> has
a *loop*, that is, an edge of the form $[x,x]$.

|    gap> IsLoopy( JohnsonGraph( 4, 2 ) );
    false
    gap> IsLoopy( CompleteGraph( Group( (1,2,3), (1,2) ), 3 ) );
    false
    gap> IsLoopy( CompleteGraph( Group( (1,2,3), (1,2) ), 3, true ) );
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsSimpleGraph}

'IsSimpleGraph( <gamma> )'

This boolean function returns 'true' if and  only if the graph <gamma> is
*simple*, that is, has no loops and whenever $[x,y]$  is an edge  then so
is $[y,x]$.

|    gap> IsSimpleGraph( CompleteGraph( Group( (1,2,3) ), 3 ) );
    true
    gap> IsSimpleGraph( CompleteGraph( Group( (1,2,3) ), 3, true ) );
    false |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Adjacency}

'Adjacency( <gamma>, <v> )'

This function returns (a copy of) the set of vertices of <gamma> adjacent
to vertex <v>.  A vertex $w$ is *adjacent*  to <v> if and only if $[v,w]$
is an edge.

|    gap> Adjacency( JohnsonGraph( 4, 2 ), 1 );
    [ 2, 3, 4, 5 ]
    gap> Adjacency( JohnsonGraph( 4, 2 ), 6 );
    [ 2, 3, 4, 5 ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsEdge}

'IsEdge( <gamma>, <e> )'

This  boolean function returns 'true' if and  only  if <e> is an  edge of
<gamma>.

|    gap> IsEdge( JohnsonGraph( 4, 2 ), [ 1, 2 ] );
    true
    gap> IsEdge( JohnsonGraph( 4, 2 ), [ 1, 6 ] );
    false |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DirectedEdges}

'DirectedEdges( <gamma> )'

This function  returns the  set of directed  (ordered) edges of the graph
<gamma>.

See also "UndirectedEdges".

|    gap> gamma := JohnsonGraph( 3, 2 );
    rec(
      isGraph := true,
      order := 3,
      group := Group( (1,3), (1,2) ),
      schreierVector := [ -1, 2, 1 ],
      adjacencies := [ [ 2, 3 ] ],
      representatives := [ 1 ],
      names := [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ],
      isSimple := true )
    gap> DirectedEdges( gamma );
    [ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]
    gap> UndirectedEdges( gamma );
    [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UndirectedEdges}

'UndirectedEdges( <gamma> )'

This function returns the set of undirected (unordered) edges of <gamma>,
which must be a simple graph.

See also "DirectedEdges".

|    gap> gamma := JohnsonGraph( 3, 2 );
    rec(
      isGraph := true,
      order := 3,
      group := Group( (1,3), (1,2) ),
      schreierVector := [ -1, 2, 1 ],
      adjacencies := [ [ 2, 3 ] ],
      representatives := [ 1 ],
      names := [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ],
      isSimple := true )
    gap> DirectedEdges( gamma );
    [ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]
    gap> UndirectedEdges( gamma );
    [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Distance}

'Distance( <gamma>, <X>, <Y> )' \\
'Distance( <gamma>, <X>, <Y>, <G> )'

This  function returns  the  distance  from <X>  to <Y>  in  <gamma>. The
parameters <X>  and <Y> may  be vertices or  vertex  sets. We  define the
*distance*  $d(<X>,<Y>)$ from  <X> to  <Y>  to be the minimum length of a
(directed) path joining a vertex of <X> to a vertex of <Y> if such a path
exists, and $-1$ otherwise.

The  optional parameter <G>,  if present, is assumed to  be a subgroup of
$\Aut(<gamma>)$ fixing  <X>  setwise.  Including  such a <G> can speed up
the function.

|    gap> Distance( JohnsonGraph(4,2), 1, 6 );
    2
    gap> Distance( JohnsonGraph(4,2), 1, 5 );
    1 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Diameter}

'Diameter( <gamma> )'

This  function  returns the  diameter of <gamma>.  A diameter of $-1$  is
returned if <gamma> is not (strongly) connected.

|    gap> Diameter( JohnsonGraph( 5, 3 ) );
    2
    gap> Diameter( JohnsonGraph( 5, 4 ) );
    1 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Girth}

'Girth( <gamma> )'

This function returns the girth of <gamma>, which must be a simple graph.
A girth of $-1$ is returned if <gamma> is a forest.

|    gap> Girth( JohnsonGraph( 4, 2 ) );
    3 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsConnectedGraph}

'IsConnectedGraph( <gamma> )'

This boolean function returns 'true' if and only if <gamma> is (strongly)
*connected*, i.e. if there is a (directed) path from $x$ to $y$ for every
pair of vertices $x,y$ of <gamma>.

|    gap> IsConnectedGraph( JohnsonGraph(4,2) );
    true
    gap> IsConnectedGraph( NullGraph(SymmetricGroup(4)) );
    false |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsBipartite}

'IsBipartite( <gamma> )'

This boolean function  returns 'true' if  and  only if the graph <gamma>,
which  must  be simple, is *bipartite*, i.e.  if  the vertex  set can  be
partitioned into two null  graphs  (which  are  called  *bicomponents* or
*parts* of <gamma>).

See also "Bicomponents", "EdgeGraph", and "BipartiteDouble".

|    gap> gamma := JohnsonGraph(4,2);
    rec(
      isGraph := true,
      order := 6,
      group := Group( (1,5)(2,6), (1,3)(4,6), (2,3)(4,5) ),
      schreierVector := [ -1, 3, 2, 3, 1, 2 ],
      adjacencies := [ [ 2, 3, 4, 5 ] ],
      representatives := [ 1 ],
      names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ],
          [ 3, 4 ] ],
      isSimple := true )
    gap> IsBipartite(gamma);
    false
    gap> delta := BipartiteDouble(gamma);
    rec(
      isGraph := true,
      order := 12,
      group := Group( ( 1, 5)( 2, 6)( 7,11)( 8,12), ( 1, 3)( 4, 6)( 7, 9)
        (10,12), ( 2, 3)( 4, 5)( 8, 9)(10,11), ( 1, 7)( 2, 8)( 3, 9)
        ( 4,10)( 5,11)( 6,12) ),
      schreierVector := [ -1, 3, 2, 3, 1, 2, 4, 4, 4, 4, 4, 4 ],
      adjacencies := [ [ 8, 9, 10, 11 ] ],
      representatives := [ 1 ],
      isSimple := true,
      names := [ [ [ 1, 2 ], "+" ], [ [ 1, 3 ], "+" ], [ [ 1, 4 ], "+" ],
          [ [ 2, 3 ], "+" ], [ [ 2, 4 ], "+" ], [ [ 3, 4 ], "+" ],
          [ [ 1, 2 ], "-" ], [ [ 1, 3 ], "-" ], [ [ 1, 4 ], "-" ],
          [ [ 2, 3 ], "-" ], [ [ 2, 4 ], "-" ], [ [ 3, 4 ], "-" ] ] )
    gap> IsBipartite(delta);
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsNullGraph}

'IsNullGraph( <gamma> )'

This boolean function returns 'true' if and only if the graph <gamma> has
no edges.

See also "NullGraph".

|    gap> IsNullGraph( CompleteGraph( Group(()), 3 ) );
    false
    gap> IsNullGraph( CompleteGraph( Group(()), 1 ) );
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsCompleteGraph}

'IsCompleteGraph( <gamma> )' \\
'IsCompleteGraph( <gamma>, <mustloops> )'

This boolean function returns  'true' if and only if the graph <gamma> is
a complete graph.  The optional boolean  parameter <mustloops> determines
whether all loops must be present for <gamma> to be considered a complete
graph (default\:\ 'false' (loops are ignored)).

See also "CompleteGraph".

|    gap> IsCompleteGraph( NullGraph( Group(()), 3 ) );
    false
    gap> IsCompleteGraph( NullGraph( Group(()), 1 ) );
    true
    gap> IsCompleteGraph( CompleteGraph(SymmetricGroup(3)), true );
    false |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Functions to determine regularity properties of graphs}

The  following  sections   describe  functions  to  determine  regularity
properties of graphs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsRegularGraph}

'IsRegularGraph( <gamma> )'

This boolean function returns 'true'  if and only if the graph <gamma> is
(out)regular.

|    gap> IsRegularGraph( JohnsonGraph(4,2) );
    true
    gap> IsRegularGraph( EdgeOrbitsGraph(Group(()),[[1,2]],2) );
    false |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{LocalParameters}

'LocalParameters( <gamma>, <V> )' \\
'LocalParameters( <gamma>, <V>, <G> )'

This function determines any  *local parameters*  $c_i(<V>)$, $a_i(<V>)$,
or $b_i(<V>)$ that simple, connected  <gamma>  may have, with respect  to
the singleton vertex or vertex set <V>  (see \cite{BCN89}).  The function
returns   a     list    of   triples,   whose      $i$-th   element    is
$[c_{i-1}(<V>),a_{i-1}(<V>),b_{i-1}(<V>)]$,  except  that  if some  local
parameter does not exist then a $-1$ is  put in its place.  This function
can  be used  to determine whether  a given subset  of the  vertices of a
graph is a distance-regular code in that graph.

The optional parameter <G>, if  present, is  assumed to  be a subgroup of
$\Aut(<gamma>)$ fixing <V> (setwise).  Including such a  <G> can speed up
the function.

|    gap> LocalParameters( JohnsonGraph(4,2), 1 );
    [ [ 0, 0, 4 ], [ 1, 2, 1 ], [ 4, 0, 0 ] ]
    gap> LocalParameters( JohnsonGraph(4,2), [1,6] );
    [ [ 0, 0, 4 ], [ 2, 2, 0 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GlobalParameters}

'GlobalParameters( <gamma> )'

In a similar   way  to 'LocalParameters'  (see "LocalParameters"),   this
function   determines the *global  parameters*  $c_i,a_i,b_i$  of simple,
connected  <gamma> (see \cite{BCN89}).    The  nonexistence of  a  global
parameter is denoted by $-1$.

|    gap> gamma := JohnsonGraph(4,2);;
    gap> GlobalParameters( gamma );
    [ [ 0, 0, 4 ], [ 1, 2, 1 ], [ 4, 0, 0 ] ]
    gap> GlobalParameters( BipartiteDouble(gamma) );
    [ [ 0, 0, 4 ], [ 1, 0, 3 ], [ -1, 0, -1 ], [ 4, 0, 0 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsDistanceRegular}

'IsDistanceRegular( <gamma> )'

This  boolean   function  returns  'true'  if  and  only  if  <gamma>  is
distance-regular,  i.e. <gamma>  is simple, connected, and  all  possible
global parameters exist.

|    gap> gamma := JohnsonGraph(4,2);;
    gap> IsDistanceRegular( gamma );
    true
    gap> IsDistanceRegular( BipartiteDouble(gamma) );
    false |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CollapsedAdjacencyMat}

'CollapsedAdjacencyMat( <G>, <gamma> )'

This function returns  the  collapsed adjacency matrix for <gamma>, where
the  collapsing group  is <G>.  It is assumed  that <G> is  a subgroup of
$\Aut(<gamma>)$.

The $(i,j)$-entry of the collapsed adjacency matrix  equals the number of
edges in  $\{ [x,y] \| y \in j$-th <G>-orbit $\}$, where  $x$ is  a fixed
vertex in the $i$-th <G>-orbit.

See also "OrbitalGraphIntersectionMatrices".

|    gap> gamma := JohnsonGraph(4,2);;
    gap> G := Stabilizer( gamma.group, 1 );;
    gap> CollapsedAdjacencyMat( G, gamma );
    [ [ 0, 4, 0 ], [ 1, 2, 1 ], [ 0, 4, 0 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{OrbitalGraphIntersectionMatrices}

'OrbitalGraphIntersectionMatrices( <G> )' \\
'OrbitalGraphIntersectionMatrices( <G>, <H> )'

This  function returns a sequence of intersection  matrices corresponding
to  the orbital  graphs for the  transitive  permutation  group  <G>.  An
intersection matrix for an  orbital  graph <gamma> for <G> is a collapsed
adjacency matrix of <gamma>,  collapsed with respect to the stabilizer in
<G> of a point.

If  the optional  parameter  <H> is  given then it  is assumed to be  the
stabilizer  in <G> of the point 1,  and this information can speed up the
function.

See also "CollapsedAdjacencyMat".

|    gap> OrbitalGraphIntersectionMatrices( SymmetricGroup(7) );
    [ [ [ 1, 0 ], [ 0, 1 ] ], [ [ 0, 6 ], [ 1, 5 ] ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Some special vertex subsets of a graph}

The following sections describe functions for special vertex subsets of a
graph.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ConnectedComponent}

'ConnectedComponent( <gamma>, <v> )'

This function  returns the set  of all vertices  in <gamma> which  can be
reached by a path starting at the vertex  <v>.  The graph <gamma> must be 
simple.

See also "ConnectedComponents".

|    gap> ConnectedComponent( NullGraph( Group((1,2)) ), 2 );
    [ 2 ]
    gap> ConnectedComponent( JohnsonGraph(4,2), 2 );
    [ 1, 2, 3, 4, 5, 6 ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ConnectedComponents}

'ConnectedComponents( <gamma> )'

This  function returns  a  list  of  the  vertex  sets  of  the connected
components of <gamma>, which must be a simple graph.

See also "ConnectedComponent".

|    gap> ConnectedComponents( NullGraph( Group((1,2,3,4)) ) );
    [ [ 1 ], [ 2 ], [ 3 ], [ 4 ] ]
    gap> ConnectedComponents( JohnsonGraph(4,2) );
    [ [ 1, 2, 3, 4, 5, 6 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Bicomponents}

'Bicomponents( <gamma> )'

If the graph  <gamma>, which must be simple,  is bipartite, this function
returns  a length 2 list  of  bicomponents or parts of <gamma>, otherwise
the empty list is returned.

Note\:\ if  <gamma>  is  not  connected  then  its  bicomponents  are not
necessarily uniquely determined.  See also "IsBipartite".

|    gap> Bicomponents( NullGraph(SymmetricGroup(4)) );
    [ [ 1, 2, 3 ], [ 4 ] ]
    gap> Bicomponents( JohnsonGraph(4,2) );
    [  ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DistanceSet}

'DistanceSet( <gamma>, <distances>, <V> )' \\
'DistanceSet( <gamma>, <distances>, <V>, <G> )'

This function  returns the  set  of  vertices $w$ of  <gamma>,  such that
$d(<V>,w)$ is in <distances> (a list or singleton distance).

The optional  parameter <G>, if  present, is assumed to be  a subgroup of
$\Aut(<gamma>)$  fixing <V> setwise.  Including  such a <G> can speed  up
the function.

|    gap> DistanceSet( JohnsonGraph(4,2), 1, [1,6] );
    [ 2, 3, 4, 5 ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Layers}

'Layers( <gamma>, <V> )' \\
'Layers( <gamma>, <V>, <G> )'

This function returns a list whose $i$-th element is  the set of vertices
of  <gamma> at distance  $i-1$  from <V>, which may be a vertex  set or a
singleton vertex.

The optional  parameter  <G>, if present, is assumed to  be a subgroup of
$\Aut(<gamma>)$ which fixes <V>  setwise.  Including such a <G> can speed
up the function.

|    gap> Layers( JohnsonGraph(4,2), 6 );
    [ [ 6 ], [ 2, 3, 4, 5 ], [ 1 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IndependentSet}

'IndependentSet( <gamma> )' \\
'IndependentSet( <gamma>, <indset> )' \\
'IndependentSet( <gamma>, <indset>, <forbidden> )'

Returns a  (hopefully  large)  independent set  (coclique) of  the  graph
<gamma>, which must be simple.  At present, a *greedy* algorithm is used.
The returned independent set will  contain  the (assumed) independent set
<indset>  (default\:\ |[]|),  and  not contain any element of <forbidden>
(default\:\ |[]|, in which case the returned independent set is maximal).
An  error is  signalled  if  <indset>  and  <forbidden>  have non-trivial
intersection.

|    gap> IndependentSet( JohnsonGraph(4,2), [3] );
    [ 3, 4 ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Functions to construct new graphs from old}

The  following sections describe  functions to construct new  graphs from
old ones.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{InducedSubgraph}

'InducedSubgraph( <gamma>, <V> )' \\
'InducedSubgraph( <gamma>, <V>, <G> )'

This function returns the subgraph of <gamma> induced on the  vertex list
<V> (which must not contain  repeated  elements).  If the  optional third
parameter  <G> is  given,  then it is assumed that <G> fixes <V> setwise,
and is a group of automorphisms of the induced subgraph when restriced to
<V>.   This  knowledge is then used  to give an  associated group  to the
induced subgraph. If  no such  <G> is given then the  associated group is
trivial.

|    gap> gamma := JohnsonGraph(4,2);;
    gap> S := [2,3,4,5];;
    gap> InducedSubgraph( gamma, S, Stabilizer(gamma.group,S,OnSets) );
    rec(
      isGraph := true,
      order := 4,
      group := Group( (2,3), (1,2)(3,4) ),
      schreierVector := [ -1, 2, 1, 2 ],
      adjacencies := [ [ 2, 3 ] ],
      representatives := [ 1 ],
      isSimple := true,
      names := [ [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ] ] ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DistanceSetInduced}

'DistanceSetInduced( <gamma>, <distances>, <V> )' \\
'DistanceSetInduced( <gamma>, <distances>, <V>, <G> )'

This  function  returns the  subgraph  of <gamma>  induced on  the set of
vertices $w$ of <gamma> such that $d(<V>,w)$ is in <distances> (a list or
singleton distance).

The optional  parameter <G>,  if present, is assumed to be a subgroup  of
$\Aut(<gamma>)$  fixing <V> setwise.   Including such a  <G> can speed up
the function.

|    gap> DistanceSetInduced( JohnsonGraph(4,2), [0,1], [1] );
    rec(
      isGraph := true,
      order := 5,
      group := Group( (2,3)(4,5), (2,5)(3,4) ),
      schreierVector := [ -1, -2, 1, 2, 2 ],
      adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 4 ] ],
      representatives := [ 1, 2 ],
      isSimple := true,
      names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ] ] ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DistanceGraph}

'DistanceGraph( <gamma>, <distances> )'

This function  returns the  graph <delta>,  with the same  vertex set  as
<gamma>, such that $[x,y]$ is  an edge of <delta> if and only if $d(x,y)$
(in <gamma>) is in the list <distances>.

|    gap> DistanceGraph( JohnsonGraph(4,2), [2] );
    rec(
      isGraph := true,
      order := 6,
      group := Group( (1,5)(2,6), (1,3)(4,6), (2,3)(4,5) ),
      schreierVector := [ -1, 3, 2, 3, 1, 2 ],
      adjacencies := [ [ 6 ] ],
      representatives := [ 1 ],
      names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ],
          [ 3, 4 ] ],
      isSimple := true )
    gap> ConnectedComponents(last);
    [ [ 1, 6 ], [ 2, 5 ], [ 3, 4 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ComplementGraph}

'ComplementGraph( <gamma> )' \\
'ComplementGraph( <gamma>, <comploops> )'

This  function returns the complement of the graph <gamma>.  The optional
boolean  parameter <comploops>  determines whether or not  loops/nonloops
are   complemented   (default\:\   'false'   (loops/nonloops    are   not
complemented)).

|    gap> ComplementGraph( NullGraph(SymmetricGroup(3)) );
    rec(
      isGraph := true,
      order := 3,
      group := Group( (1,3), (2,3) ),
      schreierVector := [ -1, 2, 1 ],
      adjacencies := [ [ 2, 3 ] ],
      representatives := [ 1 ],
      isSimple := true )
    gap> IsLoopy(last);
    false
    gap> IsLoopy(ComplementGraph(NullGraph(SymmetricGroup(3)),true));
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PointGraph}

'PointGraph( <gamma> )' \\
'PointGraph( <gamma>, <v> )'

Assuming that <gamma>  is simple, connected, and bipartite, this function
returns   the  induced   subgraph   on   the   connected   component   of
'DistanceGraph(<gamma>,2)'   containing  the   vertex   <v>  (default\:{}
$<v>=1$).

Thus, if <gamma> is the incidence graph  of a connected geometry, and <v>
represents a point, then the point graph of the geometry is returned.

|    gap> BipartiteDouble( CompleteGraph(SymmetricGroup(4)) );;
    gap> PointGraph(last);
    rec(
      isGraph := true,
      order := 4,
      group := Group( (3,4), (2,4), (1,4) ),
      schreierVector := [ -1, 2, 1, 3 ],
      adjacencies := [ [ 2, 3, 4 ] ],
      representatives := [ 1 ],
      isSimple := true,
      names := [ [ 1, "+" ], [ 2, "+" ], [ 3, "+" ], [ 4, "+" ] ] )
    gap> IsCompleteGraph(last);
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{EdgeGraph}

'EdgeGraph( <gamma> )'

This function returns the edge graph, also called the line  graph, of the
simple graph <gamma>.

This *edge graph* <delta> has the unordered edges of <gamma> as vertices,
and $e$ is joined to $f$ in <delta> precisely when $\|e\cap f\|=1$.

|    gap> EdgeGraph( CompleteGraph(SymmetricGroup(5)) );
    rec(
      isGraph := true,
      order := 10,
      group := Group( ( 1, 7)( 2, 9)( 3,10), ( 1, 4)( 5, 9)( 6,10),
        ( 2, 4)( 5, 7)( 8,10), ( 3, 4)( 6, 7)( 8, 9) ),
      schreierVector := [ -1, 3, 4, 2, 3, 4, 1, 4, 2, 2 ],
      adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ],
      representatives := [ 1 ],
      isSimple := true,
      names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ],
          [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ] ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UnderlyingGraph}

'UnderlyingGraph( <gamma> )'

This function returns the underlying graph <delta> of <gamma>.  The graph
<delta> has the  same vertex  set  as  <gamma>, and  has  an edge $[x,y]$
precisely  when <gamma> has  an  edge $[x,y]$  or an edge  $[y,x]$.  This
function also sets the 'isSimple' components of <gamma> and <delta>.

|    gap> gamma := EdgeOrbitsGraph( Group((1,2,3,4)), [1,2] );
    rec(
      isGraph := true,
      order := 4,
      group := Group( (1,2,3,4) ),
      schreierVector := [ -1, 1, 1, 1 ],
      adjacencies := [ [ 2 ] ],
      representatives := [ 1 ],
      isSimple := false )
    gap> UnderlyingGraph(gamma);
    rec(
      isGraph := true,
      order := 4,
      group := Group( (1,2,3,4) ),
      schreierVector := [ -1, 1, 1, 1 ],
      adjacencies := [ [ 2, 4 ] ],
      representatives := [ 1 ],
      isSimple := true ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{QuotientGraph}

'QuotientGraph( <gamma>, <R> )'

Let $S$ be  the smallest <gamma.group>-invariant  equivalence relation on
the vertices of <gamma>, such  that $S$ contains  the relation <R> (which
should  be a  list  of ordered  pairs (length  2  lists) of  vertices  of
<gamma>).  Then this function returns  a graph isomorphic to the quotient
<delta> of  the  graph <gamma>, defined  as   follows.   The vertices  of
<delta> are  the equivalence classes of $S$,  and $[X,Y]$ is an  edge  of
<delta> if and only if $[x,y]$ is  an edge of <gamma>  for some $x\in X$,
$y\in Y$.

|    gap> gamma := JohnsonGraph(4,2);;
    gap> QuotientGraph( gamma, [[1,6]] );
    rec(
      isGraph := true,
      order := 3,
      group := Group( (1,2), (1,3), (2,3) ),
      schreierVector := [ -1, 1, 2 ],
      adjacencies := [ [ 2, 3 ] ],
      representatives := [ 1 ],
      isSimple := true,
      names := [ [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 3 ], [ 2, 4 ] ],
          [ [ 1, 4 ], [ 2, 3 ] ] ] ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{BipartiteDouble}

'BipartiteDouble( <gamma> )'

This function  returns the  bipartite  double  of the graph  <gamma>,  as
defined in \cite{BCN89}.

|    gap> gamma := JohnsonGraph(4,2);
    rec(
      isGraph := true,
      order := 6,
      group := Group( (1,5)(2,6), (1,3)(4,6), (2,3)(4,5) ),
      schreierVector := [ -1, 3, 2, 3, 1, 2 ],
      adjacencies := [ [ 2, 3, 4, 5 ] ],
      representatives := [ 1 ],
      names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ],
          [ 3, 4 ] ],
      isSimple := true )
    gap> IsBipartite(gamma);
    false
    gap> delta := BipartiteDouble(gamma);
    rec(
      isGraph := true,
      order := 12,
      group := Group( ( 1, 5)( 2, 6)( 7,11)( 8,12), ( 1, 3)( 4, 6)( 7, 9)
        (10,12), ( 2, 3)( 4, 5)( 8, 9)(10,11), ( 1, 7)( 2, 8)( 3, 9)
        ( 4,10)( 5,11)( 6,12) ),
      schreierVector := [ -1, 3, 2, 3, 1, 2, 4, 4, 4, 4, 4, 4 ],
      adjacencies := [ [ 8, 9, 10, 11 ] ],
      representatives := [ 1 ],
      isSimple := true,
      names := [ [ [ 1, 2 ], "+" ], [ [ 1, 3 ], "+" ], [ [ 1, 4 ], "+" ],
          [ [ 2, 3 ], "+" ], [ [ 2, 4 ], "+" ], [ [ 3, 4 ], "+" ],
          [ [ 1, 2 ], "-" ], [ [ 1, 3 ], "-" ], [ [ 1, 4 ], "-" ],
          [ [ 2, 3 ], "-" ], [ [ 2, 4 ], "-" ], [ [ 3, 4 ], "-" ] ] )
    gap> IsBipartite(delta);
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GeodesicsGraph}

'GeodesicsGraph( <gamma>, <x>, <y> )'

This  function  returns the  the  graph induced  on the  set of geodesics
between vertices  <x> and  <y>,  but  not  including  <x>  or  <y>.  This
function is only for a simple graph <gamma>.

|    gap> GeodesicsGraph( JohnsonGraph(4,2), 1, 6 );
    rec(
      isGraph := true,
      order := 4,
      group := Group( (1,3)(2,4), (1,4)(2,3), (1,3,4,2) ),
      schreierVector := [ -1, 2, 1, 2 ],
      adjacencies := [ [ 2, 3 ] ],
      representatives := [ 1 ],
      isSimple := true,
      names := [ [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ] ] )
    gap> GlobalParameters(last);
    [ [ 0, 0, 2 ], [ 1, 0, 1 ], [ 2, 0, 0 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CollapsedIndependentOrbitsGraph}

'CollapsedIndependentOrbitsGraph( <G>, <gamma> )' \\
'CollapsedIndependentOrbitsGraph( <G>, <gamma>, <N> )'

Given a subgroup <G> of the automorphism group of the graph <gamma>, this
function returns a graph isomorphic to  <delta>, defined as follows.  The
vertices of <delta> are those <G>-orbits of  the vertices of <gamma> that
are independent sets,  and  $x$ is *not* joined to $y$ in <delta>  if and
only if $x\cup y$ is an independent set in <gamma>.

If the optional  parameter  $N$  is given,  then  it is  assumed to be  a
subgroup  of  $\Aut(<gamma>)$ preserving  the  set  of <G>-orbits  of the
vertices of  <gamma>  (for  example,  the normalizer in  <gamma.group> of
<G>).  This information can make the function more efficient.

|    gap> G := Group( (1,2) );;
    gap> gamma := NullGraph( SymmetricGroup(3) );;
    gap> CollapsedIndependentOrbitsGraph( G, gamma );
    rec(
      isGraph := true,
      order := 2,
      group := Group( () ),
      schreierVector := [ -1, -2 ],
      adjacencies := [ [  ], [  ] ],
      representatives := [ 1, 2 ],
      isSimple := true,
      names := [ [ 1, 2 ], [ 3 ] ] ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CollapsedCompleteOrbitsGraph}

'CollapsedCompleteOrbitsGraph( <G>, <gamma> )' \\
'CollapsedCompleteOrbitsGraph( <G>, <gamma>, <N> )'

Given  a  subgroup <G> of  the   automorphism  group of the simple  graph
<gamma>, this function returns a graph isomorphic  to <delta>, defined as
follows.  The vertices of <delta> are those <G>-orbits of the vertices of
<gamma> on  which complete subgraphs are  induced in <gamma>, and  $x$ is
joined to $y$ in  <delta> if and  only if $x\not=y$  and the  subgraph of
<gamma> induced on $x\cup y$ is a complete graph.

If the optional  parameter  <N>  is given, then  it is assumed  to  be  a
subgroup of  $\Aut(<gamma>)$  preserving  the  set of  <G>-orbits  of the
vertices  of  <gamma> (for  example,  the normalizer in  <gamma.group> of
<G>).  This information can make the function more efficient.

|    gap> G := Group( (1,2) );;
    gap> gamma := NullGraph( SymmetricGroup(3) );;
    gap> CollapsedCompleteOrbitsGraph( G, gamma );
    rec(
      isGraph := true,
      order := 1,
      group := Group( () ),
      schreierVector := [ -1 ],
      adjacencies := [ [  ] ],
      representatives := [ 1 ],
      names := [ [ 3 ] ],
      isSimple := true )
    gap> gamma := CompleteGraph( SymmetricGroup(3) );;
    gap> CollapsedCompleteOrbitsGraph( G, gamma );
    rec(
      isGraph := true,
      order := 2,
      group := Group( () ),
      schreierVector := [ -1, -2 ],
      adjacencies := [ [ 2 ], [ 1 ] ],
      representatives := [ 1, 2 ],
      names := [ [ 1, 2 ], [ 3 ] ],
      isSimple := true ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{NewGroupGraph}

'NewGroupGraph( <G>, <gamma> )'

This  function returns a  copy <delta> of <gamma>,  except that the group
associated with  <delta> is <G>, which is a assumed to be  a subgroup  of
$\Aut(<delta>)$.

Note that the result of  some functions  of  a graph  depend on the group
associated  with  that graph  (which must always  be  a  subgroup  of the
automorphism group of the graph).

|    gap> gamma := JohnsonGraph(4,2);;
    gap> aut := AutGroupGraph(gamma);
    Group( (3,4), (2,3)(4,5), (1,2)(5,6) )
    gap> Size(gamma.group);
    24
    gap> Size(aut);
    48
    gap> delta := NewGroupGraph( aut, gamma );;
    gap> Size(delta.group);
    48
    gap> IsIsomorphicGraph( gamma, delta );
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Vertex-Colouring and Complete Subgraphs}

The following   sections  describe  functions  for   vertex-colouring  or
constructing complete subgraphs of given graphs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{VertexColouring}

'VertexColouring( <gamma> )'

This  function  returns  a proper  vertex-colouring  $C$  for  the  graph
<gamma>, which must be simple.

This *proper vertex-colouring* $C$ is a list  of natural numbers, indexed
by  the  vertices of <gamma>, and  has the  property that $C[i]\not=C[j]$
whenever $[i,j]$ is an edge of <gamma>.  At  present a *greedy* algorithm
is used.

|    gap> VertexColouring( JohnsonGraph(4,2) );
    [ 1, 2, 3, 3, 2, 1 ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CompleteSubgraphs}

'CompleteSubgraphs( <gamma> )' \\
'CompleteSubgraphs( <gamma>, <k> )' \\
'CompleteSubgraphs( <gamma>, <k>, <alls> )'

This function returns a set $K$  of complete subgraphs of <gamma>,  which
must be a simple graph.  A complete subgraph is represented by its vertex
set.   If  $<k> > -1$  then the  elements of $K$  each  have  size  <k>,
otherwise the  elements  of $K$ represent  maximal complete subgraphs  of
<gamma>.  The default for <k> is $-1$, i.e. maximal complete subgraphs.

The   optional  boolean  parameter  <alls>  controls  how  many  complete
subgraphs are returned.  If <alls> is 'true' (the default), then $K$ will
contain (perhaps properly) a  set of  <gamma.group> orbit-representatives
of  the size <k>  (if $<k>  > -1$) or  maximal (if  $<k>  \< 0$) complete
subgraphs of <gamma>.

If <alls> is 'false' then $K$ will contain at most one element.   In this
case, if $<k> \< 0$ then $K$  will  contain  just  one  maximal  complete
subgraph, and if $<k> > -1$ then $K$ will contain  a complete subgraph of
size <k> if and only if such a subgraph is contained in <gamma>.

|    gap> gamma := JohnsonGraph(5,2);;
    gap> CompleteSubgraphs(gamma);
    [ [ 1, 2, 3, 4 ], [ 1, 2, 5 ] ]
    gap> CompleteSubgraphs(gamma,2,false);
    [ [ 1, 2 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CompleteSubgraphsOfGivenSize}

'CompleteSubgraphsOfGivenSize( <gamma>, <k> )' \\
'CompleteSubgraphsOfGivenSize( <gamma>, <k>, <alls> )' \\
'CompleteSubgraphsOfGivenSize( <gamma>, <k>, <alls>, <maxi> )' \\
'CompleteSubgraphsOfGivenSize( <gamma>, <k>, <alls>, <maxi>, <colnum> )'

Let <gamma> be a simple graph and $<k> > 0$.  This function returns a set
$K$ of complete subgraphs of size <k> of <gamma>, if such subgraphs exist
(else the empty set is returned).  A complete subgraph  is represented by
its vertex set.  This function is more efficient for its purpose than the
more general function 'CompleteSubgraphs'.

The  boolean  parameter  <alls>  is used  to  control  how many  complete
subgraphs are returned.  If <alls> is true  (the  default), then $K$ will
contain (perhaps properly) a set  of <gamma.group>  orbit-representatives
of the  size  <k> complete subgraphs of <gamma>.  If <alls> is false then
$K$ will contain at most one element, and will contain one element if and
only if <gamma> contains a complete subgraph of size <k>.

If the boolean parameter <maxi> is bound and  has value true, then  it is
assumed that all complete subgraphs of size <k> of <gamma> are maximal.

If  the  optional rational parameter  <colnum> is  given, then a sensible
value is
\begin{center}
    'OrderGraph(<gamma>)/Length(Set(VertexColouring(<gamma>)))'.
\end{center}

The use of this parameter may speed up the function.

|    gap> gamma := JohnsonGraph(5,2);;
    gap> CompleteSubgraphsOfGivenSize(gamma,5);
    [  ]
    gap> CompleteSubgraphsOfGivenSize(gamma,4,true,true);
    [ [ 1, 2, 3, 4 ] ]
    gap> gamma := NewGroupGraph( Group(()), gamma );;
    gap> CompleteSubgraphsOfGivenSize(gamma,4,true,true);
    [ [ 1, 2, 3, 4 ], [ 1, 5, 6, 7 ], [ 2, 5, 8, 9 ], [ 3, 6, 8, 10 ],
      [ 4, 7, 9, 10 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Functions depending on nauty}

For convenience,  {\GRAPE} provides  a (somewhat primitive)  interface to
Brendan  McKay\'s  {\nauty} (Version~1.7) package  (see \cite{Nau90}) for
calculating  automorphism  groups  of vertex-coloured  graphs,   and  for
testing graph isomorphism.

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

'AutGroupGraph( <gamma> )' \\
'AutGroupGraph( <gamma>, <colouring> )'

The first version of this function returns the  automorphism group of the
(directed) graph <gamma>, using {\nauty}.

In the second version, <colouring> is a vertex-colouring  of <gamma>, and
the subgroup of $\Aut(<gamma>)$ preserving this  colouring  is  returned.
Here, a colouring should be given as a list of sets, forming a partion of
the vertices.   The  set for the last colour may be omitted. Note that we
do not require that adjacent vertices have different colours.

|    gap> gamma := JohnsonGraph(4,2);;
    gap> Size(AutGroupGraph(gamma));
    48
    gap> Size(AutGroupGraph(gamma,[[1,6]]));
    16 |

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

'IsIsomorphicGraph( <gamma1>, <gamma2> )'

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

This  function creates or  uses the record component 'canonicalLabelling'
of a graph.  As noted  in \cite{Nau90}, a  canonical  labelling given  by
{\nauty}  can  depend   on  the version   of  {\nauty}  (Version~1.7   in
{\GRAPE}~2.2),  certain  parameters of  {\nauty}  (always set the same by 
{\GRAPE}~2.2),  and  the  compiler  and  computer  used.  If you use  the 
'canonicalLabelling' component  (say by using  'IsIsomorphicGraph')  of a 
graph stored on a file, then you must be sure that this field was created 
in the same environment in which you are presently computing. If in doubt,  
unbind the 'canonicalLabelling' component  of  the  graph  before  testing 
isomorphism.

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{An example}

We conclude this chapter with a simple example to  illustrate further the
use of {\GRAPE}.

In this example we construct the  Petersen graph $P$, and its  edge graph
(often  called line graph)  $EP$.  We compute  the (global) parameters of
$EP$, and so verify that $EP$ is distance-regular (see \cite{BCN89}).  We
also show that  there is just  one orbit  of 1-factors  of  $P$ under the
automorphism  group of $P$ (but you  should read the documentation of the
function 'CompleteSubgraphsOfGivenSize' to see exactly what that function
does).

|    gap> P := Graph( SymmetricGroup(5), [[1,2]], OnSets,
    >          function(x,y) return Intersection(x,y)=[]; end );
    rec(
      isGraph := true,
      order := 10,
      group := Group( ( 1, 2)( 6, 8)( 7, 9), ( 1, 3)( 4, 8)( 5, 9),
        ( 2, 4)( 3, 6)( 9,10), ( 2, 5)( 3, 7)( 8,10) ),
      schreierVector := [ -1, 1, 2, 3, 4, 3, 4, 2, 2, 4 ],
      adjacencies := [ [ 8, 9, 10 ] ],
      representatives := [ 1 ],
      names := [ [ 1, 2 ], [ 2, 5 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ],
          [ 1, 3 ], [ 1, 4 ], [ 3, 5 ], [ 4, 5 ], [ 3, 4 ] ] )
    gap> Diameter(P);
    2
    gap> Girth(P);
    5
    gap> EP := EdgeGraph(P);
    rec(
      isGraph := true,
      order := 15,
      group := Group( ( 1, 4)( 2, 5)( 3, 6)(10,11)(12,13)(14,15), ( 1, 7)
        ( 2, 8)( 3, 9)(10,15)(11,13)(12,14), ( 2, 3)( 4, 7)( 5,10)( 6,11)
        ( 8,12)( 9,14), ( 1, 3)( 4,12)( 5, 8)( 6,13)( 7,10)( 9,15) ),
      schreierVector := [ -1, 3, 4, 1, 3, 1, 2, 3, 2, 4, 1, 4, 1, 2, 2 ],
      adjacencies := [ [ 2, 3, 13, 15 ] ],
      representatives := [ 1 ],
      isSimple := true,
      names := [ [ [ 1, 2 ], [ 3, 5 ] ], [ [ 1, 2 ], [ 4, 5 ] ],
          [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 3 ], [ 2, 5 ] ],
          [ [ 1, 4 ], [ 2, 5 ] ], [ [ 2, 5 ], [ 3, 4 ] ],
          [ [ 1, 5 ], [ 2, 3 ] ], [ [ 1, 5 ], [ 2, 4 ] ],
          [ [ 1, 5 ], [ 3, 4 ] ], [ [ 1, 4 ], [ 2, 3 ] ],
          [ [ 2, 3 ], [ 4, 5 ] ], [ [ 1, 3 ], [ 2, 4 ] ],
          [ [ 2, 4 ], [ 3, 5 ] ], [ [ 1, 3 ], [ 4, 5 ] ],
          [ [ 1, 4 ], [ 3, 5 ] ] ] )
    gap> GlobalParameters(EP);
    [ [ 0, 0, 4 ], [ 1, 1, 2 ], [ 1, 2, 1 ], [ 4, 0, 0 ] ]
    gap> CompleteSubgraphsOfGivenSize(ComplementGraph(EP),5);
    [ [ 1, 5, 9, 11, 12 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E  Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables
%%
%%  Local Variables:
%%  mode:               outline
%%  outline-regexp:     "\\\\Chapter\\|\\\\Section\\|%E"
%%  fill-column:        73
%%  eval:               (hide-body)
%%  End:
%%