forked from openshift/origin
-
Notifications
You must be signed in to change notification settings - Fork 0
/
control_flow.go
118 lines (103 loc) · 2.79 KB
/
control_flow.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
// Copyright ©2014 The gonum 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 path
import (
"github.com/gonum/graph"
"github.com/gonum/graph/internal"
)
// PostDominatores returns all dominators for all nodes in g. It does not
// prune for strict post-dominators, immediate dominators etc.
//
// A dominates B if and only if the only path through B travels through A.
func Dominators(start graph.Node, g graph.Graph) map[int]internal.Set {
allNodes := make(internal.Set)
nlist := g.Nodes()
dominators := make(map[int]internal.Set, len(nlist))
for _, node := range nlist {
allNodes.Add(node)
}
var to func(graph.Node) []graph.Node
switch g := g.(type) {
case graph.Directed:
to = g.To
default:
to = g.From
}
for _, node := range nlist {
dominators[node.ID()] = make(internal.Set)
if node.ID() == start.ID() {
dominators[node.ID()].Add(start)
} else {
dominators[node.ID()].Copy(allNodes)
}
}
for somethingChanged := true; somethingChanged; {
somethingChanged = false
for _, node := range nlist {
if node.ID() == start.ID() {
continue
}
preds := to(node)
if len(preds) == 0 {
continue
}
tmp := make(internal.Set).Copy(dominators[preds[0].ID()])
for _, pred := range preds[1:] {
tmp.Intersect(tmp, dominators[pred.ID()])
}
dom := make(internal.Set)
dom.Add(node)
dom.Union(dom, tmp)
if !internal.Equal(dom, dominators[node.ID()]) {
dominators[node.ID()] = dom
somethingChanged = true
}
}
}
return dominators
}
// PostDominatores returns all post-dominators for all nodes in g. It does not
// prune for strict post-dominators, immediate post-dominators etc.
//
// A post-dominates B if and only if all paths from B travel through A.
func PostDominators(end graph.Node, g graph.Graph) map[int]internal.Set {
allNodes := make(internal.Set)
nlist := g.Nodes()
dominators := make(map[int]internal.Set, len(nlist))
for _, node := range nlist {
allNodes.Add(node)
}
for _, node := range nlist {
dominators[node.ID()] = make(internal.Set)
if node.ID() == end.ID() {
dominators[node.ID()].Add(end)
} else {
dominators[node.ID()].Copy(allNodes)
}
}
for somethingChanged := true; somethingChanged; {
somethingChanged = false
for _, node := range nlist {
if node.ID() == end.ID() {
continue
}
succs := g.From(node)
if len(succs) == 0 {
continue
}
tmp := make(internal.Set).Copy(dominators[succs[0].ID()])
for _, succ := range succs[1:] {
tmp.Intersect(tmp, dominators[succ.ID()])
}
dom := make(internal.Set)
dom.Add(node)
dom.Union(dom, tmp)
if !internal.Equal(dom, dominators[node.ID()]) {
dominators[node.ID()] = dom
somethingChanged = true
}
}
}
return dominators
}