%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % %A grape.tex GRAPE documentation Leonard Soicher % % % \def\GRAPE{\sf GRAPE} \def\nauty{\it nauty} \def\Aut{{\rm Aut}\,} \Chapter{Grape} This manual describes the {\GRAPE} (Version~4.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). Most {\GRAPE} functions are written entirely in the {\GAP} language. However, the {\GRAPE} functions `AutomorphismGroup', `AutGroupGraph', `IsIsomorphicGraph', `GraphIsomorphismClassRepresentatives', `GraphIsomorphism' and `PartialLinearSpaces' make direct or indirect use of B.D.~McKay{\pif}s {\nauty} (Version~2.2 final) package \cite{Nau90}, via a {\GRAPE} interface. These functions can only be used on a fully installed version of {\GRAPE} in a UNIX environment. Installation of {\GRAPE} is described in its `README' file and in its manual section "Installing the GRAPE Package". Except for the {\nauty} package included with {\GRAPE}, and the function `SmallestImageSet' by Steve Linton, the {\GRAPE} package was designed and written by Leonard H. Soicher, School of Mathematical Sciences, Queen Mary, University of London. If you use {\GRAPE} to solve a problem then please send a short email about it to \Mailto{L.H.Soicher@qmul.ac.uk}, and reference the {\GRAPE} package as follows: L.H. Soicher, The {GRAPE} package for {GAP}, Version~4.3, 2006, \URL{http://www.maths.qmul.ac.uk/~leonard/grape/}. If your work made use a function depending on the {\nauty} package then you should also reference {\nauty} \cite{Nau90}. The development of {\GRAPE} was partially supported by a European Union HCM grant in ``Computational Group Theory''. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Installing the GRAPE Package} To install {\GRAPE}~4.3 (after installing {\GAP}), first obtain the {\GRAPE} archive file `grape4r3.tar.gz', available at \URL{http://www.maths.qmul.ac.uk/~leonard/grape/grape4r3.tar.gz} and then copy this archive file into the `pkg' directory of the {\GAP} root directory. Actually, it is possible to have several {\GAP} root directories (see "ref:GAP Root Directory"), and so it is easy to install {\GRAPE} locally even if you have no permission to add files to the main {\GAP} installation. Now go to the appropriate `pkg' directory containing `grape4r3.tar.gz', and then run \begintt gunzip grape4r3.tar.gz tar -xf grape4r3.tar \endtt to unpack {\GRAPE}. After unpacking {\GRAPE}, the {\GAP}-only part of {\GRAPE} is installed. The parts of {\GRAPE} depending on B.~D.~Mckay's {\nauty} package (for computing automorphism groups and testing graph isomorphism) are only available in a UNIX environment, where you should proceed as follows: Go to the newly created `grape' directory (which we shall refer to as the *home directory* of {\GRAPE}) and run `/bin/sh configure <path>', where <path> is the path to the home directory of the {\GAP} distribution. So for example, if you install {\GRAPE} in the `pkg' directory of the {\GAP} home directory, run \begintt /bin/sh configure ../.. \endtt This will fetch the name of the system architecture on which {\GAP} has been compiled, and create a `Makefile'. Now run \begintt make \endtt to create the binaries and to put them in the appropriate place. This completes the installation of {\GRAPE} for a single architecture. If {\GAP} is installed on different architectures on a common file system, this configuration process will only work for the *last* architecture for which {\GAP} was compiled. Therefore, you should always follow the above procedure to install the {\GRAPE} binaries immediately after compiling {\GAP} on a given architecture. However, if you want to add {\GRAPE} later, you can just run `/bin/sh configure' again in the main {\GAP} directory for the architecture before installing the {\GRAPE} binaries for that architecture. You should now test {\GRAPE} and the interface to {\nauty} 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 The command \begintt IsIsomorphicGraph( JohnsonGraph(7,3), JohnsonGraph(7,4) ); \endtt should return `true', and \begintt Size( AutGroupGraph( JohnsonGraph(4,2) ) ); \endtt should be `48'. Both dvi and pdf versions of the {\GRAPE} manual are available (as `manual.dvi' and `manual.pdf' respectively) in the `doc' directory of the home directory of {\GRAPE}. If you install {\GRAPE}, then please tell \Mailto{L.H.Soicher@qmul.ac.uk}, where you should also send any comments or bug reports. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Loading GRAPE} Before using {\GRAPE} you must load the package within {\GAP} by calling the statement \begintt gap> LoadPackage("grape"); Loading GRAPE 4.3 (GRaph Algorithms using PErmutation groups), by L.H.Soicher@qmul.ac.uk. true \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 <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', and `canonicalLabelling', which record information about that graph. *Note* All global variables used by {\GRAPE} start with `GRAPE\_'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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} and \cite{Soi06}. 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}). \beginexample gap> LoadPackage("grape"); Loading GRAPE 4.3 (GRaph Algorithms using PErmutation groups), by L.H.Soicher@qmul.ac.uk. 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 ] ] \endexample