graph/path: add dominator tree API
MODIFY
graph/path/control_flow.go
graph/path/control_flow.go
@@ -10,9 +10,9 @@ import (
"gonum.org/v1/gonum/graph/traverse"
)
-// Dominators returns immediate dominators for all nodes in the flow graph
+// Dominators returns a dominator tree for all nodes in the flow graph
// g starting from the given root node.
-func Dominators(root graph.Node, g graph.Directed) map[int64]graph.Node {
+func Dominators(root graph.Node, g graph.Directed) DominatorTree {
// The algorithm used here is the Lengauer and Tarjan
// algorithm described in https://doi.org/10.1145%2F357062.357071
@@ -73,7 +73,16 @@ func Dominators(root graph.Node, g graph.Directed) map[int64]graph.Node {
}
delete(lt.dom, root.ID())
- return lt.dom
+ nodes := make(set.Nodes)
+ for _, n := range g.Nodes() {
+ nodes.Add(n)
+ }
+ dominatedBy := make(map[int64][]graph.Node)
+ for nid, d := range lt.dom {
+ did := d.ID()
+ dominatedBy[did] = append(dominatedBy[did], nodes[nid])
+ }
+ return DominatorTree{root: root, dominatorOf: lt.dom, dominatedBy: dominatedBy}
}
type lengauerTarjan struct {
@@ -161,3 +170,24 @@ func (lt *lengauerTarjan) eval(v graph.Node) graph.Node {
func (lt *lengauerTarjan) link(v, w graph.Node) {
lt.ancestor[w.ID()] = v
}
+
+// DominatorTree is a flow graph dominator tree.
+type DominatorTree struct {
+ root graph.Node
+ dominatorOf map[int64]graph.Node
+ dominatedBy map[int64][]graph.Node
+}
+
+// Root returns the root of the tree.
+func (d DominatorTree) Root() graph.Node { return d.root }
+
+// DominatorOf returns the immediate dominator of n.
+func (d DominatorTree) DominatorOf(n graph.Node) graph.Node {
+ return d.dominatorOf[n.ID()]
+}
+
+// DominatedBy returns a slice of all nodes immediately dominated by n.
+// Elements of the slice are retained by the DominatorTree.
+func (d DominatorTree) DominatedBy(n graph.Node) []graph.Node {
+ return d.dominatedBy[n.ID()]
+}

MODIFY
graph/path/control_flow_test.go
graph/path/control_flow_test.go
@@ -6,9 +6,11 @@ package path
import (
"reflect"
+ "sort"
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/ordered"
"gonum.org/v1/gonum/graph/simple"
)
@@ -16,13 +18,13 @@ var dominatorsTests = []struct {
n graph.Node
edges []simple.Edge
- want map[int64]graph.Node
+ want DominatorTree
}{
- { // Example from Lengauer and Tarjan, fig 1.
+ { // Example from Lengauer and Tarjan http://www.dtic.mil/dtic/tr/fulltext/u2/a054144.pdf fig 1.
n: char('R'),
edges: []simple.Edge{
{F: char('A'), T: char('D')},
- {F: char('B'), T: char('A')}, // Direction inferred from fig 3.
+ {F: char('B'), T: char('A')},
{F: char('B'), T: char('D')},
{F: char('B'), T: char('E')},
{F: char('C'), T: char('F')},
@@ -40,11 +42,13 @@ var dominatorsTests = []struct {
{F: char('K'), T: char('R')},
{F: char('L'), T: char('H')},
{F: char('R'), T: char('A')},
- {F: char('R'), T: char('B')}, // Direction inferred from fig 2.
+ {F: char('R'), T: char('B')},
{F: char('R'), T: char('C')},
},
- want: map[int64]graph.Node{
+ want: DominatorTree{
+ root: char('R'),
+ dominatorOf: map[int64]graph.Node{
'A': char('R'),
'B': char('R'),
'C': char('R'),
@@ -58,6 +62,13 @@ var dominatorsTests = []struct {
'K': char('R'),
'L': char('D'),
},
+ dominatedBy: map[int64][]graph.Node{
+ 'C': {char('F'), char('G')},
+ 'D': {char('L')},
+ 'G': {char('J')},
+ 'R': {char('A'), char('B'), char('C'), char('D'), char('E'), char('H'), char('I'), char('K')},
+ },
+ },
},
{ // WP example: https://en.wikipedia.org/w/index.php?title=Dominator_(graph_theory)&oldid=758099236.
n: simple.Node(1),
@@ -71,13 +82,20 @@ var dominatorsTests = []struct {
{F: simple.Node(5), T: simple.Node(2)},
},
- want: map[int64]graph.Node{
+ want: DominatorTree{
+ root: simple.Node(1),
+ dominatorOf: map[int64]graph.Node{
2: simple.Node(1),
3: simple.Node(2),
4: simple.Node(2),
5: simple.Node(2),
6: simple.Node(2),
},
+ dominatedBy: map[int64][]graph.Node{
+ 1: {simple.Node(2)},
+ 2: {simple.Node(3), simple.Node(4), simple.Node(5), simple.Node(6)},
+ },
+ },
},
{ // WP example with node IDs decremented by 1.
n: simple.Node(0),
@@ -91,13 +109,20 @@ var dominatorsTests = []struct {
{F: simple.Node(4), T: simple.Node(1)},
},
- want: map[int64]graph.Node{
+ want: DominatorTree{
+ root: simple.Node(0),
+ dominatorOf: map[int64]graph.Node{
1: simple.Node(0),
2: simple.Node(1),
3: simple.Node(1),
4: simple.Node(1),
5: simple.Node(1),
},
+ dominatedBy: map[int64][]graph.Node{
+ 0: {simple.Node(1)},
+ 1: {simple.Node(2), simple.Node(3), simple.Node(4), simple.Node(5)},
+ },
+ },
},
}
@@ -114,8 +139,19 @@ func TestDominators(t *testing.T) {
}
got := Dominators(test.n, g)
- if !reflect.DeepEqual(got, test.want) {
- t.Errorf("unexpected dominator tree: got:%v want:%v", got, test.want)
+ if !reflect.DeepEqual(got.root, test.want.root) {
+ t.Errorf("unexpected dominator tree root: got:%v want:%v", 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)
+ }
+
+ 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)
}
}
}

graph/path: add dominator tree API