GRAPE 4.0 Share Package for Computing with Graphs
                    Leonard H. Soicher
--------------------------------------------------------

I am pleased to announce the GRAPE 4.0 share package for computing with
graphs, especially those related to groups, designs or finite
geometries. GRAPE 4.0 is the first version of GRAPE for GAP 4, and is
designed to run under GAP 4b5 with bugfixes 1-3 installed. I heartily
thank Alexander Hulpke for huge amounts of help in converting GRAPE to
work well under GAP4.

The library has been completely overhauled, employing some new GAP4
features. However, I have tried to make as few changes as possible to
the user interface. The changes that have been made are detailed at the
end of this announcement (and in the GRAPE README file). They should be
noted by all previous users of GRAPE.

The new features in GRAPE 4.0 mostly come from new versions of
functions which were added to, but not documented in, previous versions
of GRAPE. These include the functions CayleyGraph and
SwitchedGraph, as well as VertexTransitiveDRGs, which determines the
distance-regular generalized orbital graphs for a given transitive
permutation group, and PartialLinearSpaces, which classifies the
partial linear spaces with given point graph and parameters. Also note
the options for CompleteSubgraphsOfGivenSize. You are strongly urged
to consult the expanded and improved documentation in GRAPE 4.0.

Please read the installation instructions below. The archive file
grape.zoo can be found by going to

http://www-gap.dcs.st-and.ac.uk/~gap/Info4/share.html

clicking on GRAPE and then dowloading the current version: 4.0 (for GAP4).

If you install GRAPE, then please tell L.H.Soicher@qmw.ac.uk, where you
should also send any comments and bug reports.

Installing GRAPE
-----------------

To install GRAPE 4.0 (as a GAP4 Share Library Package) unpack the
archive file in a directory in the `pkg' hierarchy of your version of
GAP4. (This might be the `pkg' directory of the GAP4 home directory; it
is however also possible to keep an additional `pkg' directory in your
private directories, see section "ref:Installing Share Packages" of the
GAP4 reference manual for details on how to do this.) Go to the
appropriate `pkg' directory, and then run `unzoo -x grape.zoo'.

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 and call `./configure <path>'
where <path> is the path to the GAP home directory. So for example, if
you install GRAPE in the main `pkg' directory call

./configure ../..

This will fetch the architecture type for which GAP has been compiled last
and create a `Makefile'. Now call

make

to give a list of target architectures for which nauty can be compiled within
GRAPE. Select the most suitable target and type

make <target>

to compile the binary and to install it in the appropriate place.
For example, if you are on a LINUX system with gcc, type

make linux-gcc

This completes the installation of GRAPE for a single architecture. If
you use this installation of GRAPE on different hardware platforms you
will have to compile the binary for each platform separately. This is
done by calling `configure' and `make <target>' for the package anew
immediately after compiling GAP itself for the respective
architecture. If your version of GAP is already compiled (and has last
been compiled on the same architecture) you do not need to compile GAP
again; it is sufficient to call the `configure' script in the GAP home
directory.

You should now test GRAPE and the interface to nauty. Start up GAP and
at the prompt type

RequirePackage( "grape" );

On-line documentation for GRAPE should be available by typing

?GRAPE

The command

IsIsomorphicGraph( JohnsonGraph(7,3), JohnsonGraph(7,4) );

should return `true', and

Size( AutGroupGraph( JohnsonGraph(4,2) ) );

should be `48'.

Both dvi and PostScript versions of the GRAPE manual are available
(as `manual.dvi' and `manual.ps' respectively) in the `doc' directory
of the home directory of GRAPE.

Referencing GRAPE:
------------------

If you use GRAPE to solve a problem then please send a short email to
`L.H.Soicher@qmw.ac.uk' about it, and reference the GRAPE package as
follows:

Leonard H. Soicher. GRAPE: a system for computing with graphs and
groups. In Larry Finkelstein and William M. Kantor, editors, Groups and
Computation, volume 11 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pages 287-291. American Mathematical
Society, 1993.

If your work made use a function depending on the nauty package then
you should also reference nauty as follows:

Brendan D. McKay. nauty user's guide (version 1.5), Technical report
TR-CS-90-02. Australian National University, Computer Science
Department, 1990. See also `http://cs.anu.edu.au/people/bdm/nauty/'.

Main changes from GRAPE 2.31 to GRAPE 4.0:
------------------------------------------

(1) GRAPE 4.0 is compatible with GAP4, but not with GAP3.

(2) The version of nauty now used is 2.0beta5, rather than 1.7, and
canonical labellings may have changed. All graphs stored from previous
versions of GRAPE should have their canonicalLabelling component unbound
before use with this version.

(3) IsIsomorphicGraph by default now unbinds any canonicalLabelling
components of the input graphs. This is always safe, but will downgrade
performance if testing pairwise isomorphism for many graphs. See the
GRAPE manual documentation on changing the default.

(4) The no longer needed functions MakeStabChainGivenLimit and
NextSizeCompleteSubgraphs were removed.

(5) The names component of a graph (if present) is immutable
(unless explicitly stored otherwise by the user, which is *not* recommended).
Also the representatives and schreierVector components of a graph
are immutable (and these should *never* be changed by a user).

(6) The names of an EdgeGraph or a QuotientGraph are lists, but need
no longer be sets (strictly sorted lists). This also applies to
a CollapsedIndependentOrbitsGraph and a CollapsedCompleteOrbitsGraph.
The reason for this is that GAP4 does not support a total order on
all possible GAP4 objects.

(7) ConnectedComponents returns a strictly sorted list.

(8) The function GraphIsomorphism returns fail (instead of false)
if the input graphs are not isomorphic.

(9) GraphImage(gamma) has appropriate names even when gamma.names is
unbound.

(10) The preferred name for OrbitalGraphIntersectionMatrices is
OrbitalGraphColadjMats.

(11) CompleteSubgraphs and CompleteSubgraphsOfGivenSize improved.
The default for arg[5] is now true in CompleteSubgraphsOfGivenSize.
Cliques is now another name for CompleteSubgraphs, and
CliquesOfGivenSize is another name for CompleteSubgraphsOfGivenSize.

(12) The documentation has been expanded and improved.