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

Change-Id: Icd748dae9383580341f899cbf7242f4b4a5ee129
Reviewed-on: https://go-review.googlesource.com/c/tools/+/747367
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Alan Donovan <adonovan@google.com>

cmd/digraph/digraph.go

diff --git a/cmd/digraph/digraph.go b/cmd/digraph/digraph.go
index 4da43b5..2a9ac84 100644
--- a/cmd/digraph/digraph.go
+++ b/cmd/digraph/digraph.go
@@ -156,17 +156,7 @@
 }
 
 func (g digraph) allpaths(from, to string) error {
-	// We intersect the forward closure of 'from' with
-	// the reverse closure of 'to'. This is not the most
-	// efficient implementation, but it's the clearest,
-	// and the previous one had bugs.
-	seen := nodeset(graph.Reachable(g, from))
-	rev := nodeset(graph.Reachable(g.transpose(), to))
-	for n := range seen {
-		if !rev[n] {
-			delete(seen, n)
-		}
-	}
+	seen := graph.AllPaths(g, from, to)
 
 	// For each marked node, collect its marked successors.
 	var edges []string

internal/graph/allpaths.go

diff --git a/internal/graph/allpaths.go b/internal/graph/allpaths.go
new file mode 100644
index 0000000..4473255
--- /dev/null
+++ b/internal/graph/allpaths.go
@@ -0,0 +1,24 @@
+// 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
+
+// AllPaths returns the set of nodes that are part of at least one path from src to dst.
+func AllPaths[NodeID comparable](g Graph[NodeID], src, dst NodeID) map[NodeID]bool {
+	// We intersect the forward closure of 'src' with
+	// the reverse closure of 'dst'. This is not the most
+	// efficient implementation, but it's the clearest,
+	// and the previous one had bugs.
+
+	fwd := Reachable(g, src)
+	rev := Reachable(Transpose(g), dst)
+
+	// Intersection
+	for n := range fwd {
+		if !rev[n] {
+			delete(fwd, n)
+		}
+	}
+	return fwd
+}

internal/graph/allpaths_test.go

diff --git a/internal/graph/allpaths_test.go b/internal/graph/allpaths_test.go
new file mode 100644
index 0000000..acab0be
--- /dev/null
+++ b/internal/graph/allpaths_test.go
@@ -0,0 +1,106 @@
+// 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 (
+	"maps"
+	"slices"
+	"testing"
+)
+
+func TestAllPaths(t *testing.T) {
+	g := stringGraph{
+		"A": {"B", "C"},
+		"B": {"D"},
+		"C": {"D", "E"},
+		"D": {"F"},
+		"E": {},
+		"F": {},
+	}
+
+	// Paths in g:
+	//
+	// A->B->D->F
+	// A->C->D->F
+	// A->C->E
+
+	// AllPaths(A, F) should include A, B, C, D, F. E is not on path to F.
+	got := slices.Sorted(maps.Keys(AllPaths(g, "A", "F")))
+	want := []string{"A", "B", "C", "D", "F"}
+	if !slices.Equal(got, want) {
+		t.Errorf("AllPaths(A, F) = %v, want %v", got, want)
+	}
+
+	// AllPaths(A, E) -> A, C, E. B is not on path.
+	got = slices.Sorted(maps.Keys(AllPaths(g, "A", "E")))
+	want = []string{"A", "C", "E"}
+	if !slices.Equal(got, want) {
+		t.Errorf("AllPaths(A, E) = %v, want %v", got, want)
+	}
+}
+
+func TestAllPaths_74842(t *testing.T) {
+	tests := []struct {
+		name     string
+		g        stringGraph
+		src, dst string
+		want     []string
+	}{
+		{
+			// C <--> B --> A --> D <--> E
+			//        ⋃
+			name: "non-regression test for #74842",
+			g: stringGraph{
+				"A": {"D"},
+				"B": {"A", "B", "C"},
+				"C": {"B"},
+				"D": {"E"},
+				"E": {"D"},
+			},
+			src: "A", dst: "D",
+			want: []string{"A", "D", "E"},
+		},
+		{
+			// A --> B --> D
+			//       ^
+			//       v
+			//       C[123]
+			name: "regression test for #74842",
+			g: stringGraph{
+				"A":  {"B"},
+				"B":  {"C1", "C2", "C3", "D"},
+				"C1": {"B"},
+				"C2": {"B"},
+				"C3": {"B"},
+			},
+			src: "A", dst: "D",
+			want: []string{"A", "B", "C1", "C2", "C3", "D"},
+		},
+		{
+			// A -------> B --> D
+			//  \--> C ---^     |
+			//       ^----------+
+			name: "another regression test for #74842",
+			g: stringGraph{
+				"A": {"B", "C"},
+				"B": {"D"},
+				"C": {"B"},
+				"D": {"C"},
+			},
+			src: "A", dst: "D",
+			want: []string{"A", "B", "C", "D"},
+		},
+	}
+
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			allPaths := AllPaths(tt.g, tt.src, tt.dst)
+			got := slices.Sorted(maps.Keys(allPaths))
+			if !slices.Equal(got, tt.want) {
+				t.Errorf("got %v, want %v", got, tt.want)
+			}
+		})
+	}
+}