Copyright © 2014-20 by Jan De Beule, Julius Jonušas, James D. Mitchell, Michael Torpey, Wilf A. Wilson et al.
Licensing information can be found in the
This is a minor release adding the new functionality
IsBridgeless James D. Mitchell.
This is a minor release where some of the documentation has been fixed and the installation instructions have been improved James D. Mitchell, some changes were made for compatibility with future versions of GAP Max Horn and Wilf A. Wilson.
This is a minor release adding some new features to Digraphs, principally functionality relating to computing matchings by Reinis Ciprons, and an implementation of Dijkstra’s algorithm for shortest paths by Markus Pfeiffer and Maria Tsalakou, and methods for producing a concise string representation of a digraph by Murray Whyte.
As of this version, Digraphs requires the datastructures package to be available, in version 0.2.5 or newer.
This is a minor release adding the new configuration flag
--without-intrinsics and checking that the compiler is in C99 mode by using
This is a minor release that includes some new features and some performance improvements.
The following issues were resolved, pull requests merged, or new features added:
Issue #40: If bliss is used to compute the automorphism group of a digraph, then the size of the automorphism group is returned from bliss to GAP, and the group object in GAP immediately knows its size. In particular, it is not necessary to recalculate this size. This was reported and fixed in PR #278 by Chris Jefferson.
In the function
HomomorphismDigraphsFinder, it is now possible to specify a
subgroup of the automorphism group of the range digraph. This way, the
automorphism group of the range digraph is not computed by
HomomorphismDigraphsFinder. This can result in a performance improvement
in some cases. This was reported and fixed in
PR #285 by
HomomorphismDigraphsFinder sometimes did not return any
homomorphisms when the source digraph had exactly one vertex. This was caused
by the data structures used by
HomomorphismDigraphsFinder not being
correctly initialised in this case. This issue was reported by Finn Smith
and fixed by James D. Mitchell in
In PR #283, Finn Smith
added the new operation
DigraphsRespectsColouring, which can be used to
check whether a transformation or permutation between digraphs respects given
colourings. New versions of
IsDigraphHomomorphism, and friends, were added
that accept colourings as arguments and which use
The version of bliss included in Digraphs was updated to allow all of its
data structures to be modified in-place rather than allocated and deallocated
repeatedly. The function
HomomorphismDigraphsFinder was modified to make
use of this new functionality in bliss, and subsequently the performance
HomomorphismDigraphsFinder has been improved (particularly in cases
where many homomorphisms between distinct small digraphs are found). This
was done by James D. Mitchell in
Some further minor performance improvements were made, and a compiler warning was fixed.
This is a minor release that fixes some bugs related to mutability in
This is a minor release that fixes several bugs:
GeneratorsOfEndomorphismMonoidsometimes incorrectly stored its result. This was reported by Chris Jefferson in Issue #251 and fixed by James D. Mitchell in PR #265.
ViewStringof known non-complete digraphs, where such digraphs were described as being complete. This was reported by Murray Whyte in Issue #272 and fixed by Wilf A. Wilson in PR #273.
This is a minor release of the Digraphs package. The main change in this
release is the reintroduction of the three-argument version of
DigraphAddVertices, which accepts a digraph, a number of vertices to add, and
a list of labels for the new vertices. The removal inadvertantly broke
backwards compatbility with some third-party pre-existing code that relied on
this functionality in the Digraphs package (see
The second argument of the three-argument version was redundant, and so a new
two-argument version of
DigraphAddVertices, which accepts a digraph and a list
of new vertex labels, was introduced in v1.0.0. Unfortunately, the concurrent
removal of the three-argument version of
DigraphAddVertices was not advertised
CHANGELOG. Although the three-argument version has been reintroduced,
it will remain undocumented, since there is no good reason for any new code to
use the three-argument version.
The author contact data on the title page of the manual was also updated.
The changes in this version were made by Wilf A. Wilson.
This is a major release of the Digraphs package that introduces significant new functionality, some changes in behaviour, general improvements, and several small bugfixes. With this version, we welcome Reinis Cirpons as a contributor to the package.
ViewStringfor immutable digraphs attempts to show more of the known information about the digraph. This will break tests that relied on the previous behaviour, that contained only the numbers of vertices and edges.
QuotientDigraphhas been changed so that it no longer returns digraphs with multiple edges.
IsEulerianDigraphwould previously return
truefor digraphs that are Eulerian when their isolated vertices were removed, which contradicted the documentation.
falsefor all digraphs that are not strongly connected.
DigraphColoring(American-style spelling) for
Previously, every digraph in the Digraphs package was an immutable, attribute-storing digraph. It is now possible to create mutable digraphs. Mutable digraphs are not attribute-storing, but they can be altered in place - by adding or removing vertices and edges - which, unlike with immutable digraphs, does not require a new copy of the digraph to be made. This can save time and memory.
This is particularly useful when one wants to create a digraph, alter the digraph in some way, and then perform some computations. One can now typically do this with fewer resources by creating a mutable digraph, modifying it in place, and then converting it into an immutable digraph (which can store attributes and properties), before finally performing the computations.
Every digraph now belongs to precisely one of the categories
IsImmutableDigraph, according to its mutability. A mutable digraph can be
converted in-place into an immutable digraph with
MakeImmutable. The are
various new and updated functions for creating mutable and immutable digraphs,
and for making mutable or immutable copies.
Most digraph-creation functions in the package now accept an optional first
argument, that can be either
one of these filters, the function will according create the digraph to be of
the appropriate mutability. When this is option available, the default is
always to create an immutable digraph.
On the whole, for a function in the package that takes a digraph as its argument and again returns a digraph, the function now returns a digraph of the same mutability as its result, and moreover, given a mutable argument, it converts the mutable digraph in-place into the result. However, please consult the document to learn the exact behaviour of any specific function.
Foo in the package that take and return a single digraph have
been converted into the operation
Foo, with a corresponding new attribute,
FooAttr. This means that the getter and setter functions,
SetFoo, are renamed to
for an example. For an immutable (and therefore attribute-storing) digraph,
FooAttr and returns an immutable digraph, which it
stores, and so the effect is as before. For an mutable digraph, calling
modifies the digraph in-place, which remains mutable.
The majority of the changes in Digraphs relating to mutable and immutable digraphs were made by James D. Mitchell, Finn Smith, and Wilf A. Wilson, with some further contributions by Reinis Cirpons, Luke Elliott, and Murray Whyte.
The package now includes the following new functions:
AsSemigroupcan produce strong semilattices of groups (i.e. Clifford) from semilattice digraphs, groups, and homomorphisms. This functionality was added by Finn Smith in PR #161.
BlissAutomorphismGroupcan now take an optional third argument that specifies an edge colouring for the digraph. In this case, the functions return only automorphisms of the digraph that preserve the edge colouring (and the vertex colouring, if one is given). This brilliant new functionality was added by Finn Smith in PR #186.
NrSpanningTreeswere introduced by Reinis Cirpons in PR #224.
DigraphDirectProduct, along with the companion functions
DigraphDirectProductProjections, were introduced by Reinis Cirpons in PR #228.
DigraphMycielskianwas added by Murray Whyte in PR #194.
DigraphNrStronglyConnectedComponentswas added by Murray Whyte in PR #180.
DigraphOddGirthwas added by Murray Whyte in PR #166
IsDigraphCorewere added by Murray Whyte in PRs #221 and #217, respectively.
DotHighlightedDigraphwas added by Finn Smith in PR #169.
IsCompleteMultipartiteDigraphwas added by Wilf A. Wilson in PR #236.
IsEquivalenceDigraphwas added by Wilf A. Wilson in PR #234 as a synonym for
IsReflexiveDigraph and IsSymmetricDigraph and IsTransitiveDigraph.
IsEdgeTransitivewere added by Graham Campbell in PR #165.
GeneralisedPetersenGraphwere added by Murray Whyte in PRs #181 and #204, respectively.
RandomLatticewas added by Reinis Cirpons in PR #175.
--with-external-bliss) and use the Digraphs package with the system version of
blisswas added by Isuru Fernando in PR #225.
--with-external-planarity) and use the Digraphs package with the system version of the Edge Addition Planarity Suite was added by James D. Mitchell in PR #207.
This is a minor release that fixes a few bugs.
In previous versions, the homomorphism-finding tools sometimes returned
purported ‘monomoprhisms’ that were not injective. This problem was reported by
Gordon Royle, see
and fixed by James D. Mitchell in
In addition, Wilf A. Wilson
fixed a bug
DigraphNrEdges. This function could previously lead to a crash when given a
OutNeighbours contained entries not in
This is a minor release that fixes a typo in the documentation of
JohnsonDigraph, and contains some minor tweaks for compatibility with
future versions of GAP.
This is a minor release that updates Digraphs for compatibility with the
upcoming GAP 4.11, and resolves a bug in
IsHamiltonianDigraph that could have
lead to the boolean adjacency matrix of a digraph being accidentally modified;
see Issue #191 and
This is a minor release of the Digraphs package, which improves the compatibility of Digraphs with cygwin. In particular, in the Windows installer of the next release of GAP, Digraphs should be included in a pre-compiled and working state. See Issue #177 and PR #178 for more details.
Digraphs now requires version 4.8.2 of the orb package, or newer.
This release contains several substantial new features, and some changes to previous functionality.
The most significant change in behaviour is related to the Digraph6 format used in previous versions of the Digraphs package. This method of encoding directed graphs was developed independently from, but concurrently with, the Digraph6 format introduced by nauty; see Issue #158 for more information. The Digraphs package now uses the nauty format, although digraphs encoded using the old format can still be read in. This incompatibility was reported by Jukka Kohonen, and the changes were made by Michael Torpey in PR #162.
Other additions and changes are listed below:
DigraphColouringwas renamed to
DigraphGreedyColouring, and its performance was improved; it now uses the Welsh-Powell algorithm, which can be accessed directly via
DigraphWelshPowellOrder. The behaviour of
DigraphGreedyColouringcan be modified by including an optional second argument; see the documentation for more information. This work was done by James D. Mitchell in PR #144.
DigraphShortestPathwas introduced by Murray Whyte in PR #148.
IsAntiSymmetricDigraph(with a capital S) was added as a synonym for
RandomDigraphnow allows a float as its second argument; by James D. Mitchell in PR #159.
CharacteristcPolynomialfor a digraph was added by Luke Elliott in PR #164.
IsEdgeTransitivefor digraphs were added by Graham Campbell in PR #165.
This release contains bugfixes and a couple of new features.
AsMonoidfor lattice and semilattice digraphs were added by Chris Russell in PR #136.
IsDigraphColouringwas added by James D. Mitchell in PR #145.
ArticulationPointswould sometimes contain repeated vertices (reported by Luke Elliott in Issue #140, and fixed by James D. Mitchell in PR #142).
x86intrin.hwas unnecessarily being included by the kernel module of Digraphs (reported by Wilf A. Wilson in Issue #147, and fixed by James D. Mitchell in PR #152).
Digraphs now requires version 4.8.1 of the orb package, or newer.
This release of Digraphs contains some bugfixes, along with the following new features:
Splashis now configurable, thanks to Markus Pfeiffer.
IsQuasiorderDigraphwere introduced by Chris Russell, along with the following functions for visualising these kinds of digraphs:
Digraphs now requires version 4.9.0 of GAP, or newer.
This is a minor release which contains some small adjustments to the build system of the package.
This is a minor release, which contains several bugfixes. The following problems were resolved by James D. Mitchell:
HomomorphismDigraphFindersometimes failed to find a homomorphism when one existed [Issue #111, reported by Gordon Royle];
HomomorphismDigraphFinderwas incomplete [Issue #112]; and
This release contains bugfixes and new features. In particular, it:
IsBiconnectedDigraph[Wilf A. Wilson];
IsChainDigraph[Ashley Clayton]; and
Digraphs now requires version 4.5.1 of the IO package.
The principal change in Digraphs version 0.11.0 is the addition of support for computing automorphisms, canonical labellings, and isomorphisms of digraphs with nauty. This functionality requires the NautyTracesInterface package for GAP, version 0.2 or newer. However, this is not a required package, and the default engine remains bliss. It is possible to specify the engine that is used by Digraphs. These changes to Digraphs were made by James D. Mitchell].
In particular, version 0.11.0 includes the following changes:
DigraphCanonicalLabellingis replaced by
NautyCanonicalDigraphare introduced [Chris Russell and James D. Mitchell].
IsHamiltonianDigraph and the attribute
added by Luke Elliott. Additionally, this release fixes several bugs, including
DigraphSymmetricClosure and one in
Digraphs now requires version 4.4.6 of the IO package.
This is a minor release, which contains performance improvements, and fixes a
Digraph that could cause a segmentation fault.
This release contains new features, bugfixes, and minor improvements to the
documentation. There is a new method for
ChromaticNumber, which has better
performance than the previous method
and James D. Mitchell].
A bug in the code for calculating homomorphisms of digraphs, which could cause
a crash, was resolved [James D. Mitchell].
All of the new features were added by James D. Mitchell.
This release introduces several new features.
The following attributes and properties were added by James D. Mitchell:
ArticulationPoints(and its synonym
The following operations related to matchings were added by Isabella Scott and Wilf A. Wilson:
This is a minor release, which updates the README file and updates the list of package authors and contributors.
This release contains new features, several minor bugfixes, and minor improvements to the documentation of the package.
This release introduces the new operations
[Wilf A. Wilson],
along with the following properties and operations related to semilattices
This is a minor release, which fixes bugs in
IsAntisymmetricDigraph that could trigger segmentation faults.
This release introduces several new features, changes some existing functionality, and improves the documentation. The changes in this release were made by Wilf A. Wilson.
DigraphCanonicalLabellingfor a digraph and a vertex-colouring now accept a multidigraph as their first argument;
IsomorphismDigraphsnow accept multidigraphs, and they also accept vertex-colourings as optional arguments.
UndirectedSpanningForestare introduced; and
IsSubdigraphis changed in the case that it is given one or two multidigraphs.
DigraphColouring(and its synonym,
DigraphColoring) is now an attribute.
This is a minor release. This release fixes a bug in
AsDigraph for a
transformation and an integer. The operations
OutNeighborsCopy are renamed to
OutNeighborsMutableCopy, respectively, and new operations
InNeighborsMutableCopy are introduced.
This is a major release, adding a variety of new operations and attributes for Digraphs, as well as improving some functions and improving the package’s documentation. In this version, we welcome Luke Elliott and Markus Pfeiffer as new authors.
CompleteMultipartiteDigraphis introduced. [Stuart Burrell and Wilf A. Wilson]
WriteDIMACSDigraphare introduced. [Wilf A. Wilson]
ChromaticNumberis introduced. [James D. Mitchell and Wilf A. Wilson]
IsUndirectedTreeare introduced. [Luke Elliott]
IsEulerianDigraphis introduced. [Luke Elliott]
This is a minor release containing one bugfix and several other minor changes. Digraphs now works when it and GAP are compiled in 32 bit mode.
This release contains some bugfixes, some minor new features, and some performance improvements. The package has moved to GitHub and we welcome Finn Smith as an author.
This release contains a new technique for encoding a vertex-coloured digraph as a vertex-coloured (undirected) graph while preserving the automorphism group, in order to calculate the automorphism group using bliss. These changes were made by Finn Smith. The previous technique involved adding two intermediate vertices for every edge; on a digraph with
n vertices this could add
2n(n-1) new vertices. The new technique encodes a digraph with
n vertices as a graph with
3n vertices. In certain cases, this can lead to a dramatic improvement in the time taken to calculate the automorphism group.
The new reduction is based on two techniques in:
David Bremner, Mathieu Dutour Sikiric, Dmitrii V. Pasechnik, Thomas Rehn, Achill Schürmann. Computing symmetry groups of polyhedra. https://arxiv.org/abs/1210.0206v3
Namely, “Dealing with digraphs” followed by “Reduction by superposition”. From the graph obtained by these techniques,
n vertices which are irrelevant to automorphism finding are removed.
The actual reduction used is as follows: Given a digraph
D=(V=1 .. n],E,c), create three copies
V3 of the vertex set
V1 according to the colouring
V3 with two distinct colours that do not occur in
D. Connect each vertex in
V1 to the corresponding vertices in
V3. For every arc
E, put an edge between the copy of
V2, and the copy of
V3. Automorphisms of this graph, when restricted to
V, are precisely the automorphisms of
Because this changes the graph used to calculate automorphisms, the results sometimes nominally differ from the previous version - especially in the case of canonical labelling, where unrecognisably different results may appear. Generators also often appear in different orders.
The performance improvements are most noticeable on large, quite dense digraphs. On random digraphs with 5000 vertices and 0.5 edge probability, 200-400x speedups were common. When calculating the automorphism group of the complete digraph on 1000 vertices, with vertex
i having colour
i mod 2 + 1, we obtain a 66x speedup. When the vertex
i is assigned colour
i mod 7 + 1, this becomes a 400x speedup.
Minor changes include:
DigraphReverse[Wilf A. Wilson]
DigraphMaximalCliques[Wilf A. Wilson]
AdjacencyMatrixMutableCopy[James D. Mitchell]
This release contains some bugfixes, as well as new and changed functionality. Digraphs now requires the Orb package, version 4.7.5 or higher.
IteratorFromDigraphFileare introduced. [James D. Mitchell]
ReadDigraphscan now take a file as a first argument. [James D. Mitchell]
DigraphPathis introduced to find a path between two vertices in a digraph. [Wilf A. Wilson]
IteratorOfPathsis introduced to iterate over the paths between two vertices in a digraph. [Wilf A. Wilson]
IsCompleteBipartiteDigraphis introduced. [Wilf A. Wilson]
Several bugs related to clique finding have been resolved. [Wilf A. Wilson]
bz2were previously not (un)compressed when used with
WriteDigraphs. [James D. Mitchell]
This is a minor release to fix a bug in
DigraphAllSimpleCircuits that failed to
return all simple circuits in some cases Issue 13. Some documentation was also updated.
This is a very minor release to change the version of GAP required.
This is a major release, primarily aimed at incorporating more of the functionality of Grape into Digraphs, as well as fixing some bugs. In this version, we welcomed Jan De Beule to the development team.
WriteDigraphsnow have a new output format
.pickle, which allows known automorphisms to be stored with the digraph
Digraphmethod for a Grape graph
DigraphColoringfor a digraph
IsDigraphEdgefor a digraph and a list
This is another minor release due to some missing build files in the Version 0.3.1 archive.
This is a minor release due to some missing build files in the Version 0.3 archive.
This release contains a number of bugfixes and performance improvements.
DigraphAllSimpleCircuitsbased on the algorithm in this paper by Donald B. Johnson. [Stuart Burrell and Wilf A. Wilson]
DigraphBicomponents. [Isabella Scott and Wilf A. Wilson]
DigraphCanonicalLabellingcan now be used with color classes that are preserved by the permutations acting on a digraph. [James D. Mitchell]
TCodeDecoderwas made more efficient. [James D. Mitchell]
AsTransformationis introduced for digraphs in
IsFunctionalDigraph. [James D. Mitchell]
The first release.
Pre-release version that was not made publicly available.