GAP Manual: 58. 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 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.2  (GRaph Algorithms using PErmutation groups),
    by L.H.Soicher@qmw.ac.uk.

This chapter contains the following sections:

[next] [prev] [up]