%-----------------------------------------------------------------------------
% Beginning of grape1.tex
%-----------------------------------------------------------------------------
%
\input amstex
\documentstyle{dimacs}
\NoBlackBoxes
\font\sf=cmss10
\def \GAP {{\sf GAP}}
\def \GRAPE {{\sf GRAPE}}
\def \im {\cong}
\def \cl {\centerline}
\def \ss {\smallskip}
\def \ms {\medskip}
\def \bs {\bigskip}
\def \ds {\displaystyle}
\def \split {\colon}
\def \bec {\colon=}
\def \ns {{}^{\ds .}}
\def \intersect {\cap}
\def \union {\cup}
\def \la {\langle}
\def \ra {\rangle}
\def \x {\times}
\def \a {\alpha}
\def \b {\beta}
\def \G {\Gamma}
\def \D {\Delta}
\def \S {\Sigma}
\def \s {\sigma}
\def \t {\tau}
\def \w {\omega}
\def \W {\Omega}
\def \Aut {\hbox{\rm Aut\,}}
%
\leftheadtext{LEONARD H. SOICHER}
\rightheadtext{GRAPE: FOR COMPUTING WITH GRAPHS AND GROUPS}

\topmatter
\title GRAPE: a System for Computing\\
with Graphs and Groups\endtitle
\author Leonard H. Soicher\endauthor
\address 
School of Mathematical Sciences,
Queen Mary and Westfield College,
Mile End Road,
London E1 4NS,
U.K.
\endaddress  %address for author one
\email L.H.Soicher\@qmw.ac.uk\endemail

%  The following items give publication information for the DIMACS logo
\cvol{00}
\cvolyear{0000}
\cyear{0000}

%  Math Subject Classifications 
\subjclass Primary 05C25, 05C85\endsubjclass

\thanks This paper is in final form and no version of it will be submitted for
publication elsewhere\endthanks

\endtopmatter

\document

\head 1. Introduction                % bold, centered; 
\endhead                             % don't type final punctuation 

This note briefly describes {\GRAPE}, a computer system 
for calculations with graphs and groups.
{\GRAPE} is designed primarily to study
finite graphs arising from group-theoretical and geometrical constructions.

The {\GRAPE} philosophy is that a graph $\G$ always comes together
with a known subgroup $G$ of $\Aut\G$ 
(this is sensible if we assume our graph
comes from a group-theoretical or geometrical construction), and that
$G$ should be used to reduce the storage and 
CPU-time requirements for calculations with $\G$. 
The result is that we are routinely able to do calculations with 
many large symmetric graphs (having 20,000 vertices or more) 
on a SUN Sparcstation~2. 
However, even if $G$ is the trivial group, {\GRAPE} tries not to impose
an unreasonable overhead for trying to use $G$.

The {\GRAPE} system consists of the 
{\GAP} (version 3.1) group theoretical system \cite{11} 
from Aachen, a {\GAP} language library of 
graph-theoretical functions, and some standalone programs integrated 
into the system.
{\GAP} provides a programming language 
(the {\GAP} language), a storage manager, objects such as
lists, sets, records, permutations, and groups, and a library
of group-theoretical routines (written in the {\GAP}
language). {\GAP} also allows the execution of operating system
commands from within {\GAP}, 
and the reading and writing of files. This allows us
to run various efficient standalone programs under a {\GAP}
interface as part of the {\GRAPE} system. 
At present these standalones are the author's coset
enumeration program {\it enum} (although {\GAP} now 
has a coset enumerator), B.D.~McKay's graph 
automorphism and isomorphism program {\it nauty} \cite{8},
and the author's collapsed adjacency matrix program {\it coladj}. 
All computations in the {\GRAPE} system take place via 
{\GAP} functions, so that the running of  
standalone programs is invisible to the user.
This approach allows us the flexibility 
to add programs written in various languages, but still 
to have a standard, high-level programming interface via {\GAP}.
We have in fact found that most of our graph routines are
most easily written in the {\GAP} language, and are 
reasonably efficient in this form. 

{\GRAPE} is being developed by the author at
Queen Mary and Westfield College on a SUN Sparcstation~2, 
but it should be possible to set up {\GRAPE} on most
computers running a version of the {\it UNIX} operating system.    

A predecessor to {\GRAPE}, using
{\GAP}~2.4 \cite{9}, was written by the author during visits
to the Universit\`{a} di Roma ``La Sapienza" and 
the University of Western Australia.
This system has already proved very useful. 
It was instrumental in the discovery of some new distance-regular graphs
\cite{12}, and in the determination of some of their properties. 
For some examples in \cite{5}, the system was
used to construct covers of certain graphs, and to determine the 
automorphism groups of these covers. 
For \cite{6}, the system was used to determine when certain 2-arc 
transitive graphs $QR(q)$ $(q=7,9,17,23,25,31)$
are distance-transitive, as these particular $QR(q)$ 
are not handled by a general result in \cite{6}
($QR(q)$ has $2^{(q+1)/2}$ vertices and valency $q+1$). 
Also, we are using the {\it enum} and {\it coladj} standalone
programs to construct
(most of) the intersection matrices for the 1-arc transitive 
graphs of rank $\le5$
acted on by sporadic simple groups or their automorphism groups
(see \cite{10}). The biggest cases handled so far (on a University of 
London Convex supercomputer) are the intersection matrices for the
1-arc transitive graphs on $1,545,600$ vertices arising from the action 
of Conway's group $Co_1$ on its $3A$-generated subgroups of order 
3 (our notation is that of the ATLAS \cite{4}).

We note that the latest version (3.8) of the group theory system {\it CAYLEY} 
\cite{3} provides graph-theoretical functions and incorporates
the {\it nauty} program. We have found {\it CAYLEY} useful for much
group-theoretical and some graph-theoretical work.
The {\it CAYLEY} approach to graphs is more general than that of 
{\GRAPE}, but the specialist approach of {\GRAPE} allows 
it to work with much larger symmetric graphs than {\it CAYLEY} does.

The reader is referred to \cite{2} for graph-theoretical 
terms not defined here.

\head 2. Representing graphs in {\GRAPE}                % bold, centered; 
\endhead                             % don't type final punctuation 

In general {\GRAPE} deals with finite directed graphs,
possibly with loops, but with no multiple edges.
Let $\G=(V,E)$ be such a graph.  Let $v\in V$, and denote by  
$\G_i(v)$ the set of vertices of $\G$ at distance 
$i$ from $v$, with the convention that $\G(v)=\G_1(v)$.
We suppose $n=|V|$, $V=\{v_1,\ldots,v_n\}$, and
discuss how $\G$ can be represented on a computer. 
The most common methods are by an {\it adjaceny matrix} 
(an $n\x n$ matrix whose $(i,j)$-entry is 1 if $(v_i,v_j)$
is an edge of $\G$, and 0 otherwise), 
or by a list $\G(v_1),\ldots,\G(v_n)$ of adjacency sets. 

An adjacency matrix requires $n^2$ bits of storage, 
it can be inefficient for computations with sparse graphs, 
and requires too much store for $n$ greater than about $15,000$
(with present workstation technology).
Also, constructing an adjacency matrix requires at least $O(n^2)$ steps.
Adjacency matrices are used by {\it nauty} and {\it CAYLEY},
but not by (the {\GAP} part) of {\GRAPE}.

A list of adjacency sets requires at least $O(|E|)$ storage, 
and at least $O(|E|)$  
time for its construction. Thus, such a list is inappropriate for 
a graph with very many edges (if a better way can be found, as
described below).

Suppose now we know a group $G$ of automorphisms of $\G$.
Let $V_1,\ldots,V_k$ be the distinct orbits
of $G$ on the vertex set $V$, with respective representatives 
$v_1,\ldots,v_k$. Clearly, to store $\G$, we need only store
permutation generators for $G$, the list
$v_1,\ldots,v_k$ of orbit representatives, 
and the list $\G(v_1),\ldots,\G(v_k)$. 
This is how a graph is stored in {\GRAPE}, in the form 
of a {\GAP} record. This record also contains a 
Schreier vector (see, for example, \cite{7}) to allow the efficient
calculation of $\G(v)$ for any $v\in V$. 
In practice, we often have $k\le2$, and so this method of
storage can represent a huge saving over conventional 
means. Even if $G$ is trivial, our method is not 
significantly worse than a represention by a complete list of adjacency sets. 

By default in {\GRAPE}, the vertices of a graph $\G=(V,E)$ are 
named $1,\ldots,|V|$, and this is how they are always 
represented internally. Following a suggestion of P.J. Cameron,
we allow an (optional) field called {\tt names} for a graph record, so  
that a user may give his or her names for the vertices
(these names can be integers, sets, vectors, or indeed, any {\GAP} 
type). If a subgraph of $\G$ is created then this subgraph inherits
its vertex names from $\G$.

\head 3. Some {\GRAPE} functions                % bold, centered; 
\endhead                             % don't type final punctuation 

The most common way for a graph to be constructed in {\GRAPE}
is to start with a permutation group $G$ of degree $n$, and 
a set $S$ of ordered pairs of elements of $\{1,\ldots,n\}$, and then
to construct $\G$ to have vertex set $\{1,\ldots,n\}$, and edge 
set the union of the $G$-orbits of the elements of $S$.
We are then able to associate the group $G$ with $\G$, and 
to construct $\G$, we only determine the adjacency sets for the 
orbit representatives $v_1,\ldots,v_k$, say, of $G$ on $\{1,\ldots,n\}$. 
This calculation is made especially easy if we know (generators for)
the stabilizers in $G$ for each of the $v_i$.
Many {\GRAPE} functions allow the user to input such additional 
useful information, if known,  to make the functions run faster. 

Now, for ease of exposition, we assume that our graph
$\G=(V,E)$ is undirected and has no loops. As before,
we suppose $G\le\Aut\G$ has $k$ orbits on the vertices
of $\G$, with representatives $v_1,\ldots,v_k$.

Many properties of $\G$ can be determined by {\GRAPE} functions;
for example, connected components, diameter, girth, and various regularity
properties, such as whether $\G$ is distance-regular.
Also, given a subset $X$ of $V$, {\GRAPE} can determine if
$X$ is a distance-regular code.

{\GRAPE} can construct induced subgraphs of $\G$, such as the 
induced subgraph $\D$ on a set $\G_i(v)$. 
Here, the group associated with $\D$ is the vertex stabilizer $G_v$ 
acting on $\G_i(v)$ (if the user does not provide a group).
If we do not already know this stabilizer then we can quickly construct an 
approximation $H\le G_v$ using random methods (see \cite{1} and \cite{7}). 
This is adequate as we need only be sure that $H$ acting on 
$\G_i(v)$ is a subgroup of $\Aut\D$, and
in practice we will almost always have $H=G_v$.
Approximations of this sort are used in some other {\GRAPE} functions.
    
The most important function in {\GRAPE} is called {\tt LocalInfo},
and is used by many other procedures. 

The function {\tt LocalInfo} performs a calculation similar to
a breadth-first search in $\G$, 
starting at a given vertex $v$ to successively determine 
$$\G_0(v),\G_1(v),\G_2(v),\ldots,$$ among other things. (Here, as you might
expect, we first calculate the orbits of (an approximation to) 
$G_v$ and then we only look at the adjacency sets of 
representatives of these orbits.)
Thus, one thing {\tt LocalInfo} determines is the connected component
of $\G$ containing $v$. 

Now suppose $\G$ is connected. For $v\in V$ let $d_v$ denote 
the maximum distance from $v$ to any vertex of $\G$.
Thus {\tt LocalInfo} determines $d_v$, and we have that
the diameter of $\G$ is just max$\{d_{v_1},\ldots,d_{v_k}\}$.

Suppose $v,w\in V$, and $w\in\G_i(v)$. Then {\tt LocalInfo},
in the process of performing its breadth-first search starting at
$v$, determines the numbers
$$\eqalign{c_i(v,w)&=|\G_{i-1}(v)\cap\G(w)|,\cr
a_i(v,w)&=|\G_{i}(v)\cap\G(w)|,\cr
b_i(v,w)&=|\G_{i+1}(v)\cap\G(w)|.}$$
(Note that these quantities are constant as $w$ varies
over an orbit of $G_v$).

Now define $g_v$ to be the length of the shortest circuit 
containing $v$, if $v$ is in a circuit, and define $g_v=\infty$
otherwise. Now let $t$ be the least $i$ such that 
some $c_i(v,w)\ge2$ or some $a_i(v,w)\ge1$, if such an 
$i$ exists. If no such $i$ exists then $g_v=\infty$.
Otherwise, if $c_t(v,w)\ge2$ for some $w$, then $g_v=2t$, else
$g_v=2t+1$. We also have that the girth
of $\G$ is min$\{g_{v_1},\ldots,g_{v_k}\}$.   

The function {\tt LocalInfo} saves a $c_i(v,w)$, $a_i(v,w)$, or
$b_i(v,w)$ just if it depends only on $i$ and $v$ (and not 
$w$). Such {\it parameters} $c_i(v),a_i(v),b_i(v)$,
if and when they exist,
are used in the determination of many regularity properties of
$\G$, the strongest of which is distance-regularity.            
A function very similar to {\tt LocalInfo}
can determine if a given subset of the vertices of $\G$ is
a distance-regular code.
   
Finally, it is possible to use {\GRAPE} functions as an 
interface to {\it nauty} to determine the automorphism group
of a (vertex-coloured) graph, and to test if two graphs 
are isomorphic, if these graphs are not too large.

\head 4. Note added: 20 August 1992                % bold, centered; 
\endhead                             % don't type final punctuation 

The {\GRAPE} system and a beginning user's guide \cite{13}
are available from the author.
The {\GRAPE} library now contains over 50 graph-theoretical 
functions, many of which were written while the author
was visiting the State University of Ghent. 
All the functionality of the {\GRAPE} system, except
for the ability to compute graph automorphism groups and test
for graph isomorphism, can now be achieved by {\GAP} code alone.

New features in {\GRAPE} include the ability to analyse 
the clique structure of a graph, as well as certain other induced
subgraph structure, and also functions for constructing
quotient graphs, bipartite doubles, point graphs, and 
edge graphs.

\Refs

\ref \no 1
\by L. Babai, G. Cooperman, L. Finkelstein and A. Seress 
\paper Nearly linear time algorithms for permutation groups with a small base 
\inbook ISSAC '91
\publ ACM Press \publaddr New York \yr 1991
\pages 200--209 
\endref
\ref \no 2
\by A.E. Brouwer, A.M. Cohen and A. Neumaier 
\book Distance-Regular Graphs
\publ Springer \publaddr Berlin and New York \yr 1989
\endref
\ref \no 3
\by J.J. Cannon
\paper An introduction to the group theory language, Cayley
\inbook Computational Group Theory
\ed M.D. Atkinson
\publ Academic Press \publaddr London \yr 1984
\pages 145--183
\endref
\ref \no 4
\by J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker and R.A. Wilson
\book  An ATLAS of Finite Groups
\publ Clarendon Press
\publaddr Oxford \yr 1985 
\endref
\ref \no 5
\by D.R. Hughes
\paper Regular covers of graphs and structures
\toappear
\endref
\ref \no 6
\by A.A. Ivanov and C.E. Praeger
\paper On finite affine 2-arc transitive graphs
\publ University of Western Australia Pure Mathematics Research Report, 1992
\endref
\ref \no 7
\by J.S. Leon 
\paper On an algorithm for finding a base and 
strong generating set for a group given by generating permutations
\jour Math. Comp. \vol 35 \yr 1980 \pages 941--974 
\endref
\ref \no 8
\by B.D. McKay
\paper {\it nauty} user's guide (version 1.5) 
\publ Technical report TR-CS-90-02, Computer Science Department, 
Australian National University, 1990
\endref
\ref \no 9
\by A. Niemeyer, W. Nickel and M. Sch\"onert 
\book GAP: Getting Started and Reference Manual
\publ Lehrstuhl D f\"ur Mathematik 
\publaddr RWTH Aachen \yr 1988
\endref
\ref \no 10
\by C.E. Praeger and L.H. Soicher
\paper Permutation representations and orbital graphs for the
sporadic simple groups and their automorphism groups:
rank at most five
\toappear
\endref
\ref \no 11
\by M. Sch\"onert, et. al.
\book GAP: Groups, Algorithms and Programming
\publ Lehrstuhl D f\"ur Mathematik
\publaddr RWTH Aachen \yr 1992 
\endref
\ref \no 12
\by L.H. Soicher
\paper Three new distance-regular graphs
\jour Europ. J. Combinatorics \toappear
\endref
\ref \no 13
\by L.H. Soicher
\paper Getting started with GRAPE
\publ preprint, QMW, 1992
\endref
\endRefs

\enddocument
