Austin Clements (Gerrit)

unread,

Feb 19, 2026, 6:54:07 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 SCCs, use in cmd/digraph

Change-Id: I294ea979eda5bdd6b09983d3479ccec4fe1a3fae

Change diff

diff --git a/cmd/digraph/digraph.go b/cmd/digraph/digraph.go
index 9799f25..7813729 100644
--- a/cmd/digraph/digraph.go
+++ b/cmd/digraph/digraph.go
@@ -139,51 +139,16 @@
 }
 
 func (g digraph) sccs() []nodeset {
-	// Kosaraju's algorithm---Tarjan is overkill here.
-
-	// Forward pass.
-	S := make(nodelist, 0, len(g)) // postorder stack
-	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)
-			}
-			S = append(S, node)
-		}
-	}
-	for node := range g {
-		visit(node)
-	}
-
-	// Reverse pass.
-	rev := g.transpose()
-	var scc nodeset
-	seen = make(nodeset)
-	var rvisit func(node string)
-	rvisit = func(node string) {
-		if !seen[node] {
-			seen[node] = true
-			scc[node] = true
-			for e := range rev[node] {
-				rvisit(e)
-			}
-		}
-	}
 	var sccs []nodeset
-	for len(S) > 0 {
-		top := S[len(S)-1]
-		S = S[:len(S)-1] // pop
-		if !seen[top] {
-			scc = make(nodeset)
-			rvisit(top)
-			if len(scc) == 1 && !g[top][top] {
-				continue
-			}
-			sccs = append(sccs, scc)
+	for _, comp := range graph.SCCs(g) {
+		scc := make(nodeset)
+		for _, node := range comp {
+			scc[node] = true
 		}
+		if len(scc) == 1 && !g[comp[0]][comp[0]] {
+			continue
+		}
+		sccs = append(sccs, scc)
 	}
 	return sccs
 }
diff --git a/internal/graph/scc.go b/internal/graph/scc.go
new file mode 100644
index 0000000..6db1ef9
--- /dev/null
+++ b/internal/graph/scc.go
@@ -0,0 +1,40 @@
+// 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"
+
+// SCCs computes the strong connected components of the graph g
+// using Kosaraju's algorithm.
+func SCCs[NodeID comparable](g Graph[NodeID]) [][]NodeID {
+	// Tarjan is overkill here.
+
+	// Forward pass
+	S := Postorder(g)
+
+	// Reverse pass
+	gt := NewTranspose(g)
+	seen := make(map[NodeID]bool)
+	var scc []NodeID
+	var sccs [][]NodeID
+	var rvisit func(NodeID)
+	rvisit = func(u NodeID) {
+		if !seen[u] {
+			seen[u] = true
+			scc = append(scc, u)
+			for _, v := range gt.Out(u) {
+				rvisit(v)
+			}
+		}
+	}
+	for _, root := range slices.Backward(S) {
+		if !seen[root] {
+			scc = nil
+			rvisit(root)
+			sccs = append(sccs, scc)
+		}
+	}
+	return sccs
+}
diff --git a/internal/graph/scc_test.go b/internal/graph/scc_test.go
new file mode 100644
index 0000000..b0ac0cc
--- /dev/null
+++ b/internal/graph/scc_test.go
@@ -0,0 +1,64 @@
+// 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"
+	"slices"
+	"sort"
+	"testing"
+)
+
+func TestSCCs(t *testing.T) {
+	tests := []struct {
+		g    stringGraph
+		want [][]string
+	}{
+		{
+			g: stringGraph{
+				"A": {"B"},
+				"B": {"C"},
+				"C": {"A"},
+			},
+			want: [][]string{{"A", "B", "C"}},
+		},
+		{
+			g: stringGraph{
+				"A": {"B"},
+				"B": {},
+			},
+			want: [][]string{{"A"}, {"B"}},
+		},
+		{
+			g: stringGraph{
+				"A": {"A"},
+			},
+			want: [][]string{{"A"}},
+		},
+		{
+			g: stringGraph{
+				"A": {"B"},
+				"B": {"A"},
+				"C": {"D"},
+				"D": {"C"},
+			},
+			want: [][]string{{"A", "B"}, {"C", "D"}},
+		},
+	}
+
+	for _, test := range tests {
+		got := SCCs(test.g)
+
+		// Normalize for comparison: sort components, sort within components
+		for _, c := range got {
+			sort.Strings(c)
+		}
+		slices.SortFunc(got, slices.Compare)
+
+		if !reflect.DeepEqual(got, test.want) {
+			t.Errorf("SCCs(%v) = %v, want %v", test.g, got, test.want)
+		}
+	}
+}

Change information

Files:

M cmd/digraph/digraph.go
A internal/graph/scc.go
A internal/graph/scc_test.go

Change size: M

Delta: 3 files changed, 112 insertions(+), 43 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

Alan Donovan (Gerrit)

unread,

Feb 23, 2026, 2:45:58 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 3 comments

Votes added by Alan Donovan

Code-Review

+2

3 comments

File cmd/digraph/digraph.go

Line 149, Patchset 1 (Latest): continue

Alan Donovan . unresolved

continue // trivial SCC caused by self-edge

But now I wonder why the second clause was needed: doesn't len=1 imply a self-edge?

File internal/graph/scc.go

Line 9, Patchset 1 (Latest):// SCCs computes the strong connected components of the graph g

Alan Donovan . unresolved

strongly

Line 10, Patchset 1 (Latest):// using Kosaraju's algorithm.

Alan Donovan . unresolved

Implementation detail--move inside body.

Open in Gerrit

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.

Gerrit

satisfied_requirement

unsatisfied_requirement

open

diffy

Austin Clements (Gerrit)

unread,

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 3 comments

File cmd/digraph/digraph.go

Line 149, Patchset 1: continue

Alan Donovan . resolved

continue // trivial SCC caused by self-edge

But now I wonder why the second clause was needed: doesn't len=1 imply a self-edge?

Austin Clements

len=1 does not imply a self-edge. Consider

    A A
    A B
    B C

This has three SCCs: {A}, {B}, and {C}. All of them have len(scc) == 1, but {A} is kept by the second condition while {B} and {C} are filtered out.

Added a comment: "// trivial SCC without even a self-edge"

File internal/graph/scc.go

Line 9, Patchset 1:// SCCs computes the strong connected components of the graph g

Alan Donovan . resolved

strongly

Austin Clements

Done

Line 10, Patchset 1:// using Kosaraju's algorithm.

Alan Donovan . resolved

Implementation detail--move inside body.

Austin Clements

Done

Open in Gerrit

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.

Gerrit

satisfied_requirement

unsatisfied_requirement

open

diffy

Austin Clements (Gerrit)

unread,

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

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

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

Open in Gerrit

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.

Gerrit

satisfied_requirement

unsatisfied_requirement

open

diffy

Alan Donovan (Gerrit)

unread,

Feb 24, 2026, 10:09:18 PM (7 hours ago) Feb 24

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

Votes added by Alan Donovan

Code-Review

+2

1 comment

File cmd/digraph/digraph.go

Line 149, Patchset 1: continue

Alan Donovan . resolved

continue // trivial SCC caused by self-edge

But now I wonder why the second clause was needed: doesn't len=1 imply a self-edge?

Austin Clements

len=1 does not imply a self-edge. Consider
    A A
    A B
    B C
This has three SCCs: {A}, {B}, and {C}. All of them have len(scc) == 1, but {A} is kept by the second condition while {B} and {C} are filtered out.
Added a comment: "// trivial SCC without even a self-edge"

Alan Donovan

Duh, of course. Thanks.

Open in Gerrit

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.

Gerrit

satisfied_requirement

unsatisfied_requirement

open

diffy

Reply all

Reply to author

Forward

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

Austin Clements (Gerrit)

Austin Clements has uploaded the change for review

Commit message

Change diff

Change information

Related details

Alan Donovan (Gerrit)

Alan Donovan voted and added 3 comments

Votes added by Alan Donovan

3 comments

Related details

Austin Clements (Gerrit)

Austin Clements added 3 comments

Related details

Austin Clements (Gerrit)

Austin Clements uploaded new patchset

Related details

Alan Donovan (Gerrit)

Alan Donovan voted and added 1 comment

Votes added by Alan Donovan

1 comment

Related details