GCC Code Coverage Report

Directory: ./
File: Graphs/AdjacencyData.cpp
Date: 2022-10-15 05:10:18
Exec Total Coverage
Lines: 68 68 100.0%
Functions: 10 10 100.0%
Branches: 52 74 70.3%
Decisions: 30 30 100.0%
Line Branch Decision Exec Source
1 // Copyright 2019-2022 Cambridge Quantum Computing
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "AdjacencyData.hpp"
16
17 #include <algorithm>
18 #include <set>
19 #include <sstream>
20 #include <stdexcept>
21 #include <tkassert/Assert.hpp>
22
23 using std::exception;
24 using std::map;
25 using std::runtime_error;
26 using std::set;
27 using std::string;
28 using std::stringstream;
29 using std::vector;
30
31 namespace tket {
32 namespace graphs {
33
34 29310 string AdjacencyData::to_string() const {
35 29310 map<std::size_t, set<std::size_t>> data_to_display;
36
2/2
✓ Branch 1 taken 836104 times.
✓ Branch 2 taken 29310 times.
2/2
✓ Decision 'true' taken 836104 times.
✓ Decision 'false' taken 29310 times.
 865414 for (std::size_t i = 0; i < m_cleaned_data.size(); ++i) {
37 836104 const auto& neighbours = m_cleaned_data[i];
38
1/2
✓ Branch 1 taken 836104 times.
✗ Branch 2 not taken.
 836104 auto& neighbours_to_display = data_to_display[i];
39
2/2
✓ Branch 5 taken 779416 times.
✓ Branch 6 taken 836104 times.
2/2
✓ Decision 'true' taken 779416 times.
✓ Decision 'false' taken 836104 times.
 1615520 for (std::size_t v : neighbours) {
40
2/2
✓ Branch 0 taken 389708 times.
✓ Branch 1 taken 389708 times.
2/2
✓ Decision 'true' taken 389708 times.
✓ Decision 'false' taken 389708 times.
 779416 if (i <= v) {
41
1/2
✓ Branch 1 taken 389708 times.
✗ Branch 2 not taken.
 389708 neighbours_to_display.insert(v);
42 }
43 }
44
2/2
✓ Branch 1 taken 656966 times.
✓ Branch 2 taken 179138 times.
2/2
✓ Decision 'true' taken 656966 times.
✓ Decision 'false' taken 179138 times.
 836104 if (neighbours_to_display.empty()) {
45 // Don't display it after all
46
1/2
✓ Branch 1 taken 656966 times.
✗ Branch 2 not taken.
 656966 data_to_display.erase(i);
47 }
48 }
49
50
1/2
✓ Branch 1 taken 29310 times.
✗ Branch 2 not taken.
 29310 stringstream ss;
51
2/4
✓ Branch 1 taken 29310 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 29310 times.
✗ Branch 6 not taken.
 29310 ss << "\nThere are " << m_cleaned_data.size()
52
1/2
✓ Branch 1 taken 29310 times.
✗ Branch 2 not taken.
 29310 << " vertices in total.\nVertex neighbours:\n{";
53
54
2/2
✓ Branch 5 taken 179138 times.
✓ Branch 6 taken 29310 times.
2/2
✓ Decision 'true' taken 179138 times.
✓ Decision 'false' taken 29310 times.
 208448 for (const auto& entry_to_display : data_to_display) {
55
3/6
✓ Branch 1 taken 179138 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 179138 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 179138 times.
✗ Branch 8 not taken.
 179138 ss << "\n { " << entry_to_display.first << ", { ";
56
2/2
✓ Branch 5 taken 389708 times.
✓ Branch 6 taken 179138 times.
2/2
✓ Decision 'true' taken 389708 times.
✓ Decision 'false' taken 179138 times.
 568846 for (auto v : entry_to_display.second) {
57
2/4
✓ Branch 1 taken 389708 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 389708 times.
✗ Branch 5 not taken.
 389708 ss << v << ", ";
58 }
59
1/2
✓ Branch 1 taken 179138 times.
✗ Branch 2 not taken.
 179138 ss << "} },";
60 }
61
1/2
✓ Branch 1 taken 29310 times.
✗ Branch 2 not taken.
 29310 ss << "\n}\n";
62
1/2
✓ Branch 1 taken 29310 times.
✗ Branch 2 not taken.
 58620 return ss.str();
63 29310 }
64
65 3650282 const set<std::size_t>& AdjacencyData::get_neighbours(
66 std::size_t vertex) const {
67 // GCOVR_EXCL_START
68 TKET_ASSERT(
69 vertex < m_cleaned_data.size() ||
70 AssertMessage()
71 << "AdjacencyData: get_neighbours called with invalid vertex "
72 << vertex << "; there are only " << m_cleaned_data.size()
73 << " vertices");
74 // GCOVR_EXCL_STOP
75 3650282 return m_cleaned_data[vertex];
76 }
77
78 47260 std::size_t AdjacencyData::get_number_of_vertices() const {
79 47260 return m_cleaned_data.size();
80 }
81
82 20 std::size_t AdjacencyData::get_number_of_edges() const {
83 // Each edge i-j is counted twice, i->j and j->i, except for loops.
84 20 std::size_t edges = 0;
85 20 std::size_t loops = 0;
86
87
2/2
✓ Branch 1 taken 3564 times.
✓ Branch 2 taken 20 times.
2/2
✓ Decision 'true' taken 3564 times.
✓ Decision 'false' taken 20 times.
 3584 for (std::size_t ii = 0; ii < m_cleaned_data.size(); ++ii) {
88 3564 edges += m_cleaned_data[ii].size();
89
1/2
✓ Branch 2 taken 3564 times.
✗ Branch 3 not taken.
 3564 loops += m_cleaned_data[ii].count(ii);
90 }
91 20 return loops + (edges - loops) / 2;
92 }
93
94 149121 bool AdjacencyData::add_edge(std::size_t i, std::size_t j) {
95 149121 const bool exists = edge_exists(i, j);
96
2/2
✓ Branch 0 taken 33983 times.
✓ Branch 1 taken 115138 times.
2/2
✓ Decision 'true' taken 33983 times.
✓ Decision 'false' taken 115138 times.
 149121 if (exists) {
97 33983 return false;
98 }
99 115138 m_cleaned_data[i].insert(j);
100 115138 m_cleaned_data[j].insert(i);
101 115138 return true;
102 }
103
104 3029610 bool AdjacencyData::edge_exists(std::size_t i, std::size_t j) const {
105 // GCOVR_EXCL_START
106 TKET_ASSERT(
107 (i < m_cleaned_data.size() && j < m_cleaned_data.size()) ||
108 AssertMessage() << "edge_exists called with vertices " << i << ", " << j
109 << ", but there are only " << m_cleaned_data.size()
110 << " vertices");
111 // GCOVR_EXCL_STOP
112 3029610 return m_cleaned_data[i].count(j) != 0;
113 }
114
115 2702 void AdjacencyData::clear(std::size_t number_of_vertices) {
116 2702 m_cleaned_data.resize(number_of_vertices);
117
2/2
✓ Branch 5 taken 538462 times.
✓ Branch 6 taken 2702 times.
2/2
✓ Decision 'true' taken 538462 times.
✓ Decision 'false' taken 2702 times.
 541164 for (auto& entry : m_cleaned_data) {
118 538462 entry.clear();
119 }
120 2702 }
121
122 2483 AdjacencyData::AdjacencyData(std::size_t number_of_vertices) {
123
1/2
✓ Branch 1 taken 2483 times.
✗ Branch 2 not taken.
 2483 m_cleaned_data.resize(number_of_vertices);
124 2483 }
125
126 4 AdjacencyData::AdjacencyData(
127 const map<std::size_t, vector<std::size_t>>& raw_data,
128 4 std::size_t number_of_vertices) {
129
2/2
✓ Branch 5 taken 21 times.
✓ Branch 6 taken 4 times.
2/2
✓ Decision 'true' taken 21 times.
✓ Decision 'false' taken 4 times.
 25 for (const auto& entry : raw_data) {
130 21 number_of_vertices = std::max(number_of_vertices, entry.first + 1);
131
2/2
✓ Branch 4 taken 64 times.
✓ Branch 5 taken 21 times.
2/2
✓ Decision 'true' taken 64 times.
✓ Decision 'false' taken 21 times.
 85 for (std::size_t neighbour : entry.second) {
132 64 number_of_vertices = std::max(number_of_vertices, neighbour + 1);
133 }
134 }
135
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 m_cleaned_data.resize(number_of_vertices);
136
2/2
✓ Branch 5 taken 21 times.
✓ Branch 6 taken 4 times.
2/2
✓ Decision 'true' taken 21 times.
✓ Decision 'false' taken 4 times.
 25 for (const auto& entry : raw_data) {
137
2/2
✓ Branch 5 taken 64 times.
✓ Branch 6 taken 21 times.
2/2
✓ Decision 'true' taken 64 times.
✓ Decision 'false' taken 21 times.
 85 for (std::size_t neighbour : entry.second) {
138
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 add_edge(entry.first, neighbour);
139 }
140 }
141 4 }
142
143 2480 AdjacencyData::AdjacencyData(
144 2480 const vector<vector<std::size_t>>& raw_data, bool allow_loops) {
145
1/2
✓ Branch 2 taken 2480 times.
✗ Branch 3 not taken.
 2480 m_cleaned_data.resize(raw_data.size());
146
147
2/2
✓ Branch 1 taken 76350 times.
✓ Branch 2 taken 2480 times.
2/2
✓ Decision 'true' taken 76350 times.
✓ Decision 'false' taken 2480 times.
 78830 for (std::size_t i = 0; i < m_cleaned_data.size(); ++i) {
148
2/2
✓ Branch 6 taken 274035 times.
✓ Branch 7 taken 76350 times.
2/2
✓ Decision 'true' taken 274035 times.
✓ Decision 'false' taken 76350 times.
 350385 for (std::size_t j : raw_data[i]) {
149 // GCOVR_EXCL_START
150 TKET_ASSERT(
151 i != j || allow_loops ||
152 AssertMessage() << "Vertex " << i << " out of "
153 << m_cleaned_data.size() << " has a loop.");
154 TKET_ASSERT(
155 j < m_cleaned_data.size() ||
156 AssertMessage() << "Vertex " << i << " has illegal neighbour vertex "
157 << j << ", the size is " << m_cleaned_data.size());
158 // GCOVR_EXCL_STOP
159
1/2
✓ Branch 2 taken 274035 times.
✗ Branch 3 not taken.
 274035 m_cleaned_data[i].insert(j);
160
1/2
✓ Branch 2 taken 274035 times.
✗ Branch 3 not taken.
 274035 m_cleaned_data[j].insert(i);
161 }
162 }
163 2480 }
164
165 } // namespace graphs
166 } // namespace tket
167