Despite not showing a change in ragel -v output, the new version of
ragel (6.10-4 over 6.10-1 on my local machine) has a different output.
The differences appear to be incorrect in the new version, but will not
change the behaviour except for the reported lines in a panic or other
stack trace, so let's just go with what the new version has.
This is not intended to be a completed transition since it leaves the
libraries unusable to external client code, but rather as a step towards
use of math/rand/v2. This initial step allows repair of sequence change
failures without having to worry about API difference.
Add single-pair shortest path variant of Dijkstra. This variant can terminate
early when the target is reached, potentially make a large difference in
running time for Yen's k-shortest paths algorithm, as it makes many calls to
the shortest path subroutine.
The variant is also exposed for external use.
The From method incorrectly returned nil for the empty case and node neighbour
expansion did not mark visited nodes. Fix these and exercise the corrected path
in the test. Also clean up the code structure.
Previously the code did not ignore spur paths that had already been added into
the list of potential paths. This could cause the search to return duplicate
paths for certain graphs.
This adds an additional constraint onto YenKShortestPaths to consider
the paths' cost as well as the number of paths, enabling search within a
constrained distance.
The links have been redirecting to `pkg.go.dev` for a while now. In the
case of the main README, that made the badge a virtual duplicate of the
"go.dev reference" one.
The spanning tree walk sets nodes' IDs using the SetIDFromString method
so note that nodes returned by the destination's NewNode method must
satisfy StringIDSetter.
Previously the code was not removing nodes on the root of the search
path, resulting in searches that could re-enter previously searched
nodes. In addition to this, the logic for making edges was incorrectly
marking both directions for digraphs and only one direction for
undirected graphs.
Finally, the range of nodes to include in the spur-node set was
off-by-one. This is now clarified by including the comment from the wiki
article since the pseudo-code is less clear than the English due to
choice of range indexing convention.
Tests run repeatedly do not reinitialise state, meaning that a second run
of the tests will have leftover state from the previous run. This ensures
that repeated runs are identical with the exception of map iteration order.
Changes made in dsp/fourier/internal/fftpack break the formatting used
there, so these are reverted. There will be complaints in CI.
[git-generate]
gofmt -w .
go generate gonum.org/v1/gonum/blas
go generate gonum.org/v1/gonum/blas/gonum
go generate gonum.org/v1/gonum/unit
go generate gonum.org/v1/gonum/unit/constant
go generate gonum.org/v1/gonum/graph/formats/dot
go generate gonum.org/v1/gonum/graph/formats/rdf
go generate gonum.org/v1/gonum/stat/card
git checkout -- dsp/fourier/internal/fftpack
These methods express queries that are currently able to be expressed
with a sequence of In, Out and And queries. However, the constructed
filter approach is potentially significantly more expensive and are
more complex to reason about. For example it is often possible to make
the following re-writes,
p.Out(cond).In(cond).And(p) => p.HasAllOut(cond')
and
p.In(cond).Out(cond).And(p) => p.HasAllIn(cond').
The expense comes when reaching out to a commonly connected node and then
coming back; the return traversal will generate a large set of fruitless
candidates that then need to be filtered via the conjunction. This saves
that fruitless effort.
Also don't fail, but do log. It would be nice if there were a testing
output option that always logged even without failure or -test.v, but
we have what we have.
It seems that it is sometimes possible for a bad search traversal to be chosen
resulting in very long run time. This causes the tests to crash due to the
test timeout, make the timeout softer and let other tests run when a long
failure happens.
This is a very simplified version of a Gremlin-like language. The
simplification is in part forced by Go, but also reduces the level
of hiding complexity that is present in Gremlin.
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 graphs were obtained from https://mat.tepper.cmu.edu/COLOR/instances.html
and converted to graph6 using the following code:
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
"gonum.org/v1/gonum/graph/encoding/graph6"
"gonum.org/v1/gonum/graph/simple"
)
func main() {
g := simple.NewUndirectedGraph()
sc := bufio.NewScanner(os.Stdin)
for sc.Scan() {
line := sc.Text()
if len(line) == 0 || line[0] != 'e' {
continue
}
f := strings.Fields(line)
g.SetEdge(simple.Edge{F: node(f[1]), T: node(f[2])})
}
fmt.Printf("%q\n", graph6.Encode(g))
}
func node(s string) simple.Node {
i, err := strconv.Atoi(s)
if err != nil {
panic(err)
}
return simple.Node(i)
}
To convert graphs (ASCII col format only), use `go run main.go < <input>.col'.
