1# CHANGELOG – Digraphs package for GAP 2Copyright © 2014-20 by Jan De Beule, Julius Jonušas, James D. Mitchell, Michael 3Torpey, Wilf A. Wilson et al. 4 5Licensing information can be found in the `LICENSE` file. 6 7## Version 1.1.1 (released 29/01/2020) 8 9This release fixes a bug in `HomomorphismDigraphsFinder` that was introduced 10in version 1.1.0. The bug was found and fixed by [James D. Mitchell][]; 11see [PR #290](https://github.com/gap-packages/Digraphs/pull/290). 12 13## Version 1.1.0 (released 25/01/2020) 14 15This is a minor release that includes some new features and some performance 16improvements. 17 18The following issues were resolved, pull requests merged, or new features added: 19 20* [Issue #40](https://github.com/gap-packages/Digraphs/issues/40): If [bliss][] 21 is used to compute the automorphism group of a digraph, then the size of the 22 automorphism group is returned from [bliss][] to GAP, and the group object in 23 GAP immediately knows its size. In particular, it is not necessary to 24 recalculate this size. This was reported and fixed in 25 [PR #278](https://github.com/gap-packages/Digraphs/pull/278) by 26 [Chris Jefferson][]. 27 28* [Issue #279](https://github.com/gap-packages/Digraphs/issues/279): 29 In the function `HomomorphismDigraphsFinder`, it is now possible to specify a 30 subgroup of the automorphism group of the range digraph. This way, the 31 automorphism group of the range digraph is not computed by 32 `HomomorphismDigraphsFinder`. This can result in a performance improvement 33 in some cases. This was reported and fixed in 34 [PR #285](https://github.com/gap-packages/Digraphs/pull/285) by 35 Finn Smith. 36 37* [Issue #284](https://github.com/gap-packages/Digraphs/issues/284): 38 The function `HomomorphismDigraphsFinder` sometimes did not return any 39 homomorphisms when the source digraph had exactly one vertex. This was caused 40 by the data structures used by `HomomorphismDigraphsFinder` not being 41 correctly initialised in this case. This issue was reported by Finn Smith 42 and fixed by [James D. Mitchell][] in 43 [PR #286](https://github.com/gap-packages/Digraphs/pull/286). 44 45* In [PR #283](https://github.com/gap-packages/Digraphs/pull/283), Finn Smith 46 added the new operation `DigraphsRespectsColouring`, which can be used to 47 check whether a transformation or permutation between digraphs respects given 48 colourings. New versions of `IsDigraphHomomorphism`, and friends, were added 49 that accept colourings as arguments and which use 50 `DigraphsRespectsColouring`. 51 52* The version of [bliss][] included in Digraphs was updated to allow all of its 53 data structures to be modified in-place rather than allocated and deallocated 54 repeatedly. The function `HomomorphismDigraphsFinder` was modified to make 55 use of this new functionality in [bliss][], and subsequently the performance 56 of `HomomorphismDigraphsFinder` has been improved (particularly in cases 57 where many homomorphisms between distinct small digraphs are found). This 58 was done by [James D. Mitchell][] in 59 [PR #282](https://github.com/gap-packages/Digraphs/pull/282). 60 61* Some further minor performance improvements were made, and a compiler warning 62 was fixed. 63 64## Version 1.0.3 (released 29/11/2019) 65 66This is a minor release that fixes some bugs related to mutability in 67`DigraphDisjointUnion` and `ViewString`. 68 69These problems were reported and fixed by [Wilf A. Wilson][] in 70[Issue #276](https://github.com/gap-packages/Digraphs/issues/276) and 71[PR #277](https://github.com/gap-packages/Digraphs/pull/277), respectively. 72 73## Version 1.0.2 (released 28/11/2019) 74 75This is a minor release that fixes several bugs: 76 77* `GeneratorsOfEndomorphismMonoid` sometimes incorrectly stored its result. 78 This was reported by [Chris Jefferson][] in 79 [Issue #251](https://github.com/gap-packages/Digraphs/issues/251) 80 and fixed by [James D. Mitchell][] in 81 [PR #265](https://github.com/gap-packages/Digraphs/pull/265). 82* Some warnings that occurred when compiling against GAP 4.9 were removed. 83 The warnings were reported by [James D. Mitchell][] in 84 [Issue #266](https://github.com/gap-packages/Digraphs/issues/266) 85 and fixed by [Wilf A. Wilson][] in 86 [PR #274](https://github.com/gap-packages/Digraphs/pull/274). 87* There was a bug with the `ViewString` of known non-complete digraphs, 88 where such digraphs were described as being complete. 89 This was reported by Murray Whyte in 90 [Issue #272](https://github.com/gap-packages/Digraphs/issues/272) 91 and fixed by [Wilf A. Wilson][] in 92 [PR #273](https://github.com/gap-packages/Digraphs/pull/273). 93 94 95## Version 1.0.1 (released 05/10/2019) 96 97This is a minor release of the Digraphs package. The main change in this 98release is the reintroduction of the three-argument version of 99`DigraphAddVertices`, which accepts a digraph, a number of vertices to add, and 100a list of labels for the new vertices. The removal inadvertantly broke 101backwards compatbility with some third-party pre-existing code that relied on 102this functionality in the Digraphs package (see 103[Issue #264](https://github.com/gap-packages/Digraphs/issues/264)). 104 105The second argument of the three-argument version was redundant, and so a new 106two-argument version of `DigraphAddVertices`, which accepts a digraph and a list 107of new vertex labels, was introduced in v1.0.0. Unfortunately, the concurrent 108removal of the three-argument version of `DigraphAddVertices` was not advertised 109in the `CHANGELOG`. Although the three-argument version has been reintroduced, 110it will remain undocumented, since there is no good reason for any new code to 111use the three-argument version. 112 113The author contact data on the title page of the manual was also updated. 114 115The changes in this version were made by [Wilf A. Wilson][]. 116 117 118## Version 1.0.0 (released 03/10/2019) 119 120This is a major release of the Digraphs package that introduces significant new 121functionality, some changes in behaviour, general improvements, and several 122small bugfixes. With this version, we welcome Reinis Cirpons as a contributor 123to the package. 124 125### Changed functionality or names 126 127* Perhaps the most immediately visible change is that the `ViewString` for 128 immutable digraphs attempts to show more of the known information about the 129 digraph. This will break tests that relied on the previous behaviour, that 130 contained only the numbers of vertices and edges. 131* The behaviour of `QuotientDigraph` has been changed so that it no longer 132 returns digraphs with multiple edges. 133* `IsEulerianDigraph` would previously return `true` for digraphs 134 that are Eulerian when their isolated vertices were removed, which 135 contradicted the documentation. `IsEulerianDigraph` now returns `false` for 136 _all_ digraphs that are not strongly connected. 137* The type of all digraphs has been renamed from `DigraphType` to 138 `DigraphByOutNeighboursType`. 139* The synonym `DigraphColoring` (American-style spelling) for `DigraphColouring` 140 was removed. 141 142### Immutable and mutable digraphs 143 144Previously, every digraph in the Digraphs package was an immutable, 145attribute-storing digraph. It is now possible to create mutable digraphs. 146Mutable digraphs are not attribute-storing, but they can be altered in place - 147by adding or removing vertices and edges - which, unlike with 148immutable digraphs, does not require a new copy of the digraph to be made. 149This can save time and memory. 150 151This is particularly useful when one wants to create a digraph, alter the 152digraph in some way, and then perform some computations. One can now typically 153do this with fewer resources by creating a mutable digraph, modifying it in 154place, and then converting it into an immutable digraph (which can store 155attributes and properties), before finally performing the computations. 156 157Every digraph now belongs to precisely one of the categories `IsMutableDigraph` 158or `IsImmutableDigraph`, according to its mutability. A mutable digraph can be 159converted in-place into an immutable digraph with `MakeImmutable`. The are 160various new and updated functions for creating mutable and immutable digraphs, 161and for making mutable or immutable copies. 162 163Most digraph-creation functions in the package now accept an optional first 164argument, that can be either `IsMutableDigraph` or `IsImmutableDigraph`. Given 165one of these filters, the function will according create the digraph to be of 166the appropriate mutability. When this is option available, the default is 167always to create an immutable digraph. 168 169On the whole, for a function in the package that takes a digraph as its argument 170and again returns a digraph, the function now returns a digraph of the same 171mutability as its result, and moreover, given a mutable argument, it converts 172the mutable digraph in-place into the result. However, please consult the 173document to learn the exact behaviour of any specific function. 174 175Old attributes `Foo` in the package that take and return a single digraph have 176been converted into the operation `Foo`, with a corresponding new attribute, 177`FooAttr`. This means that the getter and setter functions, `HasFoo` and 178`SetFoo`, are renamed to `HasFooAttr` and `SetFooAttr`. See `DigraphReverse` 179for an example. For an immutable (and therefore attribute-storing) digraph, 180calling `Foo` calls `FooAttr` and returns an immutable digraph, which it 181stores, and so the effect is as before. For an mutable digraph, calling `Foo` 182modifies the digraph in-place, which remains mutable. 183 184The majority of the changes in Digraphs relating to mutable and immutable 185digraphs were made by [James D. Mitchell][], Finn Smith, and 186[Wilf A. Wilson][], with some further contributions by Reinis 187Cirpons, Luke Elliott, and Murray Whyte. 188 189### New and extended functions 190 191The package now includes the following new functions: 192 193* `AsSemigroup` can produce strong semilattices of groups (i.e. Clifford) 194 from semilattice digraphs, groups, and homomorphisms. This functionality was 195 added by Finn Smith in 196 [PR #161](https://github.com/gap-packages/Digraphs/pull/161). 197* `AutomorphismGroup` and `BlissAutomorphismGroup` can now take an optional third 198 argument that specifies an edge colouring for the digraph. In this case, the 199 functions return only automorphisms of the digraph that preserve the edge 200 colouring (and the vertex colouring, if one is given). This brilliant new 201 functionality was added by Finn Smith in 202 [PR #186](https://github.com/gap-packages/Digraphs/pull/186). 203* `DegreeMatrix`, `LaplacianMatrix`, and `NrSpanningTrees` were introduced by 204 Reinis Cirpons in 205 [PR #224](https://github.com/gap-packages/Digraphs/pull/224). 206* `DigraphCartesianProduct` and `DigraphDirectProduct`, along with the 207 companion functions `DigraphCartesianProductProjections` and 208 `DigraphDirectProductProjections`, were introduced by Reinis Cirpons in 209 [PR #228](https://github.com/gap-packages/Digraphs/pull/228). 210* `DigraphMycielskian` was added by Murray Whyte in 211 [PR #194](https://github.com/gap-packages/Digraphs/pull/194). 212* `DigraphNrStronglyConnectedComponents` was added by Murray Whyte in 213 [PR #180](https://github.com/gap-packages/Digraphs/pull/180). 214* `DigraphOddGirth` was added by Murray Whyte in 215 [PR #166](https://github.com/gap-packages/Digraphs/pull/166) 216* `DigraphCore` and `IsDigraphCore` were added by Murray Whyte in PRs 217 [#221](https://github.com/gap-packages/Digraphs/pull/221) and 218 [#217](https://github.com/gap-packages/Digraphs/pull/217), respectively. 219* `DotHighlightedDigraph` was added by Finn Smith in 220 [PR #169](https://github.com/gap-packages/Digraphs/pull/169). 221* `IsCompleteMultipartiteDigraph` was added by [Wilf A. Wilson][] 222 in [PR #236](https://github.com/gap-packages/Digraphs/pull/236). 223* `IsEquivalenceDigraph` was added by [Wilf A. Wilson][] in 224 [PR #234](https://github.com/gap-packages/Digraphs/pull/234) as a synonym for 225 `IsReflexiveDigraph and IsSymmetricDigraph and IsTransitiveDigraph`. 226* `IsVertexTransitive` and `IsEdgeTransitive` were added by Graham Campbell 227 in [PR #165](https://github.com/gap-packages/Digraphs/pull/165). 228* `PetersenGraph` and `GeneralisedPetersenGraph` 229 were added by Murray Whyte in PRs 230 [#181](https://github.com/gap-packages/Digraphs/pull/181) and 231 [#204](https://github.com/gap-packages/Digraphs/pull/204), 232 respectively. 233* `RandomLattice` was added by Reinis Cirpons in 234 [PR #175](https://github.com/gap-packages/Digraphs/pull/175). 235 236### New technical functionality 237 238* The ability to compile (with the flag `--with-external-bliss`) and use the 239 Digraphs package with the system version of `bliss` was added 240 by Isuru Fernando in 241 [PR #225](https://github.com/gap-packages/Digraphs/pull/225). 242* The ability to compile (with the flag `--with-external-planarity`) and use 243 the Digraphs package with the system version of the Edge Addition Planarity 244 Suite was added by [James D. Mitchell][] in 245 [PR #207](https://github.com/gap-packages/Digraphs/pull/207). 246 247 248## Version 0.15.4 (released 06/08/2019) 249 250This is a minor release that fixes a few bugs. 251 252In previous versions, the homomorphism-finding tools sometimes returned 253purported ‘monomoprhisms’ that were not injective. This problem was reported by 254Gordon Royle, see 255[Issue #222](https://github.com/gap-packages/Digraphs/issues/222), 256and fixed by [James D. Mitchell][] in 257[PR #223](https://github.com/gap-packages/Digraphs/pull/223). 258In addition, [Wilf A. Wilson][] 259[fixed a bug](https://github.com/gap-packages/Digraphs/commit/458a10298b08881bf7ee9207534ce431378d2c4e) 260in `DigraphNrEdges`. This function could previously lead to a crash when given a 261digraph whose `OutNeighbours` contained entries not in `IsPlistRep`. 262 263## Version 0.15.3 (released 12/06/2019) 264 265This is a minor release that fixes a typo in the documentation of 266`JohnsonDigraph`, and contains some minor tweaks for compatibility with 267future versions of GAP. 268 269## Version 0.15.2 (released 17/04/2019) 270 271This is a minor release that updates Digraphs for compatibility with the 272upcoming GAP 4.11, and resolves a bug in `IsHamiltonianDigraph` that could have 273lead to the boolean adjacency matrix of a digraph being accidentally modified; 274see [Issue #191](https://github.com/gap-packages/Digraphs/issues/191) and 275[PR #192](https://github.com/gap-packages/Digraphs/pull/192). 276 277## Version 0.15.1 (released 26/03/2019) 278 279This is a minor release of the Digraphs package, which improves the 280compatibility of Digraphs with cygwin. In particular, in the Windows installer 281of the next release of GAP, Digraphs should be included in a pre-compiled and 282working state. See 283[Issue #177](https://github.com/gap-packages/Digraphs/issues/177) and 284[PR #178](https://github.com/gap-packages/Digraphs/pull/178) for more details. 285 286Digraphs now requires version 4.8.2 of the [orb 287package](https://gap-packages.github.io/orb), or newer. 288 289 290## Version 0.15.0 (released 15/02/2019) 291 292This release contains several substantial new features, and some changes to 293previous functionality. 294 295The most significant change in behaviour is related to the Digraph6 format used 296in previous versions of the Digraphs package. This method of encoding directed 297graphs was developed independently from, but concurrently with, the 298[Digraph6 format introduced by 299nauty](https://users.cecs.anu.edu.au/~bdm/data/formats.txt); see 300[Issue #158](https://github.com/gap-packages/Digraphs/issues/158) for more 301information. The Digraphs package now uses the nauty format, although digraphs 302encoded using the old format can still be read in. This incompatibility was 303reported by 304[Jukka Kohonen](https://tuhat.helsinki.fi/portal/en/persons/jukka-kohonen(a6f3f037-4918-4bf5-a114-ac417f94beb5).html), and the changes were made by 305[Michael Torpey][] in 306[PR #162](https://github.com/gap-packages/Digraphs/pull/162). 307 308Other additions and changes are listed below: 309 310* A copy of the [Edge Addition Planarity 311 Suite](https://github.com/graph-algorithms/edge-addition-planarity-suite) 312 is now included in Digraphs, and so it is now possible to test digraphs for 313 planarity, and to perform related computations. This was added by [James D. 314 Mitchell](http://goo.gl/ZtViV6) in [PR 315 #156](https://github.com/gap-packages/Digraphs/pull/156). The new 316 functionality can be accessed via: 317 * `Is(Outer)PlanarDigraph`, 318 * `(Outer)PlanarEmbedding`, 319 * `Kuratowski(Outer)PlanarSubdigraph`, 320 * `SubdigraphHomeomorphicToK(23/4/33)`, and 321 * `MaximalAntiSymmetricSubdigraph`. 322* The functionality and performance for computing homomorphisms of digraphs was 323 significantly improved by [James D. Mitchell][] in [PR 324 #160](https://github.com/gap-packages/Digraphs/pull/160). This PR also 325 introduced the operations `EmbeddingsDigraphs` and 326 `EmbeddingsDigraphsRepresentatives`. 327* The one-argument attribute `DigraphColouring` was renamed to 328 `DigraphGreedyColouring`, and its performance was improved; it now uses 329 the Welsh-Powell algorithm, which can be accessed directly via 330 `DigraphWelshPowellOrder`. The behaviour of `DigraphGreedyColouring` can be 331 modified by including an optional second argument; see the 332 documentation for more information. This work was done by [James D. 333 Mitchell](http://goo.gl/ZtViV6) in [PR 334 #144](https://github.com/gap-packages/Digraphs/pull/144). 335* `DigraphShortestPath` was introduced by Murray Whyte in [PR 336 #148](https://github.com/gap-packages/Digraphs/pull/148). 337* `IsAntiSymmetricDigraph` (with a capital S) was added as a synonym for 338 `IsAntisymmetricDigraph`. 339* `RandomDigraph` now allows a float as its second argument; by [James D. 340 Mitchell](http://goo.gl/ZtViV6) in [PR 341 #159](https://github.com/gap-packages/Digraphs/pull/159). 342* The attribute `CharacteristcPolynomial` for a digraph was added by Luke 343 Elliott in [PR #164](https://github.com/gap-packages/Digraphs/pull/164). 344* The properties `IsVertexTransitive` and `IsEdgeTransitive` for digraphs 345 were added by Graham Campbell in 346 [PR #165](https://github.com/gap-packages/Digraphs/pull/165). 347 348## Version 0.14.0 (released 23/11/2018) 349 350This release contains bugfixes and a couple of new features. 351 352* The operations `AsSemigroup` and `AsMonoid` for lattice and semilattice 353 digraphs were added by Chris Russell in [PR 354 #136](https://github.com/gap-packages/Digraphs/pull/136). 355* The operation `IsDigraphColouring` was added by [James D. 356 Mitchell](http://goo.gl/ZtViV6) in [PR 357 #145](https://github.com/gap-packages/Digraphs/pull/145). 358* In previous versions of the package, the output of `ArticulationPoints` would 359 sometimes contain repeated vertices (reported by Luke Elliott in [Issue 360 #140](https://github.com/gap-packages/Digraphs/issues/140), and fixed by 361 [James D. Mitchell][] in [PR 362 #142](https://github.com/gap-packages/Digraphs/pull/142)). 363* In previous versions of the package, an unexpected error was sometimes caused 364 when removing an immutable set of vertices from a digraph (reported and fixed 365 by [James D. Mitchell][] in [PR 366 #146](https://github.com/gap-packages/Digraphs/pull/146)). 367* The header file `x86intrin.h` was unnecessarily being included by the kernel 368 module of Digraphs (reported by [Wilf A. Wilson][] in [Issue 369 #147](https://github.com/gap-packages/Digraphs/issues/147), and fixed by 370 [James D. Mitchell][] in [PR 371 #152](https://github.com/gap-packages/Digraphs/pull/152)). 372 373[Max Horn](https://www.quendi.de/math) also contributed various compatibility 374and correctness changes to the kernel module of the package, including in PRs 375[#149](https://github.com/gap-packages/Digraphs/pull/149), 376[#150](https://github.com/gap-packages/Digraphs/pull/150), and 377[#151](https://github.com/gap-packages/Digraphs/pull/151). 378 379Digraphs now requires version 4.8.1 of the [orb 380package](https://gap-packages.github.io/orb), or newer. 381 382## Version 0.13.0 (released 19/09/2018) 383 384This release of Digraphs contains some bugfixes, along with the following new features: 385 386* The GraphViz engine used by `Splash` is now configurable, thanks to [Markus Pfeiffer](https://www.morphism.de/~markusp). 387* The properties `IsPartialOrderDigraph`, `IsPreorderDigraph`, and `IsQuasiorderDigraph` were introduced by Chris Russell, along with the following functions for visualising these kinds of digraphs: 388 * `DotPartialOrderDigraph` 389 * `DotPreorderDigraph` 390 * `DotQuasiorderDigraph` 391* The following functions for transformations and permutations were added by [James D. Mitchell][]: 392 * `IsDigraphHomomorphism` 393 * `IsDigraphEpimorphism` 394 * `IsDigraphMonomorphism` 395 * `IsDigraphEndomorphism` 396 * `IsDigraphEmbedding` 397 * `IsDigraphIsomorphism` 398 399Digraphs now requires version 4.9.0 of GAP, or newer. 400 401## Version 0.12.2 (released 24/08/2018) 402 403This is a minor release which contains some small adjustments to the build 404system of the package. 405 406## Version 0.12.1 (released 26/04/2018) 407 408This is a minor release, which contains several bugfixes. The following problems 409were resolved by [James D. Mitchell][]: 410 411* `HomomorphismDigraphFinder` sometimes failed to find a homomorphism when one existed [[Issue #111](https://github.com/gap-packages/Digraphs/issues/111), reported by Gordon Royle]; 412* the documentation for `HomomorphismDigraphFinder` was 413 incomplete [[Issue #112](https://github.com/gap-packages/Digraphs/issues/112)]; and 414* a segmentation fault could be caused when using Digraphs with 415 NautyTracesInterface, in certain cases [[Issue #114](https://github.com/gap-packages/Digraphs/issues/114)]. 416 417## Version 0.12.0 (released 31/01/2018) 418 419This release contains bugfixes and new features. In particular, it: 420 421* fixes [a bug in `ArticulationPoints` and `IsBiconnectedDigraph`](https://github.com/gap-packages/Digraphs/issues/102) [[Wilf A. Wilson][]]; 422* adds the property `IsChainDigraph` [Ashley Clayton]; and 423* adds the operation `IsDigraphAutomorphism` [Chris Russell]. 424 425Digraphs now requires version 4.5.1 of the IO package. 426 427## Version 0.11.0 (released 22/11/2017) 428 429The principal change in Digraphs version 0.11.0 is the addition of 430support for computing automorphisms, canonical labellings, and isomorphisms of 431digraphs with [nauty](http://pallini.di.uniroma1.it/). This 432functionality requires the [NautyTracesInterface 433package](https://github.com/sebasguts/NautyTracesInterface) for GAP, version 0.2 434or newer. However, this is not a required package, and the default engine 435remains [bliss](http://www.tcs.hut.fi/Software/bliss/). It is possible to 436specify the engine that is used by Digraphs. These changes to Digraphs were made 437by [James D. Mitchell][]]. 438 439In particular, version 0.11.0 includes the following changes: 440 441* `BlissAutomorphismGroup` and `NautyAutomorphismGroup` are introduced. 442* `DigraphCanonicalLabelling` is replaced by `BlissCanonicalLabelling` and 443 `NautyCanonicalLabelling`. 444* `BlissCanonicalDigraph` and `NautyCanonicalDigraph` are introduced [Chris 445 Russell and [James D. Mitchell][]]. 446* `DigraphsUseNauty` and `DigraphsUseBliss` are introduced. 447 448The property `IsHamiltonianDigraph` and the attribute `HamiltonianPath` were 449added by Luke Elliott. Additionally, this release fixes several bugs, including 450one in `DigraphSymmetricClosure` and one in `CompleteDigraph`. 451 452Digraphs now requires version 4.4.6 of the IO package. 453 454## Version 0.10.1 (released 16/08/2017) 455This is a minor release, which contains performance improvements, and fixes a 456bug in `Digraph` that could cause a segmentation fault. 457 458## Version 0.10.0 (released 20/07/2017) 459This release contains new features, bugfixes, and minor improvements to the 460documentation. There is a new method for `ChromaticNumber`, which has better 461performance than the previous method 462[[Julius Jonusas][] 463and [James D. Mitchell][]]. 464A bug in the code for calculating homomorphisms of digraphs, which could cause 465a crash, was resolved [[James D. Mitchell][]]. 466 467### New Features in Version 0.10.0 468 469* Vertex labelled digraphs can now be visualised in a way that displays vertex 470labels, by using the new operation `DotVertexLabelledDigraph`. 471* The attribute `CliqueNumber` is introduced. 472* The following new attributes for Cayley digraphs are introduced: 473 * `GroupOfCayleyDigraph` 474 * `SemigroupOfCayleyDigraph` 475 * `GeneratorsOfCayleyDigraph` 476 477All of the new features were added by [James D. Mitchell][]. 478 479## Version 0.9.0 (released 12/07/2017) 480This release introduces several new features. 481 482### New Features in Version 0.9.0 483The following attributes and properties were added by 484[James D. Mitchell][]: 485 486* `ArticulationPoints` (and its synonym `CutVertices`) 487* `IsBiconnectedDigraph` 488* `IsCycleDigraph` 489 490The following operations related to matchings were added by Isabella Scott and 491[Wilf A. Wilson][]: 492 493* `IsMatching` 494* `IsPerfectMatching` 495* `IsMaximalMatching` 496 497## Version 0.8.1 (released 18/05/2017) 498This is a minor release, which updates the README file and updates the list of 499package authors and contributors. 500 501## Version 0.8.0 (released 17/05/2017) 502This release contains new features, several minor bugfixes, and minor 503improvements to the documentation of the package. 504 505### New Features in Version 0.8.0 506 507This release introduces the new operations `DigraphClosure` 508[[Julius Jonusas][]] 509and `BooleanAdjacencyMatrixMutableCopy` 510[[Wilf A. Wilson][]], 511along with the following properties and operations related to semilattices 512[Chris Russell]: 513 514* `IsPartialOrderDigraph` 515* `IsMeetSemilatticeDigraph` 516* `IsJoinSemilatticeDigraph` 517* `IsLatticeDigraph` 518* `PartialOrderDigraphMeetOfVertices` 519* `PartialOrderDigraphJoinOfVertices` 520 521## Version 0.7.1 (released 22/03/2017) 522This is a minor release, which fixes bugs in `DigraphTopologicalSort` and 523`IsAntisymmetricDigraph` that could trigger segmentation faults. 524 525## Version 0.7.0 (released 14/03/2017) 526This release introduces several new features, changes some existing 527functionality, and improves the documentation. The changes in this release were 528made by [Wilf A. Wilson][]. 529 530### New Features in Version 0.7.0 531* This release contains a new technique for encoding a vertex-coloured 532 *multidigraph* as a vertex-coloured (undirected) graph while preserving the 533 automorphism group, in order to calculate the automorphism group and canonical 534 labelling using bliss. This enables the following functionality: 535 * the operations `AutomorphismGroup` and `DigraphCanonicalLabelling` for a 536 digraph and a vertex-colouring now accept a multidigraph as their first 537 argument; 538 * the operations `IsIsomorphicDigraph` and `IsomorphismDigraphs` now accept 539 multidigraphs, and they also accept vertex-colourings as optional arguments. 540 541* This release add new functionality related to undirected spanning trees and 542 undirected spanning forests: 543 * the property `IsUndirectedForest` is introduced; 544 * the attributes `UndirectedSpanningTree` and `UndirectedSpanningForest` are 545 introduced; and 546 * the operations `IsUndirectedSpanningTree` and `IsUndirectedSpanningForest` 547 are introduced. 548 549### Altered Behaviour in Version 0.7.0 550* The behaviour of `IsSubdigraph` is changed in the case that it is given one or 551 two multidigraphs. 552* The one-argument version of the operation `DigraphColouring` (and its synonym, 553 `DigraphColoring`) is now an attribute. 554 555## Version 0.6.1 (released 01/03/2017) 556This is a minor release. This release fixes a bug in `AsDigraph` for a 557transformation and an integer. The operations `OutNeighboursCopy` and 558`OutNeighborsCopy` are renamed to `OutNeighboursMutableCopy` and 559`OutNeighborsMutableCopy`, respectively, and new operations 560`InNeighboursMutableCopy` and `InNeighborsMutableCopy` are introduced. 561 562## Version 0.6.0 (released 09/12/2016) 563This is a major release, adding a variety of new operations and attributes 564for Digraphs, as well as improving some functions and improving the 565package's documentation. In this version, we welcome Luke Elliott and 566Markus Pfeiffer as new authors. 567 568### New Features in Version 0.6.0 569* The ability to label the edges of digraphs is introduced. [[Markus Pfeiffer][]] 570* The operation `CompleteMultipartiteDigraph` is introduced. [Stuart Burrell and [Wilf A. Wilson][]] 571* The operations `ReadDIMACSDigraph` and `WriteDIMACSDigraph` are introduced. 572 [[Wilf A. Wilson][]] 573* The operation `ChromaticNumber` is introduced. [[James D. Mitchell][] and [Wilf A. Wilson][]] 574* The operations `IsDirectedTree` and `IsUndirectedTree` are introduced. [Luke Elliott] 575* The operation `IsEulerianDigraph`is introduced. [Luke Elliott] 576 577## Version 0.5.2 (released 20/06/2016) 578This is a minor release containing one bugfix and several other minor changes. 579Digraphs now works when it and GAP are compiled in 32 bit mode. 580 581## Version 0.5.1 (released 08/06/2016) 582This release contains some bugfixes, some minor new features, and some 583performance improvements. The package has moved to GitHub and we welcome Finn 584Smith as an author. 585 586This 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. 587 588The new reduction is based on two techniques in: 589 590> David Bremner, Mathieu Dutour Sikiric, Dmitrii V. Pasechnik, Thomas Rehn, Achill Schürmann. Computing symmetry groups of polyhedra. https://arxiv.org/abs/1210.0206v3 591 592Namely, "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. 593 594The 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`. 595Because 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. 596 597The 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. 598 599Minor changes include: 600 601* a better method for `DigraphReverse` [[Wilf A. Wilson][]] 602* automorphism groups of complete, empty, cycle, chain, and complete bipartite 603digraphs are set at creation [[Michael Torpey][]] 604* a minor improvement in performance in the `DigraphMaximalCliques` [[Wilf A. Wilson][]] 605* a new operation `AdjacencyMatrixMutableCopy` [[James D. Mitchell][]] 606 607## Version 0.5.0 (released 03/03/2016) 608This release contains some bugfixes, as well as new and changed functionality. 609Digraphs now requires the [Orb package](http://gap-packages.github.io/orb), 610version 4.7.5 or higher. 611 612### New Features in Version 0.5.0 613* `DigraphFile` and `IteratorFromDigraphFile` are introduced. [[James D. Mitchell][]] 614* `WriteDigraphs` and `ReadDigraphs` can now take a file as a first argument. [[James D. Mitchell][]] 615* The operation `DigraphPath` is introduced to find a path between two vertices 616 in a digraph. [[Wilf A. Wilson][]] 617* The operation `IteratorOfPaths` is introduced to iterate over the paths 618 between two vertices in a digraph. [[Wilf A. Wilson][]] 619* The property `IsCompleteBipartiteDigraph` is introduced. [[Wilf A. Wilson][]] 620 621### Issues Resolved in Version 0.5.0 622Several bugs related to clique finding have been resolved. [[Wilf A. Wilson][]] 623 624* Files with extension `bz2` were previously not (un)compressed when used with 625 `ReadDigraphs` and `WriteDigraphs`. [[James D. Mitchell][]] 626* The documentation in Chapter 8 "Finding cliques and independent sets" has been 627 corrected to accurately reflect the functionality of the package. 628* A bug which led to too few cliques and independent sets being found for some 629 digraphs has been resolved. 630* A bug which led to duplicate cliques and independent sets being found for some 631 digraphs has been resolved. 632 633## Version 0.4.2 (released 28/01/2016) 634This is a minor release to fix a bug in `DigraphAllSimpleCircuits` that failed to 635return all simple circuits in some cases [Issue 13](https://github.com/gap-packages/Digraphs/issues/13). Some documentation was also updated. 636 637## Version 0.4.1 (released 22/01/2016) 638This is a very minor release to change the version of GAP required. 639 640## Version 0.4.0 (released 19/01/2016) 641This is a major release, primarily aimed at incorporating more of the 642functionality of Grape into Digraphs, as well as fixing some bugs. In this 643version, we welcomed Jan De Beule to the development team. 644 645### New Features in Version 0.4.0 646* Functionality to calculate cliques and independent sets 647* New methods for the constructor function `Digraph` 648* `ReadDigraphs` and `WriteDigraphs` now have a new output format `.p` or 649 `.pickle`, which allows known automorphisms to be stored with the digraph 650* The following functions now use known automorphisms: 651 - `DigraphDiameter` 652 - `DigraphDual` 653 - `DigraphShortestDistances` 654 - `Digraph` method for a Grape graph 655 - `Graph` 656 - `InDegreeSequence` 657 - `OutDegreeSequence` 658* The following new functions were added: 659 - `BipartiteDoubleDigraph` 660 - `BooleanAdjacencyMatrix` 661 - `CayleyDigraph` 662 - `DigraphAddAllLoops` 663 - `DigraphAddEdgeOrbit` 664 - `DigraphAdjacencyFunction` 665 - `DigraphColoring` for a digraph 666 - `DigraphDegeneracyOrdering` 667 - `DigraphDegeneracy` 668 - `DigraphDistanceSet` 669 - `DigraphGirth` 670 - `DigraphGroup` 671 - `DigraphLayers` 672 - `DigraphLongestSimpleCircuit` 673 - `DigraphOrbitReps` 674 - `DigraphOrbits` 675 - `DigraphRemoveEdgeOrbit` 676 - `DigraphSchreierVector` 677 - `DigraphShortestDistance` 678 - `DigraphStabilizer` 679 - `DigraphUndirectedGirth` 680 - `DistanceDigraph` 681 - `DoubleDigraph` 682 - `EdgeOrbitsDigraph` 683 - `InDegreeSet` 684 - `IsDigraphEdge` for a digraph and a list 685 - `IsDistanceRegularDigraph` 686 - `IsInRegularDigraph` 687 - `IsOutRegularDigraph` 688 - `IsRegularDigraph` 689 - `JohnsonDigraph` 690 - `LineDigraph` 691 - `LineUndirectedDigraph` 692 - `MaximalSymmetricSubdigraphWithoutLoops` 693 - `MaximalSymmetricSubdigraph` 694 - `OutDegreeSet` 695 - `RepresentativeOutNeighbours` 696 697[[Jan De Beule][], [Julius Jonusas][], [James D. Mitchell][], 698 [Michael Torpey][], [Wilf A. Wilson][]] 699 700## Version 0.3.2 (released 14/01/2016) 701This is another minor release due to some missing build files in the Version 7020.3.1 archive. 703 704## Version 0.3.1 (released 13/01/2016) 705This is a minor release due to some missing build files in the Version 0.3 archive. 706 707## Version 0.3.0 (released 12/01/2016) 708This release contains a number of bugfixes and performance improvements. 709 710### New Features in Version 0.3.0 711* The attribute `DigraphAllSimpleCircuits` based 712on the algorithm in [this paper](http://epubs.siam.org/doi/abs/10.1137/0204007?journalCode=smjcat) by Donald B. Johnson. [Stuart Burrell and [Wilf A. Wilson][]] 713* Improve efficiency of the algorithm for coloring a graph with 2 colours, a method for `IsBipartiteDigraph` and `DigraphBicomponents`. [Isabella Scott and [Wilf A. Wilson][]] 714* `AutomorphismGroup` and `DigraphCanonicalLabelling` can now be used with color classes that are preserved by the permutations acting on a digraph. [[James D. Mitchell][]] 715* The `TCodeDecoder` was made more efficient. [[James D. Mitchell][]] 716* `AsTransformation` is introduced for digraphs in `IsFunctionalDigraph`. [[James D. Mitchell][]] 717* The tests and their code coverage were improved. 718 719### Issues Resolved in Version 0.3.0 720* There was a memory leak in bliss-0.73, which is fixed in the copy of bliss included with Digraphs, but not in the official release of bliss. [[James D. Mitchell][]] 721* Some bits of code that caused compiler warnings were improved. [[James D. Mitchell][]] 722* Some memory leaks were resolved in the Digraphs kernel module. [[Michael Torpey][]] 723 724## Version 0.2.0 (released 04/09/2015) 725The first release. 726 727## Version 0.1.0 728Pre-release version that was not made publicly available. 729 730[James D. Mitchell]: http://goo.gl/ZtViV6 731[Wilf A. Wilson]: http://wilf.me 732[Michael Torpey]: https://mtorpey.github.io 733[Julius Jonusas]: http://julius.jonusas.work 734[Jan De Beule]: http://homepages.vub.ac.be/~jdbeule 735[Markus Pfeiffer]: https://www.morphism.de/~markusp 736[Chris Jefferson]: https://caj.host.cs.st-andrews.ac.uk 737[bliss]: http://www.tcs.hut.fi/Software/bliss/ 738