Digraphs

Graphs, digraphs, and multidigraphs in GAP

Version 1.0.3
Released 2019-11-29

This project is maintained by James Mitchell, Wilf Wilson

CHANGELOG – Digraphs package for GAP

Copyright © 2014-19 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.

Version 1.0.3 (released 29/11/2019)

This is a minor release that fixes some bugs related to mutability in DigraphDisjointUnion and ViewString.

These problems were reported and fixed by Wilf A. Wilson in Issue #276 and PR #277, respectively.

Version 1.0.2 (released 28/11/2019)

This is a minor release that fixes several bugs:

Version 1.0.1 (released 05/10/2019)

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 Issue #264).

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 in the 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.

Version 1.0.0 (released 03/10/2019)

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.

Changed functionality or names

Immutable and mutable digraphs

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 IsMutableDigraph or 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 IsMutableDigraph or IsImmutableDigraph. Given 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.

Old attributes 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, HasFoo and SetFoo, are renamed to HasFooAttr and SetFooAttr. See DigraphReverse for an example. For an immutable (and therefore attribute-storing) digraph, calling Foo calls FooAttr and returns an immutable digraph, which it stores, and so the effect is as before. For an mutable digraph, calling Foo 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.

New and extended functions

The package now includes the following new functions:

New technical functionality

Version 0.15.4 (released 06/08/2019)

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 Issue #222, and fixed by James D. Mitchell in PR #223. In addition, Wilf A. Wilson fixed a bug in DigraphNrEdges. This function could previously lead to a crash when given a digraph whose OutNeighbours contained entries not in IsPlistRep.

Version 0.15.3 (released 12/06/2019)

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.

Version 0.15.2 (released 17/04/2019)

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 PR #192.

Version 0.15.1 (released 26/03/2019)

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.

Version 0.15.0 (released 15/02/2019)

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:

Version 0.14.0 (released 23/11/2018)

This release contains bugfixes and a couple of new features.

Max Horn also contributed various compatibility and correctness changes to the kernel module of the package, including in PRs #149, #150, and #151.

Digraphs now requires version 4.8.1 of the orb package, or newer.

Version 0.13.0 (released 19/09/2018)

This release of Digraphs contains some bugfixes, along with the following new features:

Digraphs now requires version 4.9.0 of GAP, or newer.

Version 0.12.2 (released 24/08/2018)

This is a minor release which contains some small adjustments to the build system of the package.

Version 0.12.1 (released 26/04/2018)

This is a minor release, which contains several bugfixes. The following problems were resolved by James D. Mitchell:

Version 0.12.0 (released 31/01/2018)

This release contains bugfixes and new features. In particular, it:

Digraphs now requires version 4.5.1 of the IO package.

Version 0.11.0 (released 22/11/2017)

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:

The property IsHamiltonianDigraph and the attribute HamiltonianPath were added by Luke Elliott. Additionally, this release fixes several bugs, including one in DigraphSymmetricClosure and one in CompleteDigraph.

Digraphs now requires version 4.4.6 of the IO package.

Version 0.10.1 (released 16/08/2017)

This is a minor release, which contains performance improvements, and fixes a bug in Digraph that could cause a segmentation fault.

Version 0.10.0 (released 20/07/2017)

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 [Julius Jonusas and James D. Mitchell]. A bug in the code for calculating homomorphisms of digraphs, which could cause a crash, was resolved [James D. Mitchell].

New Features in Version 0.10.0

All of the new features were added by James D. Mitchell.

Version 0.9.0 (released 12/07/2017)

This release introduces several new features.

New Features in Version 0.9.0

The following attributes and properties were added by James D. Mitchell:

The following operations related to matchings were added by Isabella Scott and Wilf A. Wilson:

Version 0.8.1 (released 18/05/2017)

This is a minor release, which updates the README file and updates the list of package authors and contributors.

Version 0.8.0 (released 17/05/2017)

This release contains new features, several minor bugfixes, and minor improvements to the documentation of the package.

New Features in Version 0.8.0

This release introduces the new operations DigraphClosure [Julius Jonusas] and BooleanAdjacencyMatrixMutableCopy [Wilf A. Wilson], along with the following properties and operations related to semilattices [Chris Russell]:

Version 0.7.1 (released 22/03/2017)

This is a minor release, which fixes bugs in DigraphTopologicalSort and IsAntisymmetricDigraph that could trigger segmentation faults.

Version 0.7.0 (released 14/03/2017)

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.

New Features in Version 0.7.0

Altered Behaviour in Version 0.7.0

Version 0.6.1 (released 01/03/2017)

This is a minor release. This release fixes a bug in AsDigraph for a transformation and an integer. The operations OutNeighboursCopy and OutNeighborsCopy are renamed to OutNeighboursMutableCopy and OutNeighborsMutableCopy, respectively, and new operations InNeighboursMutableCopy and InNeighborsMutableCopy are introduced.

Version 0.6.0 (released 09/12/2016)

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.

New Features in Version 0.6.0

Version 0.5.2 (released 20/06/2016)

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.

Version 0.5.1 (released 08/06/2016)

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 V1, V2, V3 of the vertex set V. Colour V1 according to the colouring c of D, and V2, V3 with two distinct colours that do not occur in D. Connect each vertex in V1 to the corresponding vertices in V2, V3. For every arc (x,y) in E, put an edge between the copy of x in V2, and the copy of y in V3. Automorphisms of this graph, when restricted to V, are precisely the automorphisms of D. 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:

Version 0.5.0 (released 03/03/2016)

This release contains some bugfixes, as well as new and changed functionality. Digraphs now requires the Orb package, version 4.7.5 or higher.

New Features in Version 0.5.0

Issues Resolved in Version 0.5.0

Several bugs related to clique finding have been resolved. [Wilf A. Wilson]

Version 0.4.2 (released 28/01/2016)

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.

Version 0.4.1 (released 22/01/2016)

This is a very minor release to change the version of GAP required.

Version 0.4.0 (released 19/01/2016)

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.

New Features in Version 0.4.0

[Jan De Beule, Julius Jonusas, James D. Mitchell, Michael Torpey, Wilf A. Wilson]

Version 0.3.2 (released 14/01/2016)

This is another minor release due to some missing build files in the Version 0.3.1 archive.

Version 0.3.1 (released 13/01/2016)

This is a minor release due to some missing build files in the Version 0.3 archive.

Version 0.3.0 (released 12/01/2016)

This release contains a number of bugfixes and performance improvements.

New Features in Version 0.3.0

Issues Resolved in Version 0.3.0

Version 0.2.0 (released 04/09/2015)

The first release.

Version 0.1.0

Pre-release version that was not made publicly available.