g/a/toposort: add deterministic version
Adds a slower, but deterministic version of TopologicalOrder. To make
implementation easier, the visit recursive function is slightly
refactored.
Both implementations look very similar, but it adds more lines to keep a
common implementation versus just having two separate functions.
Change-Id: Ife4cbda128cf476005b75e216352b522b949d6a2
Reviewed-on: https://review.monogon.dev/c/monogon/+/3137
Reviewed-by: Serge Bazanski <serge@monogon.tech>
Tested-by: Jenkins CI
diff --git a/go/algorithm/toposort/toposort.go b/go/algorithm/toposort/toposort.go
index 0f39512..07ee267 100644
--- a/go/algorithm/toposort/toposort.go
+++ b/go/algorithm/toposort/toposort.go
@@ -1,6 +1,9 @@
package toposort
-import "errors"
+import (
+ "errors"
+ "slices"
+)
type outEdges[Node comparable] map[Node]bool
@@ -103,33 +106,79 @@
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 {
+ var visit func(nodes map[T]bool) error
+ visit = func(nodes map[T]bool) error {
+ for n := range nodes {
+ if !unmarkedNodes[n] {
+ continue
+ }
+ // 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.
+ if err := visit(g.nodes[n]); err != nil {
return err
}
+ delete(nodeVisitStack, n)
+ delete(unmarkedNodes, n)
+ solution = append(solution, n)
}
- 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
+ if err := visit(unmarkedNodes); err != nil {
+ return nil, err
+ }
+ return solution, nil
+}
+
+// DetTopologicalOrder is a deterministic version of TopologicalSort which has
+// higher cyclomatic complexity. See TopologicalSort for further documentation.
+func (g *Graph[T]) DetTopologicalOrder(cmp func(a, b T) int) ([]T, error) {
+ g.ensureNodes()
+ // Depth-first search-based implementation with
+ // O(|n| log(|n|) + |E| log(|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(nodes map[T]bool) error
+ visit = func(nodes map[T]bool) error {
+ sortedOrder := make([]T, 0, len(nodes))
+ for n := range nodes {
+ if !unmarkedNodes[n] {
+ continue
+ }
+ sortedOrder = append(sortedOrder, n)
}
+ slices.SortFunc(sortedOrder, cmp)
+ for _, n := range sortedOrder {
+ // 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.
+ if err := visit(g.nodes[n]); err != nil {
+ return err
+ }
+ delete(nodeVisitStack, n)
+ delete(unmarkedNodes, n)
+ solution = append(solution, n)
+ }
+ return nil
+ }
+
+ if err := visit(unmarkedNodes); err != nil {
+ return nil, err
}
return solution, nil
}
diff --git a/go/algorithm/toposort/toposort_test.go b/go/algorithm/toposort/toposort_test.go
index 09851e2..e2ab8e7 100644
--- a/go/algorithm/toposort/toposort_test.go
+++ b/go/algorithm/toposort/toposort_test.go
@@ -1,7 +1,9 @@
package toposort
import (
+ "cmp"
"errors"
+ "slices"
"testing"
)
@@ -23,6 +25,12 @@
t.Fatal(err)
}
validateSolution(t, g, solution)
+
+ detSolution, err := g.DetTopologicalOrder(cmp.Compare)
+ if err != nil {
+ t.Fatal(err)
+ }
+ validateSolution(t, g, detSolution)
}
func TestImplicitNodesEmpty(t *testing.T) {
@@ -71,6 +79,34 @@
}
}
+func TestTopoSortDet(t *testing.T) {
+ 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)
+
+ firstSolution, err := g.DetTopologicalOrder(cmp.Compare)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ for i := 0; i < 100; i++ {
+ sol, err := g.DetTopologicalOrder(cmp.Compare)
+ if err != nil {
+ t.Fatal(err)
+ }
+ if !slices.Equal(firstSolution, sol) {
+ t.Fatalf("solution in iteration %v (%v) is not equal to first solution (%v)", i, firstSolution, sol)
+ }
+ }
+}
+
// Fuzzer can be run with
// bazel test //go/algorithm/toposort:toposort_test
// --test_arg=-test.fuzz=FuzzTopoSort
@@ -94,6 +130,16 @@
t.Error(err)
}
validateSolution(t, g, solution)
+
+ detSolution, err := g.DetTopologicalOrder(cmp.Compare)
+ if errors.Is(err, ErrCycle) {
+ // Cycle found
+ return
+ }
+ if err != nil {
+ t.Error(err)
+ }
+ validateSolution(t, g, detSolution)
})
}