<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>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
1266
