Quelle grape.tex Sprache: Latech

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%A  grape.tex               GRAPE documentation              Leonard Soicher
%
%
%
\def\GRAPE{\sf GRAPE}
\def\DESIGN{\sf DESIGN}
\def\nauty{\it nauty}
\def\bliss{\it bliss}
\def\Aut{{\rm Aut}\,}

\Chapter{Grape}

This manual describes the {\GRAPE} (Version~4.9.3) package for computing
with graphs and groups.

{\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 <gamma>
always comes together with a known subgroup <G> of the automorphism
group of <gamma>, and that <G> is used to reduce the storage and
CPU-time requirements for calculations with <gamma> (see
\cite{Soi93} and \cite{Soi04}).  Of course <G> 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).

Certain {\GRAPE} functions make direct or indirect use of the {\nauty}
\cite{MP14} or {\bliss} \cite{JK07} packages, for computing
automorphism groups of graphs and testing graph isomorphism. Such functions
can only be used on a fully installed version of {\GRAPE}. Installation
of {\GRAPE} is described in this chapter of the manual.

Except for the {\nauty} package of B.~D.~McKay included with {\GRAPE},
the function `SmallestImageSet' by Steve Linton, the {\nauty} interface
by Alexander Hulpke, and the initial {\bliss} interface by Jerry James,
the {\GRAPE} package was designed and written by Leonard H. Soicher,
School of Mathematical Sciences, Queen Mary University of London.
Except for the included {\nauty} package, {\GRAPE} is licensed under the
terms of the GNU General Public License as published by the Free Software
Foundation; either version 2 of the License, or (at your option) any later
version. For details, see \URL{https://www.gnu.org/licenses/gpl.html}.
Further licensing and copyright information for {\GRAPE} is contained
in its `README.md' file.

If you use {\GRAPE} in a published work, then please reference the
package as follows:

L.H. Soicher, The {GRAPE} package for {GAP}, Version~4.9.3, 2025,
\URL{https://gap-packages.github.io/grape}.

For questions, remarks, suggestions, and issues, please use the issue
tracker at \URL{https://github.com/gap-packages/grape/issues}.

The development of {\GRAPE} was partially supported by a European Union
HCM grant in ``Computational Group Theory'', and more recently by EPSRC
grant EP/M022641/1 (CoDiMa: a Collaborative Computational Project in
the area of Computational Discrete Mathematics).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Installing the GRAPE Package}

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} (see the main {\GAP} reference section "ref:Installing a GAP
Package"). If you do need to download {\GRAPE}, you can find the most
recent `.tar.gz' archive at \URL{https://gap-packages.github.io/grape}.
The archive file should be downloaded and unpacked in the `pkg'
subdirectory of an appropriate {\GAP} root directory (see the main {\GAP}
reference section "ref:GAP Root Directories").

If your {\GRAPE} installation does not include a compiled binary of
the nauty/dreadnaut programs included with {\GRAPE} and you do not want
to use an already installed version of {\nauty} or {\bliss}, you will
need to perform compilation of the nauty/dreadnaut programs included with
{\GRAPE}, and to do this in a Unix environment, you should proceed as
follows.  After installing {\GAP}, go to the {\GRAPE} home directory
(usually the directory `pkg/grape' of the {\GAP} home directory),
and run `./configure <path>', where is the path of the {\GAP}
home directory.  So for example, if you install {\GRAPE} in the `pkg'
directory of the {\GAP} home directory, run
\begintt
./configure ../..
\endtt
Then run
\begintt
make
\endtt
to complete the installation of {\GRAPE}.

To use {\GRAPE} with a separately installed version of {\nauty} or
{\bliss} you should proceed as follows. Please note that the {\nauty}
interface for {\GRAPE} has only been extensively tested with the
included versions of {\nauty}, and the {\bliss} interface has only
been tested with Version~0.73 of {\bliss}. To use a separately
installed version of {\nauty}, type the following commands in {\GAP}, or
place these commands in your `gaprc' file (see "ref:The gaprc file"), where
`dreadnaut_or_dreadnautB_executable' should be the name of your
dreadnaut or dreadnautB executable file:
\begintt
LoadPackage("grape");
GRAPE_NAUTY := true;
GRAPE_DREADNAUT_EXE := "dreadnaut_or_dreadnautB_executable";
\endtt
To use a separately installed version of {\bliss} instead of {\nauty},
type the following commands in {\GAP}, or place these commands in your
`gaprc' file (see "ref:The gaprc file"), where `bliss_executable' should be
the name of your bliss executable file:
\begintt
LoadPackage("grape");
GRAPE_NAUTY := false;
GRAPE_BLISS_EXE := "bliss_executable";
\endtt
For example, if the bliss executable is `/usr/local/bin/bliss', then type:
\begintt
LoadPackage("grape");
GRAPE_NAUTY := false;
GRAPE_BLISS_EXE := "/usr/local/bin/bliss";
\endtt

You should now test {\GRAPE} and the interface to {\nauty} or {\bliss}
on each architecture on which you have installed {\GRAPE}. Start up
{\GAP} and at the prompt type
\begintt
LoadPackage( "grape" );
\endtt
On-line documentation for {\GRAPE} should be available by typing
\begintt
?GRAPE
\endtt
Then run some tests by typing:
\begintt
Test(Filename(DirectoriesPackageLibrary("grape","tst"),"testall.tst"));
\endtt
This should return the value `true'.

A pdf version of the {\GRAPE} manual is available as `manual.pdf' in the
`doc' directory of the home directory of {\GRAPE}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Loading GRAPE}

Before using {\GRAPE} you must load the package within {\GAP} by typing:

\begintt
LoadPackage("grape");
\endtt

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{The structure of a graph in GRAPE}

In general {\GRAPE} deals with finite directed graphs which may have
loops but have no multiple edges. However, many {\GRAPE} functions only
work for *simple* graphs (i.e. no loops, and whenever $[x,y]$ is an
edge then so is $[y,x]$), but these functions will check if an input
graph is simple.

In {\GRAPE}, a graph <gamma> is stored as a record, with mandatory
components `isGraph', `order', `group', `schreierVector',
`representatives', and `adjacencies'. 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.

The `order' component contains the number of vertices of . The
vertices of <gamma> are always 1,2,...,`<gamma>.order', but they may also
be given *names*, either by a user (using `AssignVertexNames') or by a
function constructing a graph (e.g. `InducedSubgraph', `BipartiteDouble',
`QuotientGraph'). The `names' component, if present, records these
names, with `<gamma>.names[<i>]' the name of vertex . If the `names'
component is not present (the user may, for example, choose to unbind
it), then the names are taken to be 1,2,...,`<gamma>.order'. The `group'
component records the {\GAP} permutation group associated with <gamma>
(this group must be a subgroup of the automorphism group of <gamma>). The
`representatives' component records a set of orbit representatives
for the action of `<gamma>.group' on the vertices of , with
`<gamma>.adjacencies[<i>]' being the set of vertices adjacent to
`<gamma>.representatives[<i>]'. The `group' and `schreierVector'
components are used to compute the adjacency-set of an arbitrary vertex
of <gamma> (this is done by the function `Adjacency').

The only mandatory component which may change once a graph is initially
constructed is `adjacencies' (when an edge-orbit of `.group' is
added to, or removed from, <gamma>). A graph record may also have some
of the optional components `isSimple', `autGroup', `maximumClique',
`minimumVertexColouring', and `canonicalLabelling', which record
information about that graph.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Examples of the use of GRAPE}

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 "Partial Linear Spaces", and also in the references \cite{Cam99},
\cite{CSS99}, \cite{HL99}, \cite{Soi06} and \cite{Soi24b}.

In the example here, we construct the Petersen graph $P$, and its edge
graph (also called line graph) $EP$. We compute the global parameters
of $EP$, and so verify that $EP$ is distance-regular (see \cite{BCN89}).

\beginexample
gap> LoadPackage("grape");
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 ] ]
\endexample

quality100%

¤ Dauer der Verarbeitung: 0.27 Sekunden (vorverarbeitet) ¤

*© Formatika GbR, Deutschland

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.