%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%A  constr.tex               GRAPE documentation              Leonard Soicher
%
%
%
\def\GRAPE{\sf GRAPE}
\def\nauty{\it nauty}
\def\Aut{{\rm Aut}\,}

\Chapter{Functions to construct new graphs from old}

This chapter describes 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
restricted to <V>. In that case, the image of <G> acting on <V> is the
group associated with the induced subgraph. If no such <G> is given then
the associated group is trivial. The name of vertex <i> in the induced
subgraph is equal to the name of vertex `<V>[<i>]' in <gamma>.

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

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

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

Let <V> be a vertex or a nonempty list of vertices of <gamma>.
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.

See also "Distance" and "DistanceSet". 

\beginexample
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 ] ] )
\endexample

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

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

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

\beginexample
gap> DistanceGraph( JohnsonGraph(4,2), [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 := [ [ 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 ] ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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)). The
returned graph will have the same vertex-names as <gamma>.

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 of rank
2, and <v> represents a point, then the point graph of the geometry is
returned.

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

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

\>EdgeGraph( <gamma> )

This function return a graph isomorphic to the 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$.  The name of the vertex of the returned graph
corresponding to the unordered edge $[v,w]$ of <gamma> (with $v\< w$)
is `[VertexName(<gamma>,<v>),VertexName(<gamma>,<w>)]'.

\beginexample
gap> EdgeGraph( CompleteGraph(SymmetricGroup(5)) );
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 ],
  isSimple := true,
  names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ],
      [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ] )
gap> GlobalParameters(last);
[ [ 0, 0, 6 ], [ 1, 3, 2 ], [ 4, 2, 0 ] ]
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{SwitchedGraph}

\>SwitchedGraph( <gamma>, <V> ) 
\>SwitchedGraph( <gamma>, <V>, <H> ) 

This function returns the switched graph <delta> of the graph <gamma>,
switched with respect to the vertex list (or singleton vertex) <V>.

The returned graph <delta>  has vertex-set (and vertex-names) the same
as <gamma>.  If vertices $x,y$ of <delta> are both in <V> or both not
in <V>, then $[x,y]$ is an edge of <delta> if and only if $[x,y]$ is an
edge of <gamma>; otherwise $[x,y]$ is an edge of <delta> if and only if
$[x,y]$ is not an edge of <gamma>.  If the optional third argument <H>
is given, then it is assumed to be a subgroup of Aut(<gamma>) stabilizing
<V> setwise.

\beginexample
gap> J:=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> S:=SwitchedGraph(J,[1,6]);
rec(
  isGraph := true,
  order := 6,
  group := Group( () ),
  schreierVector := [ -1, -2, -3, -4, -5, -6 ],
  adjacencies := [ [  ], [ 3, 4 ], [ 2, 5 ], [ 2, 5 ], [ 3, 4 ], [  ] ],
  representatives := [ 1, 2, 3, 4, 5, 6 ],
  isSimple := true,
  names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ] )
gap> ConnectedComponents(S);
[ [ 1 ], [ 2, 3, 4, 5 ], [ 6 ] ]
\endexample
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UnderlyingGraph}

\>UnderlyingGraph( <gamma> )

This function returns the underlying graph <delta> of <gamma>. The graph
<delta> has the same vertex-set (and vertex-names) 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>.

\beginexample
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 )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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$.  The name of a vertex $v$ in the returned graph is a list (not
necessarily ordered) of the vertex-names of <gamma> for the vertices in
the equivalence class corresponding to $v$.

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

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

\>BipartiteDouble( <gamma> )

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

\beginexample
gap> gamma := JohnsonGraph(4,2);;
gap> IsBipartite(gamma);
false
gap> delta := BipartiteDouble(gamma);
rec(
  isGraph := true,
  order := 12,
  group := Group( [ ( 1, 4, 6, 3)( 2, 5)( 7,10,12, 9)( 8,11),
      ( 2, 4)( 3, 5)( 8,10)( 9,11), ( 1, 7)( 2, 8)( 3, 9)( 4,10)( 5,11)
        ( 6,12) ] ),
  schreierVector := [ -1, 2, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3 ],
  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
\endexample

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

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

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

\beginexample
gap> GeodesicsGraph( JohnsonGraph(4,2), 1, 6 );
rec(
  isGraph := true,
  order := 4,
  group := Group( [ (1,3)(2,4), (1,4)(2,3), (2,3) ] ),
  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 ] ]
\endexample

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

\>CollapsedIndependentOrbitsGraph( <G>, <gamma> )
\>CollapsedIndependentOrbitsGraph( <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> that are independent sets in <gamma>, and $x$ is joined to $y$ in
<delta> if and only if $x\cup y$ is *not* an independent set in <gamma>.
The name of a vertex $v$ in the returned graph is a list (not necessarily
ordered) of the vertex-names of <gamma> for the vertices in the <G>-orbit
corresponding to $v$.

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.

\beginexample
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 ] ] )
gap> gamma := CompleteGraph( SymmetricGroup(3) );;
gap> CollapsedIndependentOrbitsGraph( G, gamma );
rec(
  isGraph := true,
  order := 1,
  group := Group( [ () ] ),
  schreierVector := [ -1 ],
  adjacencies := [ [  ] ],
  representatives := [ 1 ],
  isSimple := true,
  names := [ [ 3 ] ] )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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.  The name of a vertex
$v$ in the returned graph is a list (not necessarily ordered) of the
vertex-names of <gamma> for the vertices in the <G>-orbit corresponding
to $v$.

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.

\beginexample
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 )
\endexample

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

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

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

Note that the results 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).

\beginexample
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
\endexample