g/a/toposort: add bad reference validation
In a lot of cases where toposort is used to build dependency trees it
might be necessary to validate that the edges which make up the tree
do not reference nodes which are not present.
This is implemented by still implicitly creating nodes when AddEdge is
called, which allows arbitrary ordering of AddEdge/AddNode calls, but
on explicit calls to AddNode the node is also marked as being explicitly
added.
This information is later used to implement ImplicitNodeReferences which
returns all invalid references in the graph.
Change-Id: Ia19560b98d00dcc10b5d0ad0e12b212bea586c04
Reviewed-on: https://review.monogon.dev/c/monogon/+/1507
Tested-by: Jenkins CI
Reviewed-by: Serge Bazanski <serge@monogon.tech>
diff --git a/go/algorithm/toposort/toposort.go b/go/algorithm/toposort/toposort.go
index 6164b91..0f39512 100644
--- a/go/algorithm/toposort/toposort.go
+++ b/go/algorithm/toposort/toposort.go
@@ -8,18 +8,32 @@
// Its nodes have type T. An empty Graph object is ready to use.
type Graph[T comparable] struct {
nodes map[T]outEdges[T]
+ // Set of nodes added explicitly, used to check for references to nodes
+ // which haven't been added explicitly.
+ addedNodes map[T]bool
}
func (g *Graph[T]) ensureNodes() {
if g.nodes == nil {
g.nodes = make(map[T]outEdges[T])
}
+ if g.addedNodes == nil {
+ g.addedNodes = make(map[T]bool)
+ }
}
// 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()
+ g.addedNodes[n] = true
+ g.addNodeImplicit(n)
+}
+
+// addNodeImplicit adds the node n to the graph if it does not already exist
+// without marking it as being explicitly added and without ensuring that
+// g.nodes is populated.
+func (g *Graph[T]) addNodeImplicit(n T) {
if _, ok := g.nodes[n]; !ok {
g.nodes[n] = make(outEdges[T])
}
@@ -27,13 +41,45 @@
// 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.
+// If nodes from and/or to do not already exist, they are added implicitly.
func (g *Graph[T]) AddEdge(from, to T) {
g.ensureNodes()
- g.AddNode(from)
- g.AddNode(to)
+ g.addNodeImplicit(from)
+ g.addNodeImplicit(to)
g.nodes[from][to] = true
}
+// ImplicitNodeReferences returns a map of nodes with the set of their incoming
+// and outgoing references for all nodes which were referenced in an AddEdge
+// call but not added via an explicit AddNode. If the length of the returned map
+// is zero, all referenced nodes were explicitly added. This can be used to
+// check for bad references in dependency trees.
+func (g *Graph[T]) ImplicitNodeReferences() map[T]map[T]bool {
+ out := make(map[T]map[T]bool)
+ for n, outEdges := range g.nodes {
+ if !g.addedNodes[n] {
+ if out[n] == nil {
+ out[n] = make(map[T]bool)
+ }
+ // Add all outgoing edges, the refernces from these must come from
+ // reverse dependencies as this node was never added.
+ for e := range outEdges {
+ out[n][e] = true
+ }
+ }
+ for e := range outEdges {
+ // Add incoming edges to unreferenced nodes.
+ if !g.addedNodes[e] {
+ if out[e] == nil {
+ out[e] = make(map[T]bool)
+ }
+ out[e][n] = true
+ }
+ }
+ }
+ return out
+}
+
var ErrCycle = errors.New("graph has at least one cycle")
// TopologicalOrder sorts the nodes in the graph according to their topological
diff --git a/go/algorithm/toposort/toposort_test.go b/go/algorithm/toposort/toposort_test.go
index d2ec65a..490ddbf 100644
--- a/go/algorithm/toposort/toposort_test.go
+++ b/go/algorithm/toposort/toposort_test.go
@@ -22,6 +22,52 @@
validateSolution(t, g, solution)
}
+func TestImplicitNodesEmpty(t *testing.T) {
+ var g Graph[int]
+ g.AddNode(5)
+ g.AddNode(10)
+ g.AddEdge(5, 10)
+
+ out := g.ImplicitNodeReferences()
+ if len(out) != 0 {
+ t.Errorf("expected no implicit nodes, got %d", len(out))
+ }
+}
+
+func TestImplicitNodesForward(t *testing.T) {
+ var g Graph[int]
+ g.AddNode(5)
+ g.AddEdge(5, 10)
+
+ out := g.ImplicitNodeReferences()
+ if len(out) != 1 {
+ t.Errorf("expected 1 implicit node, got %d", len(out))
+ }
+ if len(out[10]) != 1 {
+ t.Error("expected node 10 to be implicit")
+ }
+ if !out[10][5] {
+ t.Errorf("expected node 10 to be referenced by node 5")
+ }
+}
+
+func TestImplicitNodesBackwards(t *testing.T) {
+ var g Graph[int]
+ g.AddNode(10)
+ g.AddEdge(5, 10)
+
+ out := g.ImplicitNodeReferences()
+ if len(out) != 1 {
+ t.Errorf("expected 1 implicit node, got %d", len(out))
+ }
+ if len(out[5]) != 1 {
+ t.Error("expected node 5 to be implicit")
+ }
+ if !out[5][10] {
+ t.Errorf("expected node 5 to be referenced by node 10")
+ }
+}
+
// Fuzzer can be run with
// bazel test //go/algorithm/toposort:toposort_test
// --test_arg=-test.fuzz=FuzzTopoSort