[tools] internal/graph: add ShortestPath, use in cmd/digraph
5 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 ShortestPath, use in cmd/digraph
Change-Id: I134a6cafcfa5e51750fa85a16195c20e65101f77
Change diff
diff --git a/cmd/digraph/digraph.go b/cmd/digraph/digraph.go
index 7813729..0e9caeb 100644
--- a/cmd/digraph/digraph.go
+++ b/cmd/digraph/digraph.go
@@ -73,8 +73,6 @@
type nodeset map[string]bool
-func singleton(x string) nodeset { return nodeset{x: true} }
-
func (s nodeset) sort() nodelist {
nodes := make(nodelist, len(s))
var i int
@@ -186,44 +184,14 @@
}
func (g digraph) somepath(from, to string) error {
- // Search breadth-first so that we return a minimal path.
-
- // A path is a linked list whose head is a candidate "to" node
- // and whose tail is the path ending in the "from" node.
- type path struct {
- node string
- tail *path
+ path := graph.ShortestPath(g, from, to)
+ if path == nil {
+ return fmt.Errorf("no path from %q to %q", from, to)
}
-
- seen := singleton(from)
-
- var queue []*path
- queue = append(queue, &path{node: from, tail: nil})
- for len(queue) > 0 {
- p := queue[0]
- queue = queue[1:]
-
- if p.node == to {
- // Found a path. Print, tail first.
- var print func(p *path)
- print = func(p *path) {
- if p.tail != nil {
- print(p.tail)
- fmt.Fprintln(stdout, p.tail.node+" "+p.node)
- }
- }
- print(p)
- return nil
- }
-
- for succ := range g[p.node] {
- if !seen[succ] {
- seen[succ] = true
- queue = append(queue, &path{node: succ, tail: p})
- }
- }
+ for i := 0; i < len(path)-1; i++ {
+ fmt.Fprintln(stdout, path[i]+" "+path[i+1])
}
- return fmt.Errorf("no path from %q to %q", from, to)
+ return nil
}
func (g digraph) toDot(w *bytes.Buffer) {
diff --git a/internal/graph/shortest.go b/internal/graph/shortest.go
new file mode 100644
index 0000000..5650ac4
--- /dev/null
+++ b/internal/graph/shortest.go
@@ -0,0 +1,45 @@
+// 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 "slices"
+
+// ShortestPath returns a shortest path from src to dst in g.
+// It returns the path as a slice of nodes starting with src and ending with dst.
+// If no path is found, it returns nil.
+func ShortestPath[NodeID comparable](g Graph[NodeID], src, dst NodeID) []NodeID {
+ if src == dst {
+ return []NodeID{src}
+ }
+
+ pred := make(map[NodeID]NodeID)
+ queue := []NodeID{src}
+ // Mark src as seen.
+ pred[src] = src
+
+ for len(queue) > 0 {
+ n := queue[0]
+ queue = queue[1:]
+
+ if n == dst {
+ // Reconstruct path
+ var path []NodeID
+ for curr := dst; curr != src; curr = pred[curr] {
+ path = append(path, curr)
+ }
+ path = append(path, src)
+ slices.Reverse(path)
+ return path
+ }
+
+ for _, v := range g.Out(n) {
+ if _, seen := pred[v]; !seen {
+ pred[v] = n
+ queue = append(queue, v)
+ }
+ }
+ }
+ return nil
+}
diff --git a/internal/graph/shortest_test.go b/internal/graph/shortest_test.go
new file mode 100644
index 0000000..e9bc8fa
--- /dev/null
+++ b/internal/graph/shortest_test.go
@@ -0,0 +1,31 @@
+// 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 (
+ "slices"
+ "testing"
+)
+
+func TestShortestPath(t *testing.T) {
+ g := stringGraph{
+ "A": {"B", "C"},
+ "B": {"D"},
+ "C": {"D"},
+ "D": {"E"},
+ "E": {},
+ }
+
+ got := ShortestPath(g, "A", "E")
+ want := []string{"A", "B", "D", "E"}
+ if !slices.Equal(got, want) {
+ t.Errorf("ShortestPath(A, E) = %v, want %v", got, want)
+ }
+
+ got = ShortestPath(g, "A", "F")
+ if got != nil {
+ t.Errorf("ShortestPath(A, F) = %v, want nil", got)
+ }
+}
Change information
Files:
- M cmd/digraph/digraph.go
- A internal/graph/shortest.go
- A internal/graph/shortest_test.go
Change size: M
Delta: 3 files changed, 82 insertions(+), 38 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:48:15 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 Code-Review+2![]( "Open in Gerrit")
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:26 PM (7 hours ago) Feb 24
to Austin Clements, goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from Austin Clements
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 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. |
Reply all
Reply to author
Forward
0 new messages