commit | 6b9956d7e76032ff09c7c6a0592de4791ce02ed5 | [log] [tgz] |
---|---|---|
author | Dan Kortschak <dan@kortschak.io> | Fri May 14 18:25:50 2021 +0930 |
committer | Dan Kortschak <dan@kortschak.io> | Wed Aug 11 13:11:27 2021 +0930 |
tree | 922d6d4c5f8de9b8e0b252c47c045266232107be | |
parent | baeadf22a64311945f73efe4679aa1aa4d1d68fd [diff] |
graph/coloring: allow warm start for DsaturExact There is an optimisation that is available for the Dsatur recursive search that takes advantage of the trivial observation that the colouring of a maximum clique in the graph must be consistent with the colouring of the graph and that a maximum clique will therefore constrain the colouring of the graph. This means that if the maximum clique is first trivially coloured the search can continue from there. However, if there are multiple co-equal maximum cliques it is possible for a clique to be chosen that will force the search down a pessimal search path, so we choose the clique to start from as the clique with the least constraining effect on the rest of the graph. The optimisation has the effect of excluding large sections of the search tree with a small amount of initial work to assess the maximum cliques. This change chooses the maximum clique with the lowest degree into the rest of the graph and assigns colours to all its nodes and progresses from there.
The core packages of the Gonum suite are written in pure Go with some assembly. Installation is done using go get
.
go get -u gonum.org/v1/gonum/...
Gonum supports and tests using the gc compiler on the two most recent Go releases on Linux (386, amd64 and arm64), macOS and Windows (both on amd64).
The Gonum modules are released on a six-month release schedule, aligned with the Go releases. i.e.: when Go-1.x
is released, Gonum-v0.n.0
is released around the same time. Six months after, Go-1.x+1
is released, and Gonum-v0.n+1.0
as well.
The release schedule, based on the current Go release schedule is thus:
Gonum-v0.n.0
: FebruaryGonum-v0.n+1.0
: AugustThe Gonum packages use a variety of build tags to set non-standard build conditions. Building Gonum applications will work without knowing how to use these tags, but they can be used during testing and to control the use of assembly and CGO code.
The current list of non-internal tags is as follows:
If you find any bugs, feel free to file an issue on the github issue tracker. Discussions on API changes, added features, code review, or similar requests are preferred on the gonum-dev Google Group.
https://groups.google.com/forum/#!forum/gonum-dev
Original code is licensed under the Gonum License found in the LICENSE file. Portions of the code are subject to the additional licenses found in THIRD_PARTY_LICENSES. All third party code is licensed either under a BSD or MIT license.
Code in graph/formats/dot is dual licensed Public Domain Dedication and Gonum License, and users are free to choose the license which suits their needs for this code.
The W3C test suites in graph/formats/rdf are distributed under both the W3C Test Suite License and the W3C 3-clause BSD License.