graph/path: implement sophisticated algorithm
Both algorithms are included since the LTA appears to beat the SLTA for
all normal uses, but the SLTA beats the LTA for very large dense graphs.
Leave tools in the benchmark code to allow users to determine which one
they want to use for their data.
MODIFY
graph/path/control_flow_bench_test.go
graph/path/control_flow_bench_test.go
package path
import (
+ "flag"
"fmt"
"io/ioutil"
"math"
@@ -23,6 +24,8 @@ import (
"gonum.org/v1/gonum/graph/topo"
)
+var slta = flag.Bool("slta", false, "specify DominatorsSLT benchmark")
+
func BenchmarkDominators(b *testing.B) {
testdata := filepath.FromSlash("./testdata/flow")
@@ -55,6 +58,16 @@ func BenchmarkDominators(b *testing.B) {
continue
}
+ if *slta {
+ b.Run(test, func(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ d := DominatorsSLT(g.root, g)
+ if got := d.Root(); got.ID() != want.ID() {
+ b.Fatalf("unexpected root node: got:%d want:%d", got.ID(), want.ID())
+ }
+ }
+ })
+ } else {
b.Run(test, func(b *testing.B) {
for i := 0; i < b.N; i++ {
d := Dominators(g.root, g)
@@ -65,6 +78,7 @@ func BenchmarkDominators(b *testing.B) {
})
}
}
+}
type labeled struct {
*simple.DirectedGraph

RENAME
graph/path/control_flow.go
graph/path/control_flow_lt.go
MODIFY
graph/path/control_flow_test.go
graph/path/control_flow_test.go
@@ -138,20 +138,31 @@ func TestDominators(t *testing.T) {
g.SetEdge(e)
}
- got := Dominators(test.n, g)
+ for _, alg := range []struct {
+ name string
+ fn func(graph.Node, graph.Directed) DominatorTree
+ }{
+ {"Dominators", Dominators},
+ {"DominatorsSLT", DominatorsSLT},
+ } {
+ got := alg.fn(test.n, g)
if !reflect.DeepEqual(got.root, test.want.root) {
- t.Errorf("unexpected dominator tree root: got:%v want:%v", got.root, test.want.root)
+ t.Errorf("unexpected dominator tree root from %s: got:%v want:%v",
+ alg.name, got.root, test.want.root)
}
if !reflect.DeepEqual(got.dominatorOf, test.want.dominatorOf) {
- t.Errorf("unexpected dominator tree: got:%v want:%v", got.dominatorOf, test.want.dominatorOf)
+ t.Errorf("unexpected dominator tree from %s: got:%v want:%v",
+ alg.name, got.dominatorOf, test.want.dominatorOf)
}
for _, nodes := range got.dominatedBy {
sort.Sort(ordered.ByID(nodes))
}
if !reflect.DeepEqual(got.dominatedBy, test.want.dominatedBy) {
- t.Errorf("unexpected dominator tree: got:%v want:%v", got.dominatedBy, test.want.dominatedBy)
+ t.Errorf("unexpected dominator tree from %s: got:%v want:%v",
+ alg.name, got.dominatedBy, test.want.dominatedBy)
+ }
}
}
}

graph/path: implement sophisticated algorithm

Both algorithms are included since the LTA appears to beat the SLTA for
all normal uses, but the SLTA beats the LTA for very large dense graphs.

Leave tools in the benchmark code to allow users to determine which one
they want to use for their data.