GCC Code Coverage Report

Directory: ./
File: Graphs/LargeCliquesResult.cpp
Date: 2022-10-15 05:10:18
Exec Total Coverage
Lines: 34 35 97.1%
Functions: 1 1 100.0%
Branches: 31 42 73.8%
Decisions: 21 22 95.5%
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 "LargeCliquesResult.hpp"
16
17 #include "AdjacencyData.hpp"
18
19 using std::set;
20 using std::size_t;
21 using std::vector;
22
23 namespace tket {
24 namespace graphs {
25
26 303427 LargeCliquesResult::LargeCliquesResult(
27 const AdjacencyData& adjacency_data,
28 303427 const set<size_t>& vertices_in_component, size_t internal_size_limit) {
29 // ...and, before swapping, everything in here will have size one greater than
30 // "result".
31 303427 vector<set<size_t>> extended_result;
32
33 // At each stage, every set will have the same size, containing a clique of
34 // that size.
35
1/2
✓ Branch 2 taken 303427 times.
✗ Branch 3 not taken.
 303427 cliques.reserve(vertices_in_component.size());
36
2/2
✓ Branch 4 taken 486531 times.
✓ Branch 5 taken 303427 times.
2/2
✓ Decision 'true' taken 486531 times.
✓ Decision 'false' taken 303427 times.
 789958 for (size_t i : vertices_in_component) {
37
2/4
✓ Branch 2 taken 486531 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 486531 times.
✗ Branch 6 not taken.
 486531 cliques.emplace_back(set{i});
38 }
39 303427 bool hit_internal_limit = false;
40
41 // A little trick: the vertex indices can always be stored in order: v1 < v2 <
42 // ... Therefore, within each vertex set, if we only allow adding vertices
43 // with LARGER index than the largest already stored, we will automatically
44 // discard duplicates.
45
1/2
✓ Branch 1 taken 338026 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 338026 times.
✗ Decision 'false' not taken.
 338026 for (size_t counter = 0; counter <= vertices_in_component.size(); ++counter) {
46 // Extend the existing results.
47
2/2
✓ Branch 5 taken 998755 times.
✓ Branch 6 taken 337714 times.
2/2
✓ Decision 'true' taken 998755 times.
✓ Decision 'false' taken 337714 times.
 1336469 for (const auto& clique : cliques) {
48 // Guaranteed to be nonempty.
49 998755 const size_t largest_index = *clique.crbegin();
50
51
2/2
✓ Branch 1 taken 312 times.
✓ Branch 2 taken 998443 times.
2/2
✓ Decision 'true' taken 312 times.
✓ Decision 'false' taken 998443 times.
 998755 if (extended_result.size() >= internal_size_limit) {
52 312 hit_internal_limit = true;
53 312 break;
54 }
55 // We only have to check the neighbours of ONE vertex to form a larger
56 // clique.
57
1/2
✓ Branch 1 taken 998443 times.
✗ Branch 2 not taken.
 998443 const auto& neighbours = adjacency_data.get_neighbours(largest_index);
58
2/2
✓ Branch 5 taken 3634800 times.
✓ Branch 6 taken 998131 times.
2/2
✓ Decision 'true' taken 3634800 times.
✓ Decision 'false' taken 998131 times.
 4632931 for (size_t new_v : neighbours) {
59
2/2
✓ Branch 0 taken 2591538 times.
✓ Branch 1 taken 1043262 times.
2/2
✓ Decision 'true' taken 2591538 times.
✓ Decision 'false' taken 1043262 times.
 3634800 if (new_v <= largest_index) {
60 2591538 continue;
61 }
62 // We have a new vertex; does it adjoin EVERY existing vertex?
63 1043262 bool joins_every_vertex = true;
64
2/2
✓ Branch 5 taken 1535516 times.
✓ Branch 6 taken 524435 times.
2/2
✓ Decision 'true' taken 1535516 times.
✓ Decision 'false' taken 524435 times.
 2059951 for (size_t existing_v : clique) {
65
4/6
✓ Branch 1 taken 1535516 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1535516 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 518827 times.
✓ Branch 7 taken 1016689 times.
2/2
✓ Decision 'true' taken 518827 times.
✓ Decision 'false' taken 1016689 times.
 1535516 if (adjacency_data.get_neighbours(existing_v).count(new_v) == 0) {
66 518827 joins_every_vertex = false;
67 518827 break;
68 }
69 }
70
2/2
✓ Branch 0 taken 524435 times.
✓ Branch 1 taken 518827 times.
2/2
✓ Decision 'true' taken 524435 times.
✓ Decision 'false' taken 518827 times.
 1043262 if (joins_every_vertex) {
71
1/2
✓ Branch 1 taken 524435 times.
✗ Branch 2 not taken.
 524435 extended_result.emplace_back(clique);
72
1/2
✓ Branch 2 taken 524435 times.
✗ Branch 3 not taken.
 524435 extended_result.back().insert(new_v);
73
2/2
✓ Branch 1 taken 312 times.
✓ Branch 2 taken 524123 times.
2/2
✓ Decision 'true' taken 312 times.
✓ Decision 'false' taken 524123 times.
 524435 if (extended_result.size() >= internal_size_limit) {
74 312 hit_internal_limit = true;
75 312 break;
76 }
77 }
78 }
79 }
80
2/2
✓ Branch 1 taken 303427 times.
✓ Branch 2 taken 34599 times.
2/2
✓ Decision 'true' taken 303427 times.
✓ Decision 'false' taken 34599 times.
 338026 if (extended_result.empty()) {
81 // No extensions
82 303427 cliques_are_definitely_max_size = !hit_internal_limit;
83 303427 return;
84 }
85
1/2
✓ Branch 1 taken 34599 times.
✗ Branch 2 not taken.
 34599 cliques = extended_result;
86 // TODO: improve memory reallocation etc. by reusing rather than clearing
87 // (or, could be sneaky and do this within a single vector, jiggle with
88 // indices).
89 34599 extended_result.clear();
90 }
91 ✗ cliques_are_definitely_max_size = false;
92
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 303427 times.
 303427 }
93
94 } // namespace graphs
95 } // namespace tket
96