Quelle  grape.tex   Sprache: Latech

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

\Chapter{Grape}

This manual describes the {\GRAPE} (Version~4.9.3) package for computing
with graphs and groups.

{\GRAPE} is primarily designed for the construction and analysis of
finite graphs related to groups, designs, and 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 the automorphism
group of <gamma>, and that <G> is used to reduce the storage and
CPU-time requirements for calculations with <gamma> (see
\cite{Soi93} and \cite{Soi04}).  Of course <G> may be the trivial group,
and in this case {\GRAPE} algorithms may perform more slowly than strictly
combinatorial algorithms (although this degradation in performance is
hopefully never more than a fixed constant factor).

Certain {\GRAPE} functions make direct or indirect use of the {\nauty}
\cite{MP14} or {\bliss} \cite{JK07} packages, for computing
automorphism groups of graphs and testing graph isomorphism. Such functions
can only be used on a fully installed version of {\GRAPE}. Installation
of {\GRAPE} is described in this chapter of the manual.

Except for the {\nauty} package of B.~D.~McKay included with {\GRAPE},
the function `SmallestImageSet' by Steve Linton, the {\nauty} interface
by Alexander Hulpke, and the initial {\bliss} interface by Jerry James,
the {\GRAPE} package was designed and written by Leonard H. Soicher,
School of Mathematical Sciences, Queen Mary University of London.
Except for the included {\nauty} package, {\GRAPE} is licensed under the
terms of the GNU General Public License as published by the Free Software
Foundation; either version 2 of the License, or (at your option) any later
version. For details, see \URL{https://www.gnu.org/licenses/gpl.html}.
Further licensing and copyright information for {\GRAPE} is contained
in its `README.md' file.

If you use {\GRAPE} in a published work, then please reference the
package as follows:

L.H. Soicher, The {GRAPE} package for {GAP}, Version~4.9.3, 2025,
\URL{https://gap-packages.github.io/grape}.

For questions, remarks, suggestions, and issues, please use the issue
tracker at \URL{https://github.com/gap-packages/grape/issues}.

The development of {\GRAPE} was partially supported by a European Union
HCM grant in ``Computational Group Theory'', and more recently by EPSRC
grant EP/M022641/1 (CoDiMa: a Collaborative Computational Project in
the area of Computational Discrete Mathematics).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Installing the GRAPE Package}

The official {\GAP} Windows distribution includes the {\GRAPE} package
fully installed.  Thus, {\GRAPE} normally requires no further installation
for Windows users of {\GAP}. What follows is for Unix users of {\GRAPE}.

You do not need to download and unpack an archive for {\GRAPE} unless you
want to install the package separately from your main {\GAP} installation
or are installing an upgrade of {\GRAPE} to an existing installation
of {\GAP} (see the main {\GAP} reference section "ref:Installing a GAP
Package"). If you do need to download {\GRAPE}, you can find the most
recent `.tar.gz' archive at \URL{https://gap-packages.github.io/grape}.
The archive file should be downloaded and unpacked in the `pkg'
subdirectory of an appropriate {\GAP} root directory (see the main {\GAP}
reference section "ref:GAP Root Directories").

If your {\GRAPE} installation does not include a compiled binary of 
the nauty/dreadnaut programs included with {\GRAPE} and you do not want 
to use an already installed version of {\nauty} or {\bliss}, you will 
need to perform compilation of the nauty/dreadnaut programs included with
{\GRAPE}, and to do this in a Unix environment, you should proceed as
follows.  After installing {\GAP}, go to the {\GRAPE} home directory
(usually the directory `pkg/grape' of the {\GAP} home directory),
and run `./configure <path>', where is the path of the {\GAP}
home directory.  So for example, if you install {\GRAPE} in the `pkg'
directory of the {\GAP} home directory, run 
\begintt 
./configure ../..
\endtt 
Then run
\begintt 
make 
\endtt 
to complete the installation of {\GRAPE}.

To use {\GRAPE} with a separately installed version of {\nauty} or
{\bliss} you should proceed as follows. Please note that the {\nauty}
interface for {\GRAPE} has only been extensively tested with the
included versions of {\nauty}, and the {\bliss} interface has only
been tested with Version~0.73 of {\bliss}. To use a separately
installed version of {\nauty}, type the following commands in {\GAP}, or 
place these commands in your `gaprc' file (see "ref:The gaprc file"), where
`dreadnaut_or_dreadnautB_executable' should be the name of your
dreadnaut or dreadnautB executable file:
\begintt
LoadPackage("grape"); 
GRAPE_NAUTY := true; 
GRAPE_DREADNAUT_EXE := "dreadnaut_or_dreadnautB_executable"; 
\endtt 
To use a separately installed version of {\bliss} instead of {\nauty},
type the following commands in {\GAP}, or place these commands in your
`gaprc' file (see "ref:The gaprc file"), where `bliss_executable' should be
the name of your bliss executable file:
\begintt
LoadPackage("grape"); 
GRAPE_NAUTY := false; 
GRAPE_BLISS_EXE := "bliss_executable"; 
\endtt 
For example, if the bliss executable is `/usr/local/bin/bliss', then type:
\begintt
LoadPackage("grape"); 
GRAPE_NAUTY := false; 
GRAPE_BLISS_EXE := "/usr/local/bin/bliss"; 
\endtt 

You should now test {\GRAPE} and the interface to {\nauty} or {\bliss}
on each architecture on which you have installed {\GRAPE}. Start up
{\GAP} and at the prompt type 
\begintt 
LoadPackage( "grape" ); 
\endtt
On-line documentation for {\GRAPE} should be available by typing 
\begintt
?GRAPE 
\endtt 
Then run some tests by typing:
\begintt
Test(Filename(DirectoriesPackageLibrary("grape","tst"),"testall.tst"));
\endtt
This should return the value `true'.
 
A pdf version of the {\GRAPE} manual is available as `manual.pdf' in the
`doc' directory of the home directory of {\GRAPE}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Loading GRAPE}

Before using {\GRAPE} you must load the package within {\GAP} by typing:

\begintt
LoadPackage("grape");
\endtt

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{The structure of a graph in GRAPE}
 
In general {\GRAPE} deals with finite 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 . The
vertices of <gamma> are always 1,2,...,`<gamma>.order', but they may also
be given *names*, either by a user (using `AssignVertexNames') or by a
function constructing a graph (e.g. `InducedSubgraph', `BipartiteDouble',
`QuotientGraph'). The `names' component, if present, records these
names, with `<gamma>.names[<i>]' the name of vertex . If the `names'
component is not present (the user may, for example, choose to unbind
it), then the names are taken to be 1,2,...,`<gamma>.order'. The `group'
component records the {\GAP} permutation group associated with <gamma>
(this group must be a subgroup of the automorphism group of <gamma>). The
`representatives' component records a set of orbit representatives
for the action of `<gamma>.group' on the vertices of , with
`<gamma>.adjacencies[<i>]' being the set of vertices adjacent to
`<gamma>.representatives[<i>]'. The `group' and `schreierVector'
components are used to compute the adjacency-set of an arbitrary vertex
of <gamma> (this is done by the function `Adjacency').

The only mandatory component which may change once a graph is initially
constructed is `adjacencies' (when an edge-orbit of `.group' is
added to, or removed from, <gamma>). A graph record may also have some
of the optional components `isSimple', `autGroup', `maximumClique',
`minimumVertexColouring', and `canonicalLabelling', which record
information about that graph.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Examples of the use of GRAPE}

We give here a simple example to illustrate the use of {\GRAPE}. All
functions used are described in detail in this manual. More
sophisticated examples of the use of {\GRAPE} can be found in
chapter "Partial Linear Spaces", and also in the references \cite{Cam99},
\cite{CSS99}, \cite{HL99}, \cite{Soi06} and \cite{Soi24b}.

In the example here, we construct the Petersen graph $P$, and its edge
graph (also called line graph) $EP$. We compute the global parameters
of $EP$, and so verify that $EP$ is distance-regular (see \cite{BCN89}).

\beginexample
gap> LoadPackage("grape");
true
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, 3, 5, 7)( 4, 6, 8, 9,10), ( 2, 4)( 6, 9)( 7,10) ]),
  schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 1, 2, 2 ], 
  adjacencies := [ [ 3, 5, 8 ] ], representatives := [ 1 ], 
  names := [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 1, 3 ], [ 4, 5 ], [ 2, 4 ], 
      [ 1, 5 ], [ 3, 5 ], [ 1, 4 ], [ 2, 5 ] ] )
gap> Diameter(P);
2
gap> Girth(P);
5
gap> EP := EdgeGraph(P);
rec( isGraph := true, order := 15, 
  group := Group([ ( 1, 4, 7, 2, 5)( 3, 6, 8, 9,12)(10,13,14,15,11), 
      ( 4, 9)( 5,11)( 6,10)( 7, 8)(12,15)(13,14) ]), 
  schreierVector := [ -1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 2 ], 
  adjacencies := [ [ 2, 3, 7, 8 ] ], representatives := [ 1 ], 
  isSimple := true, 
  names := [ [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 2 ], [ 4, 5 ] ], 
      [ [ 1, 2 ], [ 3, 5 ] ], [ [ 2, 3 ], [ 4, 5 ] ], [ [ 2, 3 ], [ 1, 5 ] ], 
      [ [ 2, 3 ], [ 1, 4 ] ], [ [ 3, 4 ], [ 1, 5 ] ], [ [ 3, 4 ], [ 2, 5 ] ], 
      [ [ 1, 3 ], [ 4, 5 ] ], [ [ 1, 3 ], [ 2, 4 ] ], [ [ 1, 3 ], [ 2, 5 ] ], 
      [ [ 2, 4 ], [ 1, 5 ] ], [ [ 2, 4 ], [ 3, 5 ] ], [ [ 3, 5 ], [ 1, 4 ] ], 
      [ [ 1, 4 ], [ 2, 5 ] ] ] )
gap> GlobalParameters(EP);
[ [ 0, 0, 4 ], [ 1, 1, 2 ], [ 1, 2, 1 ], [ 4, 0, 0 ] ]
\endexample