2249

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

Build # 2249

Build Type

Pull #556

travis-ci

Committed by

web-flow

Commit Message

lapack/testlapack: clean up Dorg2lTest

Pull Request Pull Request #556: lapack/testlapack: clean up and use isOrthogonal helper

Run Details

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

// Copyright ©2017 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 "gonum.org/v1/gonum/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) DominatorTree {
        // The algorithm used here is essentially the Lengauer and Tarjan
        // algorithm described in https://doi.org/10.1145%2F357062.357071

        lt := lengauerTarjan{
                indexOf: make(map[int64]int),
        }

        // step 1.
        lt.dfs(g, root)

        for i := len(lt.nodes) - 1; i > 0; i-- {
                w := lt.nodes[i]

                // step 2.
                for _, v := range w.pred {
                        u := lt.eval(v)

                        if u.semi < w.semi {
                                w.semi = u.semi
                        }
                }

                lt.nodes[w.semi].bucket[w] = struct{}{}
                lt.link(w.parent, w)

                // step 3.
                for v := range w.parent.bucket {
                        delete(w.parent.bucket, v)

                        u := lt.eval(v)
                        if u.semi < v.semi {
                                v.dom = u
                        } else {
                                v.dom = w.parent
                        }
                }
        }

        // step 4.
        for _, w := range lt.nodes[1:] {
                if w.dom.node.ID() != lt.nodes[w.semi].node.ID() {
                        w.dom = w.dom.dom
                }
        }

        // Construct the public-facing dominator tree structure.
        dominatorOf := make(map[int64]graph.Node)
        dominatedBy := make(map[int64][]graph.Node)
        for _, w := range lt.nodes[1:] {
                dominatorOf[w.node.ID()] = w.dom.node
                did := w.dom.node.ID()
                dominatedBy[did] = append(dominatedBy[did], w.node)
        }
        return DominatorTree{root: root, dominatorOf: dominatorOf, dominatedBy: dominatedBy}
}

// lengauerTarjan holds global state of the Lengauer-Tarjan algorithm.
// This is a mapping between nodes and the postordering of the nodes.
type lengauerTarjan struct {
        // nodes is the nodes traversed during the
        // Lengauer-Tarjan depth-first-search.
        nodes []*ltNode
        // indexOf contains a mapping between
        // the id-dense representation of the
        // graph and the potentially id-sparse
        // nodes held in nodes.
        //
        // This corresponds to the vertex
        // number of the node in the Lengauer-
        // Tarjan algorithm.
        indexOf map[int64]int
}

// ltNode is a graph node with accounting for the Lengauer-Tarjan
// algorithm.
//
// For the purposes of documentation the ltNode is given the name w.
type ltNode struct {
        node graph.Node

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

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

        // semi is a number defined as follows:
        // (i)  After w is numbered but before its semidominator
        //      is computed, semi is the number of w.
        // (ii) After the semidominator of w is computed, semi
        //      is the number of the semidominator of w.
        semi int

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

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

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

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

// dfs is the Lengauer-Tarjan DFS procedure.
func (lt *lengauerTarjan) dfs(g graph.Directed, v graph.Node) {
        i := len(lt.nodes)
        lt.indexOf[v.ID()] = i
        ltv := &ltNode{
                node:   v,
                semi:   i,
                bucket: make(map[*ltNode]struct{}),
        }
        ltv.label = ltv
        lt.nodes = append(lt.nodes, ltv)

        for _, w := range g.From(v.ID()) {
                wid := w.ID()

                idx, ok := lt.indexOf[wid]
                if !ok {
                        lt.dfs(g, w)

                        // We place this below the recursive call
                        // in contrast to the original algorithm
                        // since w needs to be initialised, and
                        // this happens in the child call to dfs.
                        idx, ok = lt.indexOf[wid]
                        if !ok {
                                panic("path: unintialized node")
                        }
                        lt.nodes[idx].parent = ltv
                }
                ltw := lt.nodes[idx]
                ltw.pred = append(ltw.pred, ltv)
        }
}

// compress is the Lengauer-Tarjan COMPRESS procedure.
func (lt *lengauerTarjan) compress(v *ltNode) {
        if v.ancestor.ancestor != nil {
                lt.compress(v.ancestor)
                if v.ancestor.label.semi < v.label.semi {
                        v.label = v.ancestor.label
                }
                v.ancestor = v.ancestor.ancestor
        }
}

// eval is the Lengauer-Tarjan EVAL function.
func (lt *lengauerTarjan) eval(v *ltNode) *ltNode {
        if v.ancestor == nil {
                return v
        }
        lt.compress(v)
        return v.label
}

// link is the Lengauer-Tarjan LINK procedure.
func (*lengauerTarjan) link(v, w *ltNode) {
        w.ancestor = 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()]
}

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	}	!

gonum / gonum / 2249

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

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