Coveralls logob
Coveralls logo
  • Home
  • Features
  • Pricing
  • Docs
  • Sign In

gonum / gonum / 2249

24 Jul 2018 - 14:03 coverage increased (+3.5%) to 75.543%
2249

Pull #556

travis-ci

9181eb84f9c35729a3bad740fb7f9d93?size=18&default=identiconweb-flow
lapack/testlapack: clean up Dorg2lTest
Pull Request #556: lapack/testlapack: clean up and use isOrthogonal helper

42344 of 56053 relevant lines covered (75.54%)

13.9 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

91.75
/graph/path/control_flow_lt.go
1
// Copyright ©2017 The Gonum Authors. All rights reserved.
2
// Use of this source code is governed by a BSD-style
3
// license that can be found in the LICENSE file.
4

5
package path
6

7
import "gonum.org/v1/gonum/graph"
8

9
// Dominators returns a dominator tree for all nodes in the flow graph
10
// g starting from the given root node.
11
func Dominators(root graph.Node, g graph.Directed) DominatorTree {
16×
12
        // The algorithm used here is essentially the Lengauer and Tarjan
16×
13
        // algorithm described in https://doi.org/10.1145%2F357062.357071
16×
14

16×
15
        lt := lengauerTarjan{
16×
16
                indexOf: make(map[int64]int),
16×
17
        }
16×
18

16×
19
        // step 1.
16×
20
        lt.dfs(g, root)
16×
21

16×
22
        for i := len(lt.nodes) - 1; i > 0; i-- {
32×
23
                w := lt.nodes[i]
16×
24

16×
25
                // step 2.
16×
26
                for _, v := range w.pred {
32×
27
                        u := lt.eval(v)
16×
28

16×
29
                        if u.semi < w.semi {
32×
30
                                w.semi = u.semi
16×
31
                        }
16×
32
                }
33

34
                lt.nodes[w.semi].bucket[w] = struct{}{}
16×
35
                lt.link(w.parent, w)
16×
36

16×
37
                // step 3.
16×
38
                for v := range w.parent.bucket {
32×
39
                        delete(w.parent.bucket, v)
16×
40

16×
41
                        u := lt.eval(v)
16×
42
                        if u.semi < v.semi {
18×
UNCOV
43
                                v.dom = u
2×
44
                        } else {
18×
45
                                v.dom = w.parent
16×
46
                        }
16×
47
                }
48
        }
49

50
        // step 4.
51
        for _, w := range lt.nodes[1:] {
32×
52
                if w.dom.node.ID() != lt.nodes[w.semi].node.ID() {
18×
UNCOV
53
                        w.dom = w.dom.dom
2×
UNCOV
54
                }
2×
55
        }
56

57
        // Construct the public-facing dominator tree structure.
58
        dominatorOf := make(map[int64]graph.Node)
16×
59
        dominatedBy := make(map[int64][]graph.Node)
16×
60
        for _, w := range lt.nodes[1:] {
32×
61
                dominatorOf[w.node.ID()] = w.dom.node
16×
62
                did := w.dom.node.ID()
16×
63
                dominatedBy[did] = append(dominatedBy[did], w.node)
16×
64
        }
16×
65
        return DominatorTree{root: root, dominatorOf: dominatorOf, dominatedBy: dominatedBy}
16×
66
}
67

68
// lengauerTarjan holds global state of the Lengauer-Tarjan algorithm.
69
// This is a mapping between nodes and the postordering of the nodes.
70
type lengauerTarjan struct {
71
        // nodes is the nodes traversed during the
72
        // Lengauer-Tarjan depth-first-search.
73
        nodes []*ltNode
74
        // indexOf contains a mapping between
75
        // the id-dense representation of the
76
        // graph and the potentially id-sparse
77
        // nodes held in nodes.
78
        //
79
        // This corresponds to the vertex
80
        // number of the node in the Lengauer-
81
        // Tarjan algorithm.
82
        indexOf map[int64]int
83
}
84

85
// ltNode is a graph node with accounting for the Lengauer-Tarjan
86
// algorithm.
87
//
88
// For the purposes of documentation the ltNode is given the name w.
89
type ltNode struct {
90
        node graph.Node
91

92
        // parent is vertex which is the parent of w
93
        // in the spanning tree generated by the search.
94
        parent *ltNode
95

96
        // pred is the set of vertices v such that (v, w)
97
        // is an edge of the graph.
98
        pred []*ltNode
99

100
        // semi is a number defined as follows:
101
        // (i)  After w is numbered but before its semidominator
102
        //      is computed, semi is the number of w.
103
        // (ii) After the semidominator of w is computed, semi
104
        //      is the number of the semidominator of w.
105
        semi int
106

107
        // bucket is the set of vertices whose
108
        // semidominator is w.
109
        bucket map[*ltNode]struct{}
110

111
        // dom is vertex defined as follows:
112
        // (i)  After step 3, if the semidominator of w is its
113
        //      immediate dominator, then dom is the immediate
114
        //      dominator of w. Otherwise dom is a vertex v
115
        //      whose number is smaller than w and whose immediate
116
        //      dominator is also w's immediate dominator.
117
        // (ii) After step 4, dom is the immediate dominator of w.
118
        dom *ltNode
119

120
        // In general ancestor is nil only if w is a tree root
121
        // in the forest; otherwise ancestor is an ancestor
122
        // of w in the forest.
123
        ancestor *ltNode
124

125
        // Initially label is w. It is adjusted during
126
        // the algorithm to maintain invariant (3) in the
127
        // Lengauer and Tarjan paper.
128
        label *ltNode
129
}
130

131
// dfs is the Lengauer-Tarjan DFS procedure.
132
func (lt *lengauerTarjan) dfs(g graph.Directed, v graph.Node) {
16×
133
        i := len(lt.nodes)
16×
134
        lt.indexOf[v.ID()] = i
16×
135
        ltv := &ltNode{
16×
136
                node:   v,
16×
137
                semi:   i,
16×
138
                bucket: make(map[*ltNode]struct{}),
16×
139
        }
16×
140
        ltv.label = ltv
16×
141
        lt.nodes = append(lt.nodes, ltv)
16×
142

16×
143
        for _, w := range g.From(v.ID()) {
32×
144
                wid := w.ID()
16×
145

16×
146
                idx, ok := lt.indexOf[wid]
16×
147
                if !ok {
32×
148
                        lt.dfs(g, w)
16×
149

16×
150
                        // We place this below the recursive call
16×
151
                        // in contrast to the original algorithm
16×
152
                        // since w needs to be initialised, and
16×
153
                        // this happens in the child call to dfs.
16×
154
                        idx, ok = lt.indexOf[wid]
16×
155
                        if !ok {
16×
156
                                panic("path: unintialized node")
!
157
                        }
158
                        lt.nodes[idx].parent = ltv
16×
159
                }
160
                ltw := lt.nodes[idx]
16×
161
                ltw.pred = append(ltw.pred, ltv)
16×
162
        }
163
}
164

165
// compress is the Lengauer-Tarjan COMPRESS procedure.
166
func (lt *lengauerTarjan) compress(v *ltNode) {
16×
167
        if v.ancestor.ancestor != nil {
32×
168
                lt.compress(v.ancestor)
16×
169
                if v.ancestor.label.semi < v.label.semi {
32×
170
                        v.label = v.ancestor.label
16×
171
                }
16×
172
                v.ancestor = v.ancestor.ancestor
16×
173
        }
174
}
175

176
// eval is the Lengauer-Tarjan EVAL function.
177
func (lt *lengauerTarjan) eval(v *ltNode) *ltNode {
16×
178
        if v.ancestor == nil {
32×
179
                return v
16×
180
        }
16×
181
        lt.compress(v)
16×
182
        return v.label
16×
183
}
184

185
// link is the Lengauer-Tarjan LINK procedure.
186
func (*lengauerTarjan) link(v, w *ltNode) {
16×
187
        w.ancestor = v
16×
188
}
16×
189

190
// DominatorTree is a flow graph dominator tree.
191
type DominatorTree struct {
192
        root        graph.Node
193
        dominatorOf map[int64]graph.Node
194
        dominatedBy map[int64][]graph.Node
195
}
196

197
// Root returns the root of the tree.
198
func (d DominatorTree) Root() graph.Node { return d.root }
!
199

200
// DominatorOf returns the immediate dominator of n.
201
func (d DominatorTree) DominatorOf(n graph.Node) graph.Node {
!
202
        return d.dominatorOf[n.ID()]
!
203
}
!
204

205
// DominatedBy returns a slice of all nodes immediately dominated by n.
206
// Elements of the slice are retained by the DominatorTree.
207
func (d DominatorTree) DominatedBy(n graph.Node) []graph.Node {
!
208
        return d.dominatedBy[n.ID()]
!
209
}
!
Troubleshooting · Open an Issue · Sales · Support · ENTERPRISE · CAREERS · STATUS
BLOG · TWITTER · Legal & Privacy · Supported CI Services · What's a CI service? · Automated Testing

© 2019 Coveralls, LLC