1 Grape

Sections

1. Installing the GRAPE Package
2. Loading GRAPE
3. The structure of a graph in GRAPE
4. Examples of the use of GRAPE

This manual describes the GRAPE (Version 4.9.1) 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 Soi93 and 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 MP14 or bliss 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 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.1, 2024, https://gap-packages.github.io/grape.

For questions, remarks, suggestions, and issues, please use the issue tracker at 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).

1.1 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 Installing a GAP Package). If you do need to download GRAPE, you can find the most recent .tar.gz archive at 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 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 path 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

./configure ../..

make 

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 The gaprc file), where dreadnaut_or_dreadnautB_executable should be the name of your dreadnaut or dreadnautB executable file:

LoadPackage("grape"); 
GRAPE_NAUTY := true; 
GRAPE_DREADNAUT_EXE := "dreadnaut_or_dreadnautB_executable"; 

LoadPackage("grape"); 
GRAPE_NAUTY := false; 
GRAPE_BLISS_EXE := "bliss_executable"; 

LoadPackage("grape"); 
GRAPE_NAUTY := false; 
GRAPE_BLISS_EXE := "/usr/local/bin/bliss"; 

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

LoadPackage( "grape" ); 

?GRAPE 

Test(Filename(DirectoriesPackageLibrary("grape","tst"),"testall.tst"));

A pdf version of the GRAPE manual is available as manual.pdf in the doc directory of the home directory of GRAPE.

1.2 Loading GRAPE

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

LoadPackage("grape");

1.3 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 gamma. 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 i. 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 gamma, 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 gamma.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.

1.4 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 Cam99, CSS99, HL99, Soi06 and 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 BCN89).

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 ] ]

[Up] [Next] [Index]