GRAPE Version 4.8.1, 

a GAP package for computing with graphs and groups, by Leonard H. Soicher,
with contributions from Steve Linton, Alexander Hulpke and Jerry James,
and including Brendan McKay's nauty 2.2 (final patched version) package.

This README document tells you how to install GRAPE and lists changes
made to GRAPE since Version 2.2. License and copyright information is 
in the GRAPE file COPYING. 

Installing GRAPE
----------------
The official GAP Windows distribution includes the GRAPE package
fully installed.  Thus, GRAPE normally requires no further installation
for Windows users of GAP. What follows is for Unix users of GRAPE.

You do not need to download and unpack an archive for GRAPE
unless you want to install the package separately from your main
GAP installation or are installing an upgrade of GRAPE to an
existing installation of GAP.  If you do need to download
GRAPE, you can find the latest archive .tar.gz file for the 
package at  https://gap-packages.github.io/grape 

Installation and testing instructions for the GRAPE package
can be found in Chapter 1 of the GRAPE manual, available from
https://gap-packages.github.io/grape

Referencing GRAPE
-----------------
If you use GRAPE to solve a problem, then please email
L.H.Soicher@qmul.ac.uk, and reference:

L.H. Soicher, The GRAPE package for GAP, Version 4.8.1, 2018, 
https://gap-packages.github.io/grape

------------------------------------------------------------------------

Main changes from GRAPE 4.8 to GRAPE 4.8.1 (October 2018):
----------------------------------------------------------

(1) GRAPE package moved on to github.

(2) Indexing in GRAPE documentation made to work better.

(3) Documentation for CompleteSubgraphsOfGivenSize improved. 

(4) Obsolete POST_RESTORE_FUNCS no longer used.
 

Main changes from GRAPE 4.7 to GRAPE 4.8 (June 2018):
-----------------------------------------------------

(1) New function: HammingGraph

(2) New operations: MaximumClique, MinimumVertexColouring 

(3) New attributes (which cannot be stored in a GRAPE graph record, but 
are declared as attributes rather than operations so as not to
conflict with the Digraphs package): CliqueNumber, ChromaticNumber 

(4) ConnectedComponent and ConnectedComponents are now operations 
rather than functions, to avoid conflicts with other developers.

(5) Enhanced functionality for function VertexColouring, which can 
now be used to determine whether a graph has a proper vertex k-colouring,
and if so, to return such a colouring.  

(6) Efficiency of the function VertexTransitiveDRGs improved for
transitive permutation groups having some orbitals which are not
self-paired.

(7) GRAPE HTML documentation now made with version 4.12 of tth, and
displays correctly on all browsers tested (thanks to Andries Brouwer
for pointing out the problem and to GAP Support for providing a solution). 

(8) The GRAPE HTML documentation links to the GAP reference manual now
work (thanks to Jerome Benoit for providing a solution).

(9) The default location for a user-installed bliss executable (if used) is 
now  ExternalFilename(DirectoriesSystemPrograms(),"bliss") 
(thank you to Jerome Benoit for suggesting this). 
However, the default location of the dreadnaut executable remains
ExternalFilename(DirectoriesPackagePrograms("grape"),"dreadnautB")
to run the included version in GRAPE of nauty/dreadnaut.

(10) Efficiency change to PartialLinearSpaces, to use exact cover
instead of clique search to classify "bundles".

(11) Fixed small efficiency bug in CompleteSubgraphsMain. 


Main changes from GRAPE 4.6.1 to GRAPE 4.7 (January 2016):
---------------------------------------------------------

(1) The included version of nauty is now the final patched 
version of nauty 2.2.

(2) The user may run their own copy of dreadnaut or dreadnautB, 
rather than the included version from nauty 2.2.

(3) The user may run their own version of bliss as an alternative
to nauty. 

(4) A test file tst/testall.g is now included.

(5) Documentation and installation instructions have been revised 
accordingly.

Main changes from GRAPE 4.6 to GRAPE 4.6.1:
-------------------------------------------

(1) Except for nauty 2.2, GRAPE is now licensed under the GPL,
version 2 or higher.

(2) Installation instructions revised.

Main changes from GRAPE 4.5 to GRAPE 4.6:
------------------------------------------

(1) GRAPE revised to work fully under Windows (XP or later), with an
appropriate 32-bit nauty/dreadnaut binary (made by A. Hulpke) included.

(2) Installation instructions revised.

Main changes from GRAPE 4.4 to GRAPE 4.5:
------------------------------------------

(1) Makefile.in revised.

(2) Installation instructions revised.

(3) Default banner now used.

Main changes from GRAPE 4.3 to GRAPE 4.4:
------------------------------------------

(1) With much help from Alexander Hulpke, and using new features in GAP
4.5, the interface between GRAPE and dreadnaut is now done entirely in
GAP code. This means that as long as nauty/dreadnaut can be compiled on
a given computer, then GRAPE should work on that computer, although there
are still problems with Windows machines.

(2) Graphs with colour-classes can now be handled by the automorphism group
and graph isomorphism functions. 

(3) The functions Graph, Diameter, Girth, IsBipartite, IsConnectedGraph,
IsDistanceRegular, IsVertex, and IsEdge are now operations to avoid
possible name conflicts with GAP, GAP users, or other packages.

(4) The internal functions OrbitRepresentatives, RepWord,
OrbitNumbers, NumbersToSets, and IntransitiveGroupGenerators renamed
GRAPE_OrbitRepresentatives, GRAPE_RepWord, GRAPE_OrbitNumbers,
GRAPE_NumbersToSets, and GRAPE_IntransitiveGroupGenerators, respectively,
to avoid possible name conflicts with GAP, GAP users, or other packages.

(5) Documentation upgraded.

(6) GAP code and standalone programs for the undocumented functions Enum
and EnumColadj removed.  It appears no one uses them now, and their
functionality can largely be handled by current documented GAP/GRAPE
functions.

Main changes from GRAPE 4.2 to GRAPE 4.3:
------------------------------------------

(1) GRAPE can now be installed via `/bin/sh configure ../..; make'.

(2) The version of nauty now used is 2.2 final, rather than 2.0beta5,
and canonical labellings may have changed.  Moreover, dreadnautB is now
used instead of dreadnaut, so there is no practical upper bound on the
number of vertices when using nauty.  All graphs stored from previous
versions of GRAPE should have their `canonicalLabelling' component
unbound before use with this version.

(3) Added function `GraphIsomorphismClassRepresentatives', which should be
used for efficient pairwise isomorphism testing of three or more graphs.

(4) `CompleteSubgraphsOfGivenSize' now fully documented to include
the functionality of finding cliques with given vertex vector-weight
sum.

(5) `GraphIsomorphism' now documented, and for safety, `GraphIsomorphism'
now has a third parameter <firstunbindcanon>, behaving as in
`IsIsomorphicGraph'.

(6) For safety, (possibly old) canonical labellings are no longer copied
over to a graph returned by `CopyGraph', `GraphImage' or `NewGroupGraph'.

(7) Changed call to  `StabChainBaseStrongGenerators'  to have three
parameters to conform with the changed functionality in this procedure
from GAP 4.4.5.

(8) Fixed minor problem in Makefile.in (reported by A.E. Brouwer).

(9) The standard archive format is now tar.gz, rather than zoo.

(10) grape.bib moved to manual.bib.

Main changes from GRAPE 4.1 to GRAPE 4.2:
------------------------------------------
(1) Including Steve Linton's `SmallestImageSet' function, and using
this function for faster isomorph rejection in `CompleteSubgraphs',
`CompleteSubgraphsOfGivenSize', and `PartialLinearSpaces'.

(2) Further improvements to `CompleteSubgraphs' and
`CompleteSubgraphsOfGivenSize', including functionality in the latter
which will be required by the `Design' package.

(3) All global function names are now read-only.
 
(4) `OrbitalGraphIntersectionMatrices' is no longer an 
alternative name for `OrbitalGraphColadjMats'.
This change is *not* backward compatible.

(5) The function `Vertices' is now an operation, so as not to
conflict with the xgap package. 

(6) The default value for GRAPE_NRANGRENS has been increased to 18.

(7) Output streams are now used in `AutGroupGraph' and
`SetAutGroupCanonicalLabelling'.

Main changes from GRAPE 4.0 to GRAPE 4.1:
------------------------------------------
(1) Extended functionality of `CompleteSubgraphsOfGivenSize' so that a 
user can request only *maximal* complete subgraphs of a given size to
be returned.
 
(2) Extended functionality of `CompleteSubgraphs' and
`CompleteSubgraphsOfGivenSize' so that the required complete subgraphs
can be classified up to equivalence under the permutation group associated
with the input graph.

(3) Improvements to `CompleteSubgraphs' and `CompleteSubgraphsOfGivenSize'
which sometimes result in significant speed-ups.

(4) The default UNIX file permissions for GRAPE files now include write
permission for the owner. This is to make default file permissions more 
in line with those of GAP.

(5) The naming convention for the vertices of the graphs output (in a
list) by `PartialLinearSpaces' has changed to be more consistent with
vertex-naming conventions in GRAPE.  The point-vertices of such a graph
<delta> are 1,...,`<ptgraph>.order', with the name of point-vertex <i>
being the name of vertex <i> of <ptgraph>. A line-vertex of <delta>
is named by a list (not necessarily ordered) of the point-vertex names
for the points on that line.  
Warning: This change is *not* backward compatible.

(6) For non-simple input graphs, different nauty parameters than
previously are set by `AutGroupGraph' and `SetAutGroupCanonicalLabelling'
(which is called by `IsIsomorphicGraph').  This is in order to avoid a
performance problem with certain sparse directed graphs.
Warning: canonical labellings may be different than before.

(7) Input graph to `CollapsedIndependentOrbitsGraph' must be simple.
(The function did not always produce correct output for non-simple graphs.)

(8) Bug fixed so that `AutGroupGraph' and `SetAutGroupCanonicalLabelling'
always output ranges as full lists for processing as input to
nauty/dreadnaut.

(9) Bug fixed in function `Girth'. This bug could cause wrong answers to
be returned. 

(10) Improved documentation, including an example of research using GRAPE.

(11) Better file management for the non-GAP part of GRAPE.

(12) A p2c translation of tcfrontend4.p is now supplied and used.

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.

Main changes from GRAPE 2.2 to GRAPE 2.31:
------------------------------------------
(1) The new  CompleteSubgraphsOfGivenSize,  which allows for searching in
a vertex-weighted graph for cliques with a given vertex-weight sum.

(2) The new function  PartialLinearSpaces,  which classifies partial linear
spaces with given point graph and parameters  s,t.  

(3) The new function  VertexTransitiveDRGs,  which determines the 
distance-regular generalized orbital graphs for a given transitive 
permutation group.

(4) New functions  CayleyGraph  and  SwitchedGraph.

(5) A one-vertex graph is now considered to be bipartite, 
with bicomponents = [[],[1]] (to be consistent with considering a 
zero-vertex graph to be bipartite, with bicomponents = [[],[]]). 

(6) A bug fixed in the function UnderlyingGraph. That bug had
the effect that if the returned graph had loops, then it 
might have had its isSimple component erroneously set to true.