1.1.0

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.

• Issue #279: 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 Finn Smith.

• Issue #284: The function 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 PR #286.

• 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 DigraphsRespectsColouring.

• 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 of HomomorphismDigraphsFinder has been improved (particularly in cases where many homomorphisms between distinct small digraphs are found). This was done by James D. Mitchell in PR #282.

• Some further minor performance improvements were made, and a compiler warning was fixed.

1.0.3

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.

1.0.2

This is a minor release that fixes several bugs:

• GeneratorsOfEndomorphismMonoid sometimes incorrectly stored its result. This was reported by Chris Jefferson in Issue #251 and fixed by James D. Mitchell in PR #265.
• Some warnings that occurred when compiling against GAP 4.9 were removed. The warnings were reported by James D. Mitchell in Issue #266 and fixed by Wilf A. Wilson in PR #274.
• There was a bug with the ViewString of 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.

1.0.1

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.

1.0.0

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

• Perhaps the most immediately visible change is that the ViewString for 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.
• The behaviour of QuotientDigraph has been changed so that it no longer returns digraphs with multiple edges.
• IsEulerianDigraph would previously return true for digraphs that are Eulerian when their isolated vertices were removed, which contradicted the documentation. IsEulerianDigraph now returns false for all digraphs that are not strongly connected.
• The type of all digraphs has been renamed from DigraphType to DigraphByOutNeighboursType.
• The synonym DigraphColoring (American-style spelling) for DigraphColouring was removed.

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:

• AsSemigroup can produce strong semilattices of groups (i.e. Clifford) from semilattice digraphs, groups, and homomorphisms. This functionality was added by Finn Smith in PR #161.
• AutomorphismGroup and BlissAutomorphismGroup can 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.
• DegreeMatrix, LaplacianMatrix, and NrSpanningTrees were introduced by Reinis Cirpons in PR #224.
• DigraphCartesianProduct and DigraphDirectProduct, along with the companion functions DigraphCartesianProductProjections and DigraphDirectProductProjections, were introduced by Reinis Cirpons in PR #228.
• DigraphMycielskian was added by Murray Whyte in PR #194.
• DigraphNrStronglyConnectedComponents was added by Murray Whyte in PR #180.
• DigraphOddGirth was added by Murray Whyte in PR #166
• DigraphCore and IsDigraphCore were added by Murray Whyte in PRs #221 and #217, respectively.
• DotHighlightedDigraph was added by Finn Smith in PR #169.
• IsCompleteMultipartiteDigraph was added by Wilf A. Wilson in PR #236.
• IsEquivalenceDigraph was added by Wilf A. Wilson in PR #234 as a synonym for IsReflexiveDigraph and IsSymmetricDigraph and IsTransitiveDigraph.
• IsVertexTransitive and IsEdgeTransitive were added by Graham Campbell in PR #165.
• PetersenGraph and GeneralisedPetersenGraph were added by Murray Whyte in PRs #181 and #204, respectively.
• RandomLattice was added by Reinis Cirpons in PR #175.

New technical functionality

• The ability to compile (with the flag --with-external-bliss) and use the Digraphs package with the system version of bliss was added by Isuru Fernando in PR #225.
• The ability to compile (with the flag --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.

0.15.4

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.

0.15.3

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.

0.15.2

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.

0.15.1

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.

0.15.0

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:

• A copy of the Edge Addition Planarity Suite is now included in Digraphs, and so it is now possible to test digraphs for planarity, and to perform related computations. This was added by James D. Mitchell in PR #156. The new functionality can be accessed via:
  • Is(Outer)PlanarDigraph,
  • (Outer)PlanarEmbedding,
  • Kuratowski(Outer)PlanarSubdigraph,
  • SubdigraphHomeomorphicToK(23/4/33), and
  • MaximalAntiSymmetricSubdigraph.
• The functionality and performance for computing homomorphisms of digraphs was significantly improved by James D. Mitchell in PR #160. This PR also introduced the operations EmbeddingsDigraphs and EmbeddingsDigraphsRepresentatives.
• The one-argument attribute DigraphColouring was 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 DigraphGreedyColouring can 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.
• DigraphShortestPath was introduced by Murray Whyte in PR #148.
• IsAntiSymmetricDigraph (with a capital S) was added as a synonym for IsAntisymmetricDigraph.
• RandomDigraph now allows a float as its second argument; by James D. Mitchell in PR #159.
• The attribute CharacteristcPolynomial for a digraph was added by Luke Elliott in PR #164.
• The properties IsVertexTransitive and IsEdgeTransitive for digraphs were added by Graham Campbell in PR #165.