[tools] internal/graph: add AllPaths, use in cmd/digraph
4 views
Skip to first unread message
Austin Clements (Gerrit)
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![]( "Open in Gerrit")
Austin Clements would like Alan Donovan to review this change.
Commit message
internal/graph: add AllPaths, use in cmd/digraph
Change-Id: Icd748dae9383580341f899cbf7242f4b4a5ee129
Change diff
diff --git a/cmd/digraph/digraph.go b/cmd/digraph/digraph.go
index 0e9caeb..b11ab77 100644
--- a/cmd/digraph/digraph.go
+++ b/cmd/digraph/digraph.go
@@ -152,17 +152,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
diff --git a/internal/graph/allpaths.go b/internal/graph/allpaths.go
new file mode 100644
index 0000000..4ad97fc
--- /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(NewTranspose(g), dst)
+
+ // Intersection
+ for n := range fwd {
+ if !rev[n] {
+ delete(fwd, n)
+ }
+ }
+ return fwd
+}
diff --git a/internal/graph/allpaths_test.go b/internal/graph/allpaths_test.go
new file mode 100644
index 0000000..1f814ad
--- /dev/null
+++ b/internal/graph/allpaths_test.go
@@ -0,0 +1,42 @@
+// 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)
+ }
+}
Change information
Files:
- M cmd/digraph/digraph.go
- A internal/graph/allpaths.go
- A internal/graph/allpaths_test.go
Change size: M
Delta: 3 files changed, 67 insertions(+), 11 deletions(-)
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. |
Alan Donovan (Gerrit)
Feb 23, 2026, 2:54:05 PM (2 days ago) Feb 23
to Austin Clements, goph...@pubsubhelper.golang.org, Go LUCI, golang-co...@googlegroups.com
Attention needed from Austin Clements
Alan Donovan voted and added 1 comment![]( "Open in Gerrit")
Votes added by Alan Donovan
| Code-Review | +2 |
1 comment
File internal/graph/allpaths.go
Line 12, Patchset 1 (Latest):
// and the previous one had bugs.Alan Donovan . unresolved
See CL 692675 for a test case you might want to include.
Related details
Attention is currently required from:
- Austin Clements
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. |
Austin Clements (Gerrit)
Feb 24, 2026, 10:03:24 PM (7 hours ago) Feb 24
to Austin Clements, goph...@pubsubhelper.golang.org, Alan Donovan, Go LUCI, golang-co...@googlegroups.com
Austin Clements added 1 comment![]( "Open in Gerrit")
File internal/graph/allpaths.go
See CL 692675 for a test case you might want to include.
Austin Clements
Done
Related details
Attention set is empty
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. |
Austin Clements (Gerrit)
Feb 24, 2026, 10:03:26 PM (7 hours ago) Feb 24
to Austin Clements, goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Austin Clements uploaded new patchset![]( "Open in Gerrit")
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
Related details
Attention set is empty
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. |
Reply all
Reply to author
Forward
0 new messages