GCC Code Coverage Report

Directory: ./
File: src/connected-component.cc
Date: 2024-12-13 16:14:03
Exec Total Coverage
Lines: 97 97 100.0%
Branches: 74 114 64.9%
Line Branch Exec Source
1 //
2 // Copyright (c) 2014 CNRS
3 // Authors: Florent Lamiraux
4 //
5
6 // Redistribution and use in source and binary forms, with or without
7 // modification, are permitted provided that the following conditions are
8 // met:
9 //
10 // 1. Redistributions of source code must retain the above copyright
11 // notice, this list of conditions and the following disclaimer.
12 //
13 // 2. Redistributions in binary form must reproduce the above copyright
14 // notice, this list of conditions and the following disclaimer in the
15 // documentation and/or other materials provided with the distribution.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 // HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
28 // DAMAGE.
29
30 #include <algorithm>
31 #include <hpp/core/connected-component.hh>
32 #include <hpp/core/edge.hh>
33
34 namespace hpp {
35 namespace core {
36 // Mark connected components of a list as unexplored.
37 222 void ConnectedComponent::clean(RawPtrs_t& set) {
38
2/2
✓ Branch 3 taken 268 times.
✓ Branch 4 taken 222 times.
 490 for (RawPtrs_t::iterator it = set.begin(); it != set.end(); ++it) {
39 268 (*it)->explored_ = false;
40 }
41 222 }
42
43 17 void ConnectedComponent::merge(const ConnectedComponentPtr_t& other) {
44
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 17 times.
 17 assert(other);
45
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 17 times.
 17 assert(weak_.lock().get() == this);
46
47 // Tell other's nodes that they now belong to this connected component
48 17 for (NodeVector_t::iterator itNode = other->nodes_.begin();
49
2/2
✓ Branch 3 taken 39 times.
✓ Branch 4 taken 17 times.
 56 itNode != other->nodes_.end(); ++itNode) {
50
1/2
✓ Branch 3 taken 39 times.
✗ Branch 4 not taken.
 39 (*itNode)->connectedComponent(weak_.lock());
51 }
52 // Add other's nodes to this list.
53
1/2
✓ Branch 7 taken 17 times.
✗ Branch 8 not taken.
 17 nodes_.insert(nodes_.end(), other->nodes_.begin(), other->nodes_.end());
54
55 // Tell other's reachableTo's that other has been replaced by this
56 17 for (RawPtrs_t::iterator itcc = other->reachableTo_.begin();
57
2/2
✓ Branch 3 taken 18 times.
✓ Branch 4 taken 17 times.
 35 itcc != other->reachableTo_.end(); ++itcc) {
58
1/2
✓ Branch 3 taken 18 times.
✗ Branch 4 not taken.
 18 (*itcc)->reachableFrom_.erase(other.get());
59
1/2
✓ Branch 2 taken 18 times.
✗ Branch 3 not taken.
 18 (*itcc)->reachableFrom_.insert(this);
60 }
61
62 // Tell other's reachableFrom's that other has been replaced by this
63 17 for (RawPtrs_t::iterator itcc = other->reachableFrom_.begin();
64
2/2
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 17 times.
 20 itcc != other->reachableFrom_.end(); ++itcc) {
65
1/2
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
 3 (*itcc)->reachableTo_.erase(other.get());
66
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 (*itcc)->reachableTo_.insert(this);
67 }
68
69 17 RawPtrs_t tmp;
70
2/4
✓ Branch 2 taken 17 times.
✗ Branch 3 not taken.
✓ Branch 9 taken 17 times.
✗ Branch 10 not taken.
 51 std::set_union(reachableTo_.begin(), reachableTo_.end(),
71 34 other->reachableTo_.begin(), other->reachableTo_.end(),
72 std::inserter(tmp, tmp.begin()));
73
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 reachableTo_ = tmp;
74 17 tmp.clear();
75
1/2
✓ Branch 2 taken 17 times.
✗ Branch 3 not taken.
 17 reachableTo_.erase(other.get());
76
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 reachableTo_.erase(this);
77
2/4
✓ Branch 2 taken 17 times.
✗ Branch 3 not taken.
✓ Branch 9 taken 17 times.
✗ Branch 10 not taken.
 51 std::set_union(reachableFrom_.begin(), reachableFrom_.end(),
78 34 other->reachableFrom_.begin(), other->reachableFrom_.end(),
79 std::inserter(tmp, tmp.begin()));
80
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 reachableFrom_ = tmp;
81 17 tmp.clear();
82
1/2
✓ Branch 2 taken 17 times.
✗ Branch 3 not taken.
 17 reachableFrom_.erase(other.get());
83
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 reachableFrom_.erase(this);
84 17 }
85
86 174 bool ConnectedComponent::canReach(const ConnectedComponentPtr_t& cc) {
87 // Store visited connected components for further cleaning.
88 174 RawPtrs_t explored;
89
1/2
✓ Branch 1 taken 174 times.
✗ Branch 2 not taken.
 174 std::deque<RawPtr_t> queue;
90
1/2
✓ Branch 1 taken 174 times.
✗ Branch 2 not taken.
 174 queue.push_back(this);
91 174 explored_ = true;
92
1/2
✓ Branch 1 taken 174 times.
✗ Branch 2 not taken.
 174 explored.insert(this);
93
2/2
✓ Branch 1 taken 186 times.
✓ Branch 2 taken 65 times.
 251 while (!queue.empty()) {
94 186 RawPtr_t current = queue.front();
95 186 queue.pop_front();
96
2/2
✓ Branch 1 taken 109 times.
✓ Branch 2 taken 77 times.
 186 if (current == cc.get()) {
97
1/2
✓ Branch 1 taken 109 times.
✗ Branch 2 not taken.
 109 clean(explored);
98 109 return true;
99 }
100 77 for (RawPtrs_t::iterator itChild = current->reachableTo_.begin();
101
2/2
✓ Branch 3 taken 13 times.
✓ Branch 4 taken 77 times.
 90 itChild != current->reachableTo_.end(); ++itChild) {
102 13 RawPtr_t child = *itChild;
103
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 1 times.
 13 if (!child->explored_) {
104 12 child->explored_ = true;
105
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 explored.insert(child);
106
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 queue.push_back(child);
107 }
108 }
109 }
110
1/2
✓ Branch 1 taken 65 times.
✗ Branch 2 not taken.
 65 clean(explored);
111 65 return false;
112 174 }
113
114 34 bool ConnectedComponent::canReach(const ConnectedComponentPtr_t& cc,
115 RawPtrs_t& ccToThis) {
116 34 bool reachable = false;
117 // Store visited connected components
118 34 RawPtrs_t exploredForward;
119
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 std::deque<RawPtr_t> queue;
120
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 queue.push_back(this);
121 34 explored_ = true;
122
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 exploredForward.insert(this);
123
2/2
✓ Branch 1 taken 51 times.
✓ Branch 2 taken 34 times.
 85 while (!queue.empty()) {
124 51 RawPtr_t current = queue.front();
125 51 queue.pop_front();
126
2/2
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 37 times.
 51 if (current == cc.get()) {
127 14 reachable = true;
128
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 exploredForward.insert(current);
129 } else {
130 37 for (RawPtrs_t::iterator itChild = current->reachableTo_.begin();
131
2/2
✓ Branch 3 taken 18 times.
✓ Branch 4 taken 37 times.
 55 itChild != current->reachableTo_.end(); ++itChild) {
132 18 RawPtr_t child = *itChild;
133
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 1 times.
 18 if (!child->explored_) {
134 17 child->explored_ = true;
135
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 exploredForward.insert(child);
136
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 queue.push_back(child);
137 }
138 }
139 }
140 }
141 // Set visited connected components to unexplored
142
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 clean(exploredForward);
143
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 14 times.
 34 if (!reachable) return false;
144
145 // Store visited connected components
146 14 RawPtrs_t exploredBackward;
147
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 queue.push_back(cc.get());
148 14 cc->explored_ = true;
149
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 exploredBackward.insert(cc.get());
150
2/2
✓ Branch 1 taken 31 times.
✓ Branch 2 taken 14 times.
 45 while (!queue.empty()) {
151 31 RawPtr_t current = queue.front();
152 31 queue.pop_front();
153
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 17 times.
 31 if (current == this) {
154
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 exploredBackward.insert(current);
155 } else {
156 17 for (RawPtrs_t::iterator itChild = current->reachableFrom_.begin();
157
2/2
✓ Branch 3 taken 18 times.
✓ Branch 4 taken 17 times.
 35 itChild != current->reachableFrom_.end(); ++itChild) {
158 18 RawPtr_t child = *itChild;
159
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 1 times.
 18 if (!child->explored_) {
160 17 child->explored_ = true;
161
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 exploredBackward.insert(child);
162
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 queue.push_back(child);
163 }
164 }
165 }
166 }
167 // Set visited connected components to unexplored
168
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 clean(exploredBackward);
169
2/4
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
✓ Branch 9 taken 14 times.
✗ Branch 10 not taken.
 14 std::set_intersection(exploredForward.begin(), exploredForward.end(),
170 exploredBackward.begin(), exploredBackward.end(),
171 std::inserter(ccToThis, ccToThis.begin()));
172 14 return true;
173 34 }
174
175 int ConnectedComponent::static_id = 0;
176
177 } // namespace core
178 } // namespace hpp
179