Graphs, digraphs, and multidigraphs in GAP
Version 1.0.3
Released 2019-11-29
This project is maintained by James Mitchell, Wilf Wilson
In this directory is a collection of various types of digraphs, which can be loaded into the GAP computational algebra system using the Digraphs package. It is a completely optional addition to the package, which can be used to produce examples of digraphs for use in the package.
The latest version of this library is available at http://gap-packages.github.io/Digraphs.
Simply download the archive, and extract it into the root directory of your
Digraphs installation. This should result in a digraphs-lib
directory inside
your digraphs
directory.
Once the library is installed, simply launch GAP, load the Digraphs package, and
use the ReadDigraphs
function on one of the files in the digraph-lib
directory. This will return a list of digraphs which can be used as required.
Here is an example GAP session:
gap> LoadPackage("digraphs", false);;
gap> filename := Concatenation(DIGRAPHS_Dir(), "/digraphs-lib/latin.g6.gz");;
gap> latin_graphs := ReadDigraphs(filename);
[ <immutable digraph with 100 vertices, 2700 edges>,
<immutable digraph with 121 vertices, 3630 edges>,
<immutable digraph with 144 vertices, 4752 edges>,
<immutable digraph with 169 vertices, 6084 edges>,
<immutable digraph with 196 vertices, 7644 edges>,
<immutable digraph with 225 vertices, 9450 edges>,
<immutable digraph with 256 vertices, 11520 edges>,
<immutable digraph with 289 vertices, 13872 edges>,
<immutable digraph with 324 vertices, 16524 edges>,
<immutable digraph with 361 vertices, 19494 edges>,
<immutable digraph with 4 vertices, 12 edges>,
<immutable digraph with 400 vertices, 22800 edges>,
<immutable digraph with 441 vertices, 26460 edges>,
<immutable digraph with 484 vertices, 30492 edges>,
<immutable digraph with 529 vertices, 34914 edges>,
<immutable digraph with 576 vertices, 39744 edges>,
<immutable digraph with 625 vertices, 45000 edges>,
<immutable digraph with 676 vertices, 50700 edges>,
<immutable digraph with 729 vertices, 56862 edges>,
<immutable digraph with 784 vertices, 63504 edges>,
<immutable digraph with 841 vertices, 70644 edges>,
<immutable digraph with 9 vertices, 54 edges>,
<immutable digraph with 900 vertices, 78300 edges>,
<immutable digraph with 16 vertices, 144 edges>,
<immutable digraph with 25 vertices, 300 edges>,
<immutable digraph with 36 vertices, 540 edges>,
<immutable digraph with 49 vertices, 882 edges>,
<immutable digraph with 64 vertices, 1344 edges>,
<immutable digraph with 81 vertices, 1944 edges> ]
The following files were created by the authors of the Digraphs package:
acyclic.ds6.gz
- Acyclic graphscomplete.g6.gz
- Complete graphscyclic.ds6.gz
- Cyclic graphsempty.s6
- Empty graphs (graphs with no edges)extreme.d6.gz
- Required for DigraphsTestExtremeextreme.ds6.gz
- Required for DigraphsTestExtrememulti.ds6.gz
- Multigraphsrandom.d6.gz
- A few randomly generated digraphssparse.ds6.gz
- Sparse graphs (few edges per vertex)tournament.d6.gz
- TournamentsThe following files contain symmetric digraphs (i.e. graphs) taken from the nauty and Traces website, by Brendan McKay and Adolfo Piperno:
ag.s6.gz
- Affine geometry graphscfi.s6.gz
- Cai, Fuerer and Immerman graphscmz.s6.gz
- Miyazaki graphsgrid.s6.gz
- Grid graphsgrid-sw.s6.gz
- Grid graphs with switched edgeshad.g6.gz
- Hadamard matrix graphshad-sw.g6.gz
- Hadamard matrix graphs with switched edgesk.g6.gz
- Complete graphslatin.g6.gz
- Latin square graphslatin-sw.g6.gz
- Latin square graphs with switched edgeslattice.g6.gz
- Lattice graphsmz.s6.gz
- Miyazaki graphsmz-aug.s6.gz
- Augmented Miyazaki graphsmz-aug2.s6.gz
- Augmented Miyazaki graphs 2paley.g6.gz
- Paley graphspg.s6.gz
- Desarguesian projective plane graphsrnd-3-reg.s6.gz
- Random cubic graphssts.g6.gz
- Steiner triple system graphssts-sw.g6.gz
- Steiner triple system graphs with switched edgestriang.g6.gz
- Triangular graphsThere are also some additional files, added by Jan De Beule, which containing graphs that come from finite geometry, which were
fining.p.gz
contains some graphs coming from finite geometries:
H(5,4)
,
two vertices are adjacent iff they are skew.H(4,4)
, two
vertices are adjacent iff they are skew.Q(4,8)
, two vertices are adjacent iff they are distinct and
incident (no loops!). This is a bipartite graph with diameter 4 and
undirected girth 8.polar_graphs.p.gz
A polar graph is by definition the point graph of a
finite classical polar space. Note that such a geometry is a partial linear
space, so not every pair of points is a pair of collinear points. Two points
are adjacent iff they are distinct and collinear. The diameter of these
graphs is 2, their undirected girth 3, the latter since these spaces contain
lines. Reading in this file requires around 4 Gb of memory.
dual_polar_graphs.p.gz
We consider again finite classical polar spaces.
Such geometries contain points, lines, etc., up to maximal subspaces, which
all have the same projective dimension. The vertices of a dual polar graph
are these maximal subspaces, of dimension, say, d
, and they are adjacent
iff they are distinct and meet in a d-1
dimensional projective subspace.
Reading in this file requires around 5 Gb of memory.
generators_graphs.p.gz
(Parts 1, 2, and 3). We again consider finite
classical polar spaces. The vertices are the maximal subspaces and they are
adjacent iff they are distinct and skew. Reading part 2 requires almost 6 Gb
of memory, and reading part 3 requires another 6 Gb. Reading part 1 requires
much less memory, around 1.5 Gb.
incidence_graphs.p.gz
A generalised polygon of gonality n is a point line
geometry, such that if one considers the incidence graph, i.e. the vertices
are the points and adjacency is incidence (without loops), then it has
diameter n and girth 2n. All graphs in this file are incidence graphs of
generalised polygons. Note that by a famous theorem, thick GPs (i.e. at
least three points on a line and dually, at least three lines on a point),
have gonality 3, 4, 6, or 8. This file contains the incidence graph of the
smallest generalised octogon, some generalised hexagons, and a lot of
generalised quadrangles, and some projective planes. To read it completely,
around 1.5 Gb of memory is required.