This chapter describes the main functions of the GRAPE (Version~2.31) 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 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 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 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.31 (GRaph Algorithms using PErmutation groups), by L.H.Soicher@qmw.ac.uk.
GAP 3.4.4