Graphs, digraphs, and multidigraphs in GAP
Version 0.12.1
Released 2018-04-26
This project is maintained by J. D. Mitchell
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 the following link:
http://gap-packages.github.io/Digraphs/
Simply download it and extract the archive 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 := "~/gap/pkg/digraphs/digraphs-lib/latin.g6.gz";;
gap> latin_graphs := ReadDigraphs(filename);
[ <digraph with 100 vertices, 2700 edges>,
<digraph with 121 vertices, 3630 edges>,
<digraph with 144 vertices, 4752 edges>,
<digraph with 169 vertices, 6084 edges>,
<digraph with 196 vertices, 7644 edges>,
<digraph with 225 vertices, 9450 edges>,
<digraph with 256 vertices, 11520 edges>,
<digraph with 289 vertices, 13872 edges>,
<digraph with 324 vertices, 16524 edges>,
<digraph with 361 vertices, 19494 edges>,
<digraph with 4 vertices, 12 edges>,
<digraph with 400 vertices, 22800 edges>,
<digraph with 441 vertices, 26460 edges>,
<digraph with 484 vertices, 30492 edges>,
<digraph with 529 vertices, 34914 edges>,
<digraph with 576 vertices, 39744 edges>,
<digraph with 625 vertices, 45000 edges>,
<digraph with 676 vertices, 50700 edges>,
<digraph with 729 vertices, 56862 edges>,
<digraph with 784 vertices, 63504 edges>,
<digraph with 841 vertices, 70644 edges>,
<digraph with 9 vertices, 54 edges>,
<digraph with 900 vertices, 78300 edges>,
<digraph with 16 vertices, 144 edges>,
<digraph with 25 vertices, 300 edges>,
<digraph with 36 vertices, 540 edges>,
<digraph with 49 vertices, 882 edges>,
<digraph with 64 vertices, 1344 edges>,
<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 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 containing graphs coming from finite geometry:
fining.p.gz
- contains some graphs comining from finite geometries:
(1): vertices are the generators of the hermitian polar space H(5,4), two vertices are adjacent iff they are skew
(2): vertices are the generators of the hermitian quadrangle H(4,4), two vertices are adjacent iff they are skew
(3): vertices areh the points and lines of the classical generalized quadrangle Q(4,8), two vertics are adjacent iff
they are incident (and no loops!). This is a bipartite graph with diameter 4 and undirected girth 8
(4): the bipartite graph (see (3)) of an elation generalized quadrangle. This one was constructed as a coset geometry.
(5): the bipartite graph of the split Cayley hexagon of order 4, diameter is 6 and girth is 12.
(6): the bipartite graph of the Ree-Tits generalized octagon! This one has diameter 8 and girth 16!
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 differe and they are collinear. The diamter of
these graphs is 2, their undirected girth 3, the latter since these spaces
contain lines. Reading in this file requires around 4 Gb.
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 d say, and they
are adjacent iff they differ and meet in a d-1 dimensional projective
subspace. Reading in this file requres around 5Gb.
generators_graphs.p.gz
(parts 1, 2 and 3). We consider again finite
classical polar spaces. The vertices are the maximal subspaces and they
are adjacent iff they differ and are skew. Reading part 2 requires almost
6Gb, reading part 3 requires again 6Gb. Reading part 1 requires much less
(around 1.5Gb).
incidence_graphs.p.gz
a generalized 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 the lines, adjacency is incidence (withouth
loops), then it has diameter n and girth 2n. All graphs in this repository
are incidence graphs of generalized 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. The repository
contains the incidence graph of the smallest generalized octogon, some
generalized hexagons, and a lot of generalized quadrangles, and some
projective planes. To read it completely, around 1.5Gb is requiered.
which were added by Jan De Beule.