<html><head><title>[grape] 1 Grape</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP002.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <h1>1 Grape</h1><p> <P> <H3>Sections</H3> <oL> <li> <A HREF="CHAP001.htm#SECT001">Installing the GRAPE Package</a> <li> <A HREF="CHAP001.htm#SECT002">Loading GRAPE</a> <li> <A HREF="CHAP001.htm#SECT003">The structure of a graph in GRAPE</a> <li> <A HREF="CHAP001.htm#SECT004">Examples of the use of GRAPE</a> </ol><p> <p> This manual describes the GRAPE (Version 4.3) package for computing with graphs and groups. <p> 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 <var>gamma</var> always comes together with a known subgroup <var>G</var> of the automorphism group of <var>gamma</var>, and that <var>G</var> is used to reduce the storage and CPU-time requirements for calculations with <var>gamma</var> (see <a href="biblio.htm#Soi93"><cite>Soi93</cite></a> and <a href="biblio.htm#Soi04"><cite>Soi04</cite></a>). Of course <var>G</var> 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). <p> Most GRAPE functions are written entirely in the <font face="Gill Sans,Helvetica,Arial">GAP</font> language. However, the GRAPE functions <code>AutomorphismGroup</code>, <code>AutGroupGraph</code>, <code>IsIsomorphicGraph</code>, <code>GraphIsomorphismClassRepresentatives</code>, <code>GraphIsomorphism</code> and <code>PartialLinearSpaces</code> make direct or indirect use of B.D. McKay's nauty (Version 2.2 final) package <a href="biblio.htm#Nau90"><cite>Nau90</cite></a>, 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 <code>README</code> file and in its manual section <a href="CHAP001.htm#SECT001">Installing the GRAPE Package</a>. <p> Except for the nauty package included with GRAPE, and the function <code>SmallestImageSet</code> by Steve Linton, the GRAPE package was designed and written by Leonard H. Soicher, School of Mathematical Sciences, Queen Mary, University of London. <p> If you use GRAPE to solve a problem then please send a short email about it to <a href="mailto:L.H.Soicher@qmul.ac.uk">L.H.Soicher@qmul.ac.uk</a>, and reference the GRAPE package as follows: <p> L.H. Soicher, The GRAPE package for GAP, Version 4.3, 2006, <a href="http://www.maths.qmul.ac.uk/~leonard/grape/">http://www.maths.qmul.ac.uk/~leonard/grape/</a>. <p> If your work made use a function depending on the nauty package then you should also reference nauty <a href="biblio.htm#Nau90"><cite>Nau90</cite></a>. <p> The development of GRAPE was partially supported by a European Union HCM grant in ``Computational Group Theory''. <p> <p> <h2><a name="SECT001">1.1 Installing the GRAPE Package</a></h2> <p><p> To install GRAPE 4.3 (after installing <font face="Gill Sans,Helvetica,Arial">GAP</font>), first obtain the GRAPE archive file <code>grape4r3.tar.gz</code>, available at <a href="http://www.maths.qmul.ac.uk/~leonard/grape/grape4r3.tar.gz">http://www.maths.qmul.ac.uk/~leonard/grape/grape4r3.tar.gz</a> and then copy this archive file into the <code>pkg</code> directory of the <font face="Gill Sans,Helvetica,Arial">GAP</font> root directory. Actually, it is possible to have several <font face="Gill Sans,Helvetica,Arial">GAP</font> root directories (see <a href="../../../doc/htm/ref/CHAP009.htm#SECT002">GAP Root Directory</a>), and so it is easy to install GRAPE locally even if you have no permission to add files to the main <font face="Gill Sans,Helvetica,Arial">GAP</font> installation. Now go to the appropriate <code>pkg</code> directory containing <code>grape4r3.tar.gz</code>, and then run <pre> gunzip grape4r3.tar.gz tar -xf grape4r3.tar </pre> to unpack GRAPE. <p> After unpacking GRAPE, the <font face="Gill Sans,Helvetica,Arial">GAP</font>-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: <p> Go to the newly created <code>grape</code> directory (which we shall refer to as the <strong>home directory</strong> of GRAPE) and run <code>/bin/sh configure </code><var>path</var><code></code>, where <var>path</var> is the path to the home directory of the <font face="Gill Sans,Helvetica,Arial">GAP</font> distribution. So for example, if you install GRAPE in the <code>pkg</code> directory of the <font face="Gill Sans,Helvetica,Arial">GAP</font> home directory, run <pre> /bin/sh configure ../.. </pre> <p> This will fetch the name of the system architecture on which <font face="Gill Sans,Helvetica,Arial">GAP</font> has been compiled, and create a <code>Makefile</code>. Now run <pre> make </pre> to create the binaries and to put them in the appropriate place. This completes the installation of GRAPE for a single architecture. If <font face="Gill Sans,Helvetica,Arial">GAP</font> is installed on different architectures on a common file system, this configuration process will only work for the <strong>last</strong> architecture for which <font face="Gill Sans,Helvetica,Arial">GAP</font> was compiled. Therefore, you should always follow the above procedure to install the GRAPE binaries immediately after compiling <font face="Gill Sans,Helvetica,Arial">GAP</font> on a given architecture. However, if you want to add GRAPE later, you can just run <code>/bin/sh configure</code> again in the main <font face="Gill Sans,Helvetica,Arial">GAP</font> directory for the architecture before installing the GRAPE binaries for that architecture. <p> You should now test GRAPE and the interface to nauty on each architecture on which you have installed GRAPE. Start up <font face="Gill Sans,Helvetica,Arial">GAP</font> and at the prompt type <pre> LoadPackage( "grape" ); </pre> On-line documentation for GRAPE should be available by typing <pre> ?GRAPE </pre> The command <pre> IsIsomorphicGraph( JohnsonGraph(7,3), JohnsonGraph(7,4) ); </pre> should return <code>true</code>, and <pre> Size( AutGroupGraph( JohnsonGraph(4,2) ) ); </pre> should be <code>48</code>. <p> Both dvi and pdf versions of the GRAPE manual are available (as <code>manual.dvi</code> and <code>manual.pdf</code> respectively) in the <code>doc</code> directory of the home directory of GRAPE. <p> If you install GRAPE, then please tell <a href="mailto:L.H.Soicher@qmul.ac.uk">L.H.Soicher@qmul.ac.uk</a>, where you should also send any comments or bug reports. <p> <p> <h2><a name="SECT002">1.2 Loading GRAPE</a></h2> <p><p> Before using GRAPE you must load the package within <font face="Gill Sans,Helvetica,Arial">GAP</font> by calling the statement <p> <pre> gap> LoadPackage("grape"); Loading GRAPE 4.3 (GRaph Algorithms using PErmutation groups), by L.H.Soicher@qmul.ac.uk. true </pre> <p> <p> <h2><a name="SECT003">1.3 The structure of a graph in GRAPE</a></h2> <p><p> In general GRAPE deals with finite directed graphs which may have loops but have no multiple edges. However, many GRAPE functions only work for <strong>simple</strong> graphs (i.e. no loops, and whenever <var>[x,y]</var> is an edge then so is <var>[y,x]</var>), but these functions will check if an input graph is simple. <p> In GRAPE, a graph <var>gamma</var> is stored as a record, with mandatory components <code>isGraph</code>, <code>order</code>, <code>group</code>, <code>schreierVector</code>, <code>representatives</code>, and <code>adjacencies</code>. 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. <p> The <code>order</code> component contains the number of vertices of <var>gamma</var>. The vertices of <var>gamma</var> are always 1,2,...,<code></code><var>gamma</var><code>.order</code>, but they may also be given <strong>names</strong>, either by a user (using <code>AssignVertexNames</code>) or by a function constructing a graph (e.g. <code>InducedSubgraph</code>, <code>BipartiteDouble</code>, <code>QuotientGraph</code>). The <code>names</code> component, if present, records these names, with <code></code><var>gamma</var><code>.names[</code><var>i</var><code>]</code> the name of vertex <var>i</var>. If the <code>names</code> component is not present (the user may, for example, choose to unbind it), then the names are taken to be 1,2,...,<code></code><var>gamma</var><code>.order</code>. The <code>group</code> component records the <font face="Gill Sans,Helvetica,Arial">GAP</font> permutation group associated with <var>gamma</var> (this group must be a subgroup of the automorphism group of <var>gamma</var>). The <code>representatives</code> component records a set of orbit representatives for the action of <code></code><var>gamma</var><code>.group</code> on the vertices of <var>gamma</var>, with <code></code><var>gamma</var><code>.adjacencies[</code><var>i</var><code>]</code> being the set of vertices adjacent to <code></code><var>gamma</var><code>.representatives[</code><var>i</var><code>]</code>. The <code>group</code> and <code>schreierVector</code> components are used to compute the adjacency-set of an arbitrary vertex of <var>gamma</var> (this is done by the function <code>Adjacency</code>). <p> The only mandatory component which may change once a graph is initially constructed is <code>adjacencies</code> (when an edge-orbit of <code></code><var>gamma</var><code>.group</code> is added to, or removed from, <var>gamma</var>). A graph record may also have some of the optional components <code>isSimple</code>, <code>autGroup</code>, and <code>canonicalLabelling</code>, which record information about that graph. <p> <strong>Note</strong> All global variables used by GRAPE start with <code>GRAPE_</code>. <p> <p> <h2><a name="SECT004">1.4 Examples of the use of GRAPE</a></h2> <p><p> 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 <a href="CHAP009.htm#SSEC001.1">Partial Linear Spaces</a>, and also in the references <a href="biblio.htm#Cam99"><cite>Cam99</cite></a>, <a href="biblio.htm#CSS99"><cite>CSS99</cite></a>, <a href="biblio.htm#HL99"><cite>HL99</cite></a> and <a href="biblio.htm#Soi06"><cite>Soi06</cite></a>. <p> In the example here, we construct the Petersen graph <var>P</var>, and its edge graph (also called line graph) <var>EP</var>. We compute the global parameters of <var>EP</var>, and so verify that <var>EP</var> is distance-regular (see <a href="biblio.htm#BCN89"><cite>BCN89</cite></a>). <p> <pre> 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 ] ] </pre> <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP002.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> <address>grape manual<br>June 2006 </address></body></html>