digraph: refactor allpaths to print an adjacency list
Refactors allpaths to print an adjacency list from "from" to "to", instead of
just the nodes. This allows other tools like modgraphviz to print the subgraph.
For example, the following command:
cd $GOPATH/src/cloud.google.com/go && \
go mod graph | \
digraph allpaths cloud.google.com/go golang.org/x/text@v0.3.2 | \
modgraphviz | \
dot -Tpng -o graph.png
Generates the following graph.png: https://user-images.githubusercontent.com/3584893/60481727-df0a8680-9c4b-11e9-8df9-c581d599edd1.png
Also splits out the allpaths tests into their own test, and adds many test
cases.
This is a breaking change. The previous behavior returned vertices; now it
returns edges. If you relied on the previous behavior, use:
my-application | digraph allpaths <from> <to> | digraph nodes
Change-Id: I2eb7c377f5fe1e1e90c5b74eaa78d5211192bb2a
Reviewed-on: https://go-review.googlesource.com/c/tools/+/184337
Reviewed-by: Alan Donovan <adonovan@google.com>
diff --git a/cmd/digraph/digraph.go b/cmd/digraph/digraph.go
index e3f8fac..6393f44 100644
--- a/cmd/digraph/digraph.go
+++ b/cmd/digraph/digraph.go
@@ -262,6 +262,47 @@
return sccs
}
+func (g graph) allpaths(from, to string) error {
+ // Mark all nodes to "to".
+ seen := make(nodeset) // value of seen[x] indicates whether x is on some path to "to"
+ var visit func(node string) bool
+ visit = func(node string) bool {
+ reachesTo, ok := seen[node]
+ if !ok {
+ reachesTo = node == to
+ seen[node] = reachesTo
+ for e := range g[node] {
+ if visit(e) {
+ reachesTo = true
+ }
+ }
+ if reachesTo && node != to {
+ seen[node] = true
+ }
+ }
+ return reachesTo
+ }
+ visit(from)
+
+ // For each marked node, collect its marked successors.
+ var edges []string
+ for n := range seen {
+ for succ := range g[n] {
+ if seen[succ] {
+ edges = append(edges, n+" "+succ)
+ }
+ }
+ }
+
+ // Sort (so that this method is deterministic) and print edges.
+ sort.Strings(edges)
+ for _, e := range edges {
+ fmt.Fprintln(stdout, e)
+ }
+
+ return nil
+}
+
func parse(rd io.Reader) (graph, error) {
g := make(graph)
@@ -284,6 +325,7 @@
return g, nil
}
+// Overridable for testing purposes.
var stdin io.Reader = os.Stdin
var stdout io.Writer = os.Stdout
@@ -398,33 +440,7 @@
if g[to] == nil {
return fmt.Errorf("no such 'to' node %q", to)
}
-
- seen := make(nodeset) // value of seen[x] indicates whether x is on some path to 'to'
- var visit func(label string) bool
- visit = func(label string) bool {
- reachesTo, ok := seen[label]
- if !ok {
- reachesTo = label == to
-
- seen[label] = reachesTo
- for e := range g[label] {
- if visit(e) {
- reachesTo = true
- }
- }
- seen[label] = reachesTo
- }
- return reachesTo
- }
- if !visit(from) {
- return fmt.Errorf("no path from %q to %q", from, to)
- }
- for label, reachesTo := range seen {
- if !reachesTo {
- delete(seen, label)
- }
- }
- seen.sort().println("\n")
+ g.allpaths(from, to)
case "sccs":
if len(args) != 0 {
diff --git a/cmd/digraph/digraph_test.go b/cmd/digraph/digraph_test.go
index 835290d..3376065 100644
--- a/cmd/digraph/digraph_test.go
+++ b/cmd/digraph/digraph_test.go
@@ -1,7 +1,6 @@
// Copyright 2019 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 main
import (
@@ -30,35 +29,34 @@
`
for _, test := range []struct {
+ name string
input string
cmd string
args []string
want string
}{
- {g1, "nodes", nil, "belt\nhat\njacket\npants\nshirt\nshoes\nshorts\nsocks\nsweater\ntie\n"},
- {g1, "reverse", []string{"jacket"}, "jacket\nshirt\nsweater\n"},
- {g1, "forward", []string{"socks"}, "shoes\nsocks\n"},
- {g1, "forward", []string{"socks", "sweater"}, "jacket\nshoes\nsocks\nsweater\n"},
-
- {g2, "allpaths", []string{"a", "d"}, "a\nb\nc\nd\n"},
-
- {g2, "sccs", nil, "a\nb\nc d\n"},
- {g2, "scc", []string{"d"}, "c\nd\n"},
- {g2, "succs", []string{"a"}, "b\nc\n"},
- {g2, "preds", []string{"c"}, "a\nd\n"},
- {g2, "preds", []string{"c", "d"}, "a\nb\nc\nd\n"},
+ {"nodes", g1, "nodes", nil, "belt\nhat\njacket\npants\nshirt\nshoes\nshorts\nsocks\nsweater\ntie\n"},
+ {"reverse", g1, "reverse", []string{"jacket"}, "jacket\nshirt\nsweater\n"},
+ {"forward", g1, "forward", []string{"socks"}, "shoes\nsocks\n"},
+ {"forward multiple args", g1, "forward", []string{"socks", "sweater"}, "jacket\nshoes\nsocks\nsweater\n"},
+ {"scss", g2, "sccs", nil, "a\nb\nc d\n"},
+ {"scc", g2, "scc", []string{"d"}, "c\nd\n"},
+ {"succs", g2, "succs", []string{"a"}, "b\nc\n"},
+ {"preds", g2, "preds", []string{"c"}, "a\nd\n"},
+ {"preds multiple args", g2, "preds", []string{"c", "d"}, "a\nb\nc\nd\n"},
} {
- stdin = strings.NewReader(test.input)
- stdout = new(bytes.Buffer)
- if err := digraph(test.cmd, test.args); err != nil {
- t.Error(err)
- continue
- }
+ t.Run(test.name, func(t *testing.T) {
+ stdin = strings.NewReader(test.input)
+ stdout = new(bytes.Buffer)
+ if err := digraph(test.cmd, test.args); err != nil {
+ t.Fatal(err)
+ }
- got := stdout.(fmt.Stringer).String()
- if got != test.want {
- t.Errorf("digraph(%s, %s) = %q, want %q", test.cmd, test.args, got, test.want)
- }
+ got := stdout.(fmt.Stringer).String()
+ if got != test.want {
+ t.Errorf("digraph(%s, %s) = got %q, want %q", test.cmd, test.args, got, test.want)
+ }
+ })
}
// TODO(adonovan):
@@ -66,6 +64,110 @@
// - test errors
}
+func TestAllpaths(t *testing.T) {
+ for _, test := range []struct {
+ name string
+ in string
+ to string // from is always "A"
+ want string
+ }{
+ {
+ name: "Basic",
+ in: "A B\nB C",
+ to: "B",
+ want: "A B\n",
+ },
+ {
+ name: "Long",
+ in: "A B\nB C\n",
+ to: "C",
+ want: "A B\nB C\n",
+ },
+ {
+ name: "Cycle Basic",
+ in: "A B\nB A",
+ to: "B",
+ want: "A B\nB A\n",
+ },
+ {
+ name: "Cycle Path Out",
+ // A <-> B -> C -> D
+ in: "A B\nB A\nB C\nC D",
+ to: "C",
+ want: "A B\nB A\nB C\n",
+ },
+ {
+ name: "Cycle Path Out Further Out",
+ // A -> B <-> C -> D -> E
+ in: "A B\nB C\nC D\nC B\nD E",
+ to: "D",
+ want: "A B\nB C\nC B\nC D\n",
+ },
+ {
+ name: "Two Paths Basic",
+ // /-> C --\
+ // A -> B -- -> E -> F
+ // \-> D --/
+ in: "A B\nB C\nC E\nB D\nD E\nE F",
+ to: "E",
+ want: "A B\nB C\nB D\nC E\nD E\n",
+ },
+ {
+ name: "Two Paths With One Immediately From Start",
+ // /-> B -+ -> D
+ // A -- |
+ // \-> C <+
+ in: "A B\nA C\nB C\nB D",
+ to: "C",
+ want: "A B\nA C\nB C\n",
+ },
+ {
+ name: "Two Paths Further Up",
+ // /-> B --\
+ // A -- -> D -> E -> F
+ // \-> C --/
+ in: "A B\nA C\nB D\nC D\nD E\nE F",
+ to: "E",
+ want: "A B\nA C\nB D\nC D\nD E\n",
+ },
+ {
+ // We should include A - C - D even though it's further up the
+ // second path than D (which would already be in the graph by
+ // the time we get around to integrating the second path).
+ name: "Two Splits",
+ // /-> B --\ /-> E --\
+ // A -- -> D -- -> G -> H
+ // \-> C --/ \-> F --/
+ in: "A B\nA C\nB D\nC D\nD E\nD F\nE G\nF G\nG H",
+ to: "G",
+ want: "A B\nA C\nB D\nC D\nD E\nD F\nE G\nF G\n",
+ },
+ {
+ // D - E should not be duplicated.
+ name: "Two Paths - Two Splits With Gap",
+ // /-> B --\ /-> F --\
+ // A -- -> D -> E -- -> H -> I
+ // \-> C --/ \-> G --/
+ in: "A B\nA C\nB D\nC D\nD E\nE F\nE G\nF H\nG H\nH I",
+ to: "H",
+ want: "A B\nA C\nB D\nC D\nD E\nE F\nE G\nF H\nG H\n",
+ },
+ } {
+ t.Run(test.name, func(t *testing.T) {
+ stdin = strings.NewReader(test.in)
+ stdout = new(bytes.Buffer)
+ if err := digraph("allpaths", []string{"A", test.to}); err != nil {
+ t.Fatal(err)
+ }
+
+ got := stdout.(fmt.Stringer).String()
+ if got != test.want {
+ t.Errorf("digraph(allpaths, A, %s) = got %q, want %q", test.to, got, test.want)
+ }
+ })
+ }
+}
+
func TestSplit(t *testing.T) {
for _, test := range []struct {
line string
