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:
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}.
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}).
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
