[tools] internal/graph: add Reachable, use in cmd/digraph

4 views

Skip to first unread message

Austin Clements (Gerrit)

unread,

Feb 19, 2026, 6:54:05 PM (5 days ago) Feb 19

to Alan Donovan, goph...@pubsubhelper.golang.org, Austin Clements, golang-co...@googlegroups.com

Attention needed from Alan Donovan

Austin Clements has uploaded the change for review

Austin Clements would like Alan Donovan to review this change.

Commit message

internal/graph: add Reachable, use in cmd/digraph

Change-Id: I985db02d26d4b40db6de0d82d260da4790e4cd67

Change diff

diff --git a/cmd/digraph/digraph.go b/cmd/digraph/digraph.go
index 1086fc5..9799f25 100644
--- a/cmd/digraph/digraph.go
+++ b/cmd/digraph/digraph.go
@@ -127,23 +127,6 @@
 	return nodelist(slices.Collect(g.All()))
 }
 
-func (g digraph) reachableFrom(roots nodeset) nodeset {
-	seen := make(nodeset)
-	var visit func(node string)
-	visit = func(node string) {
-		if !seen[node] {
-			seen[node] = true
-			for e := range g[node] {
-				visit(e)
-			}
-		}
-	}
-	for root := range roots {
-		visit(root)
-	}
-	return seen
-}
-
 func (g digraph) transpose() digraph {
 	rev := make(digraph)
 	for node, edges := range g {
@@ -210,8 +193,8 @@
 	// the reverse closure of 'to'. This is not the most
 	// efficient implementation, but it's the clearest,
 	// and the previous one had bugs.
-	seen := g.reachableFrom(singleton(from))
-	rev := g.transpose().reachableFrom(singleton(to))
+	seen := nodeset(graph.Reachable(g, from))
+	rev := nodeset(graph.Reachable(g.transpose(), to))
 	for n := range seen {
 		if !rev[n] {
 			delete(seen, n)
@@ -403,7 +386,7 @@
 		if cmd == "reverse" {
 			g = g.transpose()
 		}
-		g.reachableFrom(roots).sort().println("\n")
+		nodeset(graph.Reachable(g, roots.sort()...)).sort().println("\n")
 
 	case "somepath":
 		if len(args) != 2 {
@@ -475,14 +458,14 @@
 		}
 
 		edges := make(map[string]struct{})
-		for from := range g.reachableFrom(singleton(node)) {
+		for from := range graph.Reachable(g, node) {
 			for to := range g[from] {
 				edges[fmt.Sprintf("%s %s", from, to)] = struct{}{}
 			}
 		}
 
 		gtrans := g.transpose()
-		for from := range gtrans.reachableFrom(singleton(node)) {
+		for from := range graph.Reachable(gtrans, node) {
 			for to := range gtrans[from] {
 				edges[fmt.Sprintf("%s %s", to, from)] = struct{}{}
 			}
diff --git a/internal/graph/reachable.go b/internal/graph/reachable.go
new file mode 100644
index 0000000..378d76d
--- /dev/null
+++ b/internal/graph/reachable.go
@@ -0,0 +1,23 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package graph
+
+// Reachable returns the set of nodes reachable from the given roots.
+func Reachable[NodeID comparable](g Graph[NodeID], roots ...NodeID) map[NodeID]bool {
+	seen := make(map[NodeID]bool)
+	var visit func(node NodeID)
+	visit = func(node NodeID) {
+		if !seen[node] {
+			seen[node] = true
+			for _, e := range g.Out(node) {
+				visit(e)
+			}
+		}
+	}
+	for _, root := range roots {
+		visit(root)
+	}
+	return seen
+}
diff --git a/internal/graph/reachable_test.go b/internal/graph/reachable_test.go
new file mode 100644
index 0000000..50a4eb4
--- /dev/null
+++ b/internal/graph/reachable_test.go
@@ -0,0 +1,35 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package graph
+
+import (
+	"reflect"
+	"testing"
+)
+
+func TestReachable(t *testing.T) {
+	g := stringGraph{
+		"A": {"B", "C"},
+		"B": {"D"},
+		"C": {"D"},
+		"D": {},
+		"E": {"F"},
+		"F": {},
+	}
+
+	got := Reachable[string](g, "A")
+	want := map[string]bool{"A": true, "B": true, "C": true, "D": true}
+
+	if !reflect.DeepEqual(got, want) {
+		t.Errorf("Reachable(A) = %v, want %v", got, want)
+	}
+
+	got = Reachable[string](g, "E")
+	want = map[string]bool{"E": true, "F": true}
+
+	if !reflect.DeepEqual(got, want) {
+		t.Errorf("Reachable(E) = %v, want %v", got, want)
+	}
+}

Change information

Files:

M cmd/digraph/digraph.go
A internal/graph/reachable.go
A internal/graph/reachable_test.go

Change size: M

Delta: 3 files changed, 63 insertions(+), 22 deletions(-)

Open in Gerrit

Related details

Attention is currently required from:

Alan Donovan

Submit Requirements:

Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass

Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings.

Gerrit

unsatisfied_requirement

satisfied_requirement

open

diffy

Austin Clements (Gerrit)

unread,

Feb 24, 2026, 10:03:24 PM (6 hours ago) Feb 24

to Austin Clements, goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com

Attention needed from Alan Donovan

Austin Clements uploaded new patchset

Austin Clements uploaded patch set #2 to this change.

Following approvals got outdated and were removed:

TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI