Copyright (C) 2014-18 by Jan De Beule, Julius Jonušas, James D. Mitchell, Michael Torpey, Wilf A. Wilson et al.
Licensing information can be found in the LICENSE file.
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 existsed [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.