CAIN

Systems related to Group Theory


GRAPE


GRAPE is a system for computing with graphs, and is primarily designed for constructing and analysing graphs related to groups and finite geometries.

The vast majority of GRAPE functions are written entirely in the GAP language, except for the automorphism group and isomorphism testing functions, which use Brendan McKay's Nauty (Version 1.7) package.

Except for the nauty 1.7 package included with GRAPE, the GRAPE system was designed and written by Leonard H. Soicher, School of Mathematical Sciences, Queen Mary and Westfield College, Mile End Road, London E1 4NS, U.K., email: L.H.Soicher@qmw.ac.uk.

GRAPE is primarily designed for the construction and analysis of graphs related to 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. 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 GAP permutation group associated with GAP (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).

GRAPE has been encorporated into GAP.


Special Purpose Systems


webmaster@can.nl

Last updated: December 15, 1994