cmd/digraph: use graph.Transpose

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

cmd/digraph/digraph.go

diff --git a/cmd/digraph/digraph.go b/cmd/digraph/digraph.go
index 2a9ac84..a31e13e 100644
--- a/cmd/digraph/digraph.go
+++ b/cmd/digraph/digraph.go
@@ -84,12 +84,6 @@
 	return nodes
 }
 
-func (s nodeset) addAll(x nodeset) {
-	for node := range x {
-		s[node] = true
-	}
-}
-
 // A digraph maps nodes to the non-nil set of their immediate successors.
 type digraph map[string]nodeset
 
@@ -129,17 +123,6 @@
 	return nodelist(slices.Collect(g.Nodes()))
 }
 
-func (g digraph) transpose() digraph {
-	rev := make(digraph)
-	for node, edges := range g {
-		rev.addNode(node)
-		for succ := range edges {
-			rev.addEdges(succ, node)
-		}
-	}
-	return rev
-}
-
 func (g digraph) sccs() []nodeset {
 	var sccs []nodeset
 	for _, comp := range graph.SCCs(g) {
@@ -260,9 +243,13 @@
 		for node := range g {
 			nodes[node] = true
 		}
-		rev := g.transpose()
+		rev := graph.Transpose(g)
 		for _, node := range nodes.sort() {
-			fmt.Fprintf(stdout, "%d\t%d\t%s\n", len(rev[node]), len(g[node]), node)
+			inDegree := 0
+			for range rev.Out(node) {
+				inDegree++
+			}
+			fmt.Fprintf(stdout, "%d\t%d\t%s\n", inDegree, len(g[node]), node)
 		}
 
 	case "transpose":
@@ -270,8 +257,9 @@
 			return fmt.Errorf("usage: digraph transpose")
 		}
 		var revEdges []string
-		for node, succs := range g.transpose() {
-			for succ := range succs {
+		rev := graph.Transpose(g)
+		for node := range rev.Nodes() {
+			for succ := range rev.Out(node) {
 				revEdges = append(revEdges, fmt.Sprintf("%s %s", node, succ))
 			}
 		}
@@ -284,17 +272,18 @@
 		if len(args) == 0 {
 			return fmt.Errorf("usage: digraph %s <node> ... ", cmd)
 		}
-		g := g
+		var gr graph.Graph[string] = g
 		if cmd == "preds" {
-			g = g.transpose()
+			gr = graph.Transpose(g)
 		}
 		result := make(nodeset)
 		for _, root := range args {
-			edges := g[root]
-			if edges == nil {
+			if g[root] == nil {
 				return fmt.Errorf("no such node %q", root)
 			}
-			result.addAll(edges)
+			for succ := range gr.Out(root) {
+				result[succ] = true
+			}
 		}
 		result.sort().println("\n")
 
@@ -309,11 +298,11 @@
 			}
 			roots[root] = true
 		}
-		g := g
+		var gr graph.Graph[string] = g
 		if cmd == "reverse" {
-			g = g.transpose()
+			gr = graph.Transpose(g)
 		}
-		nodeset(graph.Reachable(g, roots.sort()...)).sort().println("\n")
+		nodeset(graph.Reachable(gr, roots.sort()...)).sort().println("\n")
 
 	case "somepath":
 		if len(args) != 2 {
@@ -391,9 +380,9 @@
 			}
 		}
 
-		gtrans := g.transpose()
+		gtrans := graph.Transpose(g)
 		for from := range graph.Reachable(gtrans, node) {
-			for to := range gtrans[from] {
+			for to := range gtrans.Out(from) {
 				edges[fmt.Sprintf("%s %s", to, from)] = struct{}{}
 			}
 		}