g/a/toposort: add topological sorting pkg
This adds a package which implements topological sorting.
There are existing Go packages out there which do this, but all of
them have various shortcomings, either in the API or in
performance or stability.
This uses a fairly simple DFS-based algorithm for doing the majority
of the work. It uses generics for the nodes to allow for flexibility and
is covered by a fuzz test to check for correctness.
Change-Id: I4ae3f0b97ef801350b87cdae3a3d9a1ba63830e3
Reviewed-on: https://review.monogon.dev/c/monogon/+/1351
Tested-by: Jenkins CI
Reviewed-by: Serge Bazanski <serge@monogon.tech>
diff --git a/build/analysis/nogo_config.json b/build/analysis/nogo_config.json
index da28532..21afc4d 100644
--- a/build/analysis/nogo_config.json
+++ b/build/analysis/nogo_config.json
@@ -2,7 +2,8 @@
"composites": {
"exclude_files": {
"external/": "third_party",
- "metropolis/pkg/bootparam/": "gofuzz"
+ "metropolis/pkg/bootparam/": "gofuzz",
+ "go/algorithm/toposort/": "gofuzz"
}
},
"copylocks": {
diff --git a/go/algorithm/toposort/BUILD.bazel b/go/algorithm/toposort/BUILD.bazel
new file mode 100644
index 0000000..992a2f7
--- /dev/null
+++ b/go/algorithm/toposort/BUILD.bazel
@@ -0,0 +1,14 @@
+load("@io_bazel_rules_go//go:def.bzl", "go_library", "go_test")
+
+go_library(
+ name = "toposort",
+ srcs = ["toposort.go"],
+ importpath = "source.monogon.dev/go/algorithm/toposort",
+ visibility = ["//visibility:public"],
+)
+
+go_test(
+ name = "toposort_test",
+ srcs = ["toposort_test.go"],
+ embed = [":toposort"],
+)
diff --git a/go/algorithm/toposort/toposort.go b/go/algorithm/toposort/toposort.go
new file mode 100644
index 0000000..6164b91
--- /dev/null
+++ b/go/algorithm/toposort/toposort.go
@@ -0,0 +1,89 @@
+package toposort
+
+import "errors"
+
+type outEdges[Node comparable] map[Node]bool
+
+// Graph is a directed graph represented using an adjacency list.
+// Its nodes have type T. An empty Graph object is ready to use.
+type Graph[T comparable] struct {
+ nodes map[T]outEdges[T]
+}
+
+func (g *Graph[T]) ensureNodes() {
+ if g.nodes == nil {
+ g.nodes = make(map[T]outEdges[T])
+ }
+}
+
+// AddNode adds the node n to the graph if it does not already exist, in which
+// case it does nothing.
+func (g *Graph[T]) AddNode(n T) {
+ g.ensureNodes()
+ if _, ok := g.nodes[n]; !ok {
+ g.nodes[n] = make(outEdges[T])
+ }
+}
+
+// AddEdge adds the directed edge from the from node to the to node to the
+// graph if it does not already exist, in which case it does nothing.
+func (g *Graph[T]) AddEdge(from, to T) {
+ g.ensureNodes()
+ g.AddNode(from)
+ g.AddNode(to)
+ g.nodes[from][to] = true
+}
+
+var ErrCycle = errors.New("graph has at least one cycle")
+
+// TopologicalOrder sorts the nodes in the graph according to their topological
+// order (aka. dependency order) and returns a valid order. Note that this
+// implementation returns the reverse order of a "standard" topological order,
+// i.e. if edge A -> B exists, it returns B, A. This is more convenient for
+// solving dependency ordering problems, as a normal dependency graph will sort
+// according to execution order.
+// Further note that there can be multiple such orderings and any of them might
+// be returned. Even multiple invocations of TopologicalOrder can return
+// different orderings. If no such ordering exists (i.e. the graph contains at
+// least one cycle), an error is returned.
+func (g *Graph[T]) TopologicalOrder() ([]T, error) {
+ g.ensureNodes()
+ // Depth-first search-based implementation with O(|n| + |E|) complexity.
+ var solution []T
+ unmarkedNodes := make(map[T]bool)
+ for n := range g.nodes {
+ unmarkedNodes[n] = true
+ }
+
+ nodeVisitStack := make(map[T]bool)
+
+ var visit func(n T) error
+ visit = func(n T) error {
+ if !unmarkedNodes[n] {
+ return nil
+ }
+ // If we're revisiting a node already on the visit stack, we have a
+ // cycle.
+ if nodeVisitStack[n] {
+ return ErrCycle
+ }
+ nodeVisitStack[n] = true
+ // Visit every node m pointed to by an edge from the current node n.
+ for m := range g.nodes[n] {
+ if err := visit(m); err != nil {
+ return err
+ }
+ }
+ delete(nodeVisitStack, n)
+ delete(unmarkedNodes, n)
+ solution = append(solution, n)
+ return nil
+ }
+
+ for n := range unmarkedNodes {
+ if err := visit(n); err != nil {
+ return nil, err
+ }
+ }
+ return solution, nil
+}
diff --git a/go/algorithm/toposort/toposort_test.go b/go/algorithm/toposort/toposort_test.go
new file mode 100644
index 0000000..d2ec65a
--- /dev/null
+++ b/go/algorithm/toposort/toposort_test.go
@@ -0,0 +1,62 @@
+package toposort
+
+import "testing"
+
+func TestBasic(t *testing.T) {
+ // Test the example from Wikipedia's Topological sorting page
+ var g Graph[int]
+ g.AddEdge(5, 11)
+ g.AddEdge(11, 2)
+ g.AddEdge(7, 11)
+ g.AddEdge(7, 8)
+ g.AddEdge(11, 9)
+ g.AddEdge(8, 9)
+ g.AddEdge(11, 10)
+ g.AddEdge(3, 8)
+ g.AddEdge(3, 10)
+
+ solution, err := g.TopologicalOrder()
+ if err != nil {
+ t.Fatal(err)
+ }
+ validateSolution(t, g, solution)
+}
+
+// Fuzzer can be run with
+// bazel test //go/algorithm/toposort:toposort_test
+// --test_arg=-test.fuzz=FuzzTopoSort
+// --test_arg=-test.fuzzcachedir=/tmp/fuzz
+// --test_arg=-test.fuzztime=60s
+
+func FuzzTopoSort(f *testing.F) {
+ // Add starting example from above
+ f.Add([]byte{5, 11, 11, 2, 7, 11, 7, 8, 11, 9, 8, 9, 11, 10, 3, 8, 3, 10})
+ f.Fuzz(func(t *testing.T, a []byte) {
+ var g Graph[int]
+ for i := 0; i < len(a)-1; i += 2 {
+ g.AddEdge(int(a[i]), int(a[i+1]))
+ }
+ solution, err := g.TopologicalOrder()
+ if err == ErrCycle {
+ // Cycle found
+ return
+ }
+ if err != nil {
+ t.Error(err)
+ }
+ validateSolution(t, g, solution)
+ })
+}
+
+func validateSolution(t *testing.T, g Graph[int], solution []int) {
+ t.Helper()
+ visited := make(map[int]bool)
+ for _, n := range solution {
+ visited[n] = true
+ for m := range g.nodes[n] {
+ if !visited[m] {
+ t.Errorf("node %d has an edge to node %d, but not yet visited", n, m)
+ }
+ }
+ }
+}