GCC Code Coverage Report

Directory: ./
File: ZX/ZXDSubdiagram.cpp
Date: 2022-10-15 05:10:18
Warnings: 5 unchecked decisions!
Exec Total Coverage
Lines: 108 123 87.8%
Functions: 4 5 80.0%
Branches: 153 292 52.4%
Decisions: 43 62 69.4%
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 "Utils/GraphHeaders.hpp"
16 #include "ZX/ZXDiagram.hpp"
17
18 namespace tket {
19
20 namespace zx {
21
22 ✗ ZXDiagram::Subdiagram::Subdiagram() : boundary_(), verts_() {}
23
24 27 ZXDiagram::Subdiagram::Subdiagram(
25 27 const std::vector<std::pair<Wire, WireEnd>>& cut, const ZXVertSeqSet& verts)
26
1/2
✓ Branch 2 taken 27 times.
✗ Branch 3 not taken.
 27 : boundary_(cut), verts_(verts) {}
27
28 4 void ZXDiagram::Subdiagram::check_validity(const ZXDiagram& diag) const {
29 4 std::set<std::pair<Wire, WireEnd>> boundary_lookup;
30
2/2
✓ Branch 5 taken 12 times.
✓ Branch 6 taken 4 times.
2/2
✓ Decision 'true' taken 12 times.
✓ Decision 'false' taken 4 times.
 16 for (const std::pair<Wire, WireEnd>& w : boundary_) {
31
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 auto inserted = boundary_lookup.insert(w);
32
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 12 times.
 12 if (!inserted.second)
33 ✗ throw ZXError(
34 ✗ "Malformed ZX Subdiagram: Wire appears multiple times in boundary");
35
4/8
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 12 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 12 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✓ Branch 11 taken 12 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 12 times.
 12 if (verts_.find(diag.vertex_at_end(w.first, w.second)) == verts_.end())
36 ✗ throw ZXError(
37 "Malformed ZX Subdiagram: Vertex adjacent to boundary is not in "
38 ✗ "vertex set");
39 }
40
5/8
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 6 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 10 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 6 times.
✓ Branch 12 taken 4 times.
0/1
? Decision couldn't be analyzed.
 10 for (const ZXVert& v : verts_) {
41
3/6
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 6 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 6 times.
 6 if (is_boundary_type(diag.get_zxtype(v)))
42 ✗ throw ZXError("Malformed ZX Subdiagram: Contains a boundary vertex");
43
3/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 14 times.
✓ Branch 9 taken 6 times.
0/1
? Decision couldn't be analyzed.
 20 for (const Wire& w : diag.adj_wires(v)) {
44
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 ZXVert n = diag.other_end(w, v);
45
4/6
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 14 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 8 times.
✓ Branch 8 taken 6 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 6 times.
 14 if (verts_.find(n) == verts_.end()) {
46
2/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 8 times.
✗ Branch 6 not taken.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 8 times.
 8 if (boundary_lookup.find({w, diag.end_of(w, v)}) ==
47
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
 16 boundary_lookup.end())
48 ✗ throw ZXError("Malformed ZX Subdiagram: subdiagram is not closed");
49 } else {
50
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 6 times.
 6 if ((boundary_lookup.find({w, WireEnd::Source}) ==
51 6 boundary_lookup.end()) ^
52
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 (boundary_lookup.find({w, WireEnd::Target}) ==
53
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
 12 boundary_lookup.end()))
54 ✗ throw ZXError(
55 "Malformed ZX Subdiagram: wire between two interior vertices "
56 ✗ "contains one boundary");
57 }
58 6 }
59 }
60 4 }
61
62 3 ZXDiagram ZXDiagram::Subdiagram::to_diagram(const ZXDiagram& orig) const {
63
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 ZXDiagram diag;
64 3 std::map<ZXVert, ZXVert> vert_iso;
65 3 std::map<std::pair<Wire, WireEnd>, ZXVert> bound_iso;
66
2/2
✓ Branch 4 taken 8 times.
✓ Branch 5 taken 3 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 3 times.
 11 for (const std::pair<Wire, WireEnd>& bw : boundary_) {
67
2/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
 8 ZXVert bv = diag.add_vertex(ZXType::Open, orig.get_qtype(bw.first));
68
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 diag.boundary.push_back(bv);
69
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 bound_iso.insert({bw, bv});
70 }
71
5/8
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 8 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 5 times.
✓ Branch 12 taken 3 times.
0/1
? Decision couldn't be analyzed.
 8 for (const ZXVert& ov : verts_) {
72
2/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
 5 ZXVert v = diag.add_vertex(orig.get_vertex_ZXGen_ptr(ov));
73
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 5 vert_iso.insert({ov, v});
74
3/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 11 times.
✓ Branch 9 taken 5 times.
0/1
? Decision couldn't be analyzed.
 16 for (const Wire& w : orig.adj_wires(ov)) {
75 11 bool internal = true;
76
3/4
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 5 times.
2/2
✓ Decision 'true' taken 6 times.
✓ Decision 'false' taken 5 times.
 11 if (orig.source(w) == ov) {
77
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 auto found_bound = bound_iso.find({w, WireEnd::Source});
78
2/2
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 2 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 2 times.
 6 if (found_bound != bound_iso.end()) {
79 4 internal = false;
80
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 WireProperties wp = orig.get_wire_info(w);
81 8 diag.add_wire(
82
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 v, found_bound->second, ZXWireType::Basic, wp.qtype,
83 wp.source_port, std::nullopt);
84 }
85 }
86
3/4
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 5 times.
2/2
✓ Decision 'true' taken 6 times.
✓ Decision 'false' taken 5 times.
 11 if (orig.target(w) == ov) {
87
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 auto found_bound = bound_iso.find({w, WireEnd::Target});
88
2/2
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 2 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 2 times.
 6 if (found_bound != bound_iso.end()) {
89 4 internal = false;
90
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 WireProperties wp = orig.get_wire_info(w);
91 8 diag.add_wire(
92
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 found_bound->second, v, ZXWireType::Basic, wp.qtype, std::nullopt,
93 wp.target_port);
94 }
95 }
96
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 7 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 7 times.
 11 if (internal) {
97
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 ZXVert other = orig.other_end(w, ov);
98
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 auto found_other = vert_iso.find(other);
99
2/2
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 2 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 2 times.
 4 if (found_other != vert_iso.end()) {
100
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 WireProperties wp = orig.get_wire_info(w);
101
3/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 1 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 1 times.
 2 if (orig.source(w) == ov)
102
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 diag.add_wire(v, found_other->second, wp);
103 else
104
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 diag.add_wire(found_other->second, v, wp);
105 }
106 }
107 5 }
108 }
109 6 return diag;
110 3 }
111
112 27 void ZXDiagram::substitute(
113 const ZXDiagram& to_insert, const Subdiagram& to_replace) {
114 27 unsigned n_bounds = to_insert.boundary.size();
115
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 27 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 27 times.
 27 if (n_bounds != to_replace.boundary_.size())
116 ✗ throw ZXError(
117 "ZXDiagram substitution error: boundary size of replacement does not "
118 ✗ "fit size of subdiagram");
119
120 std::pair<std::map<ZXVert, ZXVert>, std::map<Wire, Wire>> iso =
121
1/2
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
 27 copy_graph(to_insert, false);
122
123 27 std::map<Wire, ZXVert> loops;
124
2/2
✓ Branch 0 taken 65 times.
✓ Branch 1 taken 27 times.
2/2
✓ Decision 'true' taken 65 times.
✓ Decision 'false' taken 27 times.
 92 for (unsigned i = 0; i < n_bounds; ++i) {
125
1/2
✓ Branch 1 taken 65 times.
✗ Branch 2 not taken.
 65 std::pair<Wire, WireEnd> w = to_replace.boundary_.at(i);
126
1/2
✓ Branch 1 taken 65 times.
✗ Branch 2 not taken.
 65 WireProperties wp = get_wire_info(w.first);
127
2/4
✓ Branch 1 taken 65 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 65 times.
✗ Branch 5 not taken.
 65 ZXVert new_b = iso.first.at(to_insert.boundary.at(i));
128
2/4
✓ Branch 1 taken 65 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 65 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 65 times.
 65 if (wp.qtype != get_qtype(new_b))
129 ✗ throw ZXError(
130 ✗ "ZXDiagram substitution error: QuantumType mismatch at a boundary");
131 ZXVert to_connect =
132
4/6
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 31 times.
✓ Branch 3 taken 34 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 31 times.
✗ Branch 7 not taken.
 65 (w.second == WireEnd::Source) ? target(w.first) : source(w.first);
133
4/6
✓ Branch 2 taken 65 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 65 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 8 times.
✓ Branch 8 taken 57 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 57 times.
 65 if (to_replace.verts_.find(to_connect) != to_replace.verts_.end()) {
134 // Connect two boundaries together
135
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 auto inserted = loops.insert({w.first, new_b});
136
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 4 times.
 8 if (!inserted.second) {
137 // Already seen the other end, so actually connect the loop
138 4 ZXVert other_b = inserted.first->second;
139
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 4 Wire wb = adj_wires(new_b).at(0);
140
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 ZXVert adj = other_end(wb, new_b);
141 std::optional<unsigned> adj_port =
142
5/8
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 3 times.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 3 times.
✗ Branch 10 not taken.
 4 (source(wb) == adj) ? source_port(wb) : target_port(wb);
143
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 3 times.
 4 if (adj == other_b) {
144 // Creates a wire-loop, resolve to a scalar
145 bool hadamard =
146
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 (wp.type == ZXWireType::H) ^ (get_wire_type(wb) == ZXWireType::H);
147
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1 times.
 1 if (hadamard)
148 ✗ multiply_scalar(0.);
149
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
1/2
✓ Decision 'true' taken 1 times.
✗ Decision 'false' not taken.
 1 else if (wp.qtype == QuantumType::Quantum)
150
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 multiply_scalar(4.);
151 else
152 ✗ multiply_scalar(2.);
153 } else {
154 // Connect the adjacent vertices
155
2/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
 3 Wire wob = adj_wires(other_b).at(0);
156
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 ZXVert other_adj = other_end(wob, other_b);
157 std::optional<unsigned> other_adj_port =
158
5/8
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 2 times.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 2 times.
✗ Branch 10 not taken.
 3 (source(wob) == other_adj) ? source_port(wob) : target_port(wob);
159 6 bool hadamard = (wp.type == ZXWireType::H) ^
160
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 (get_wire_type(wb) == ZXWireType::H) ^
161
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 (get_wire_type(wob) == ZXWireType::H);
162
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
 3 add_wire(
163 adj, other_adj, hadamard ? ZXWireType::H : ZXWireType::Basic,
164 wp.qtype, adj_port, other_adj_port);
165 }
166
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 remove_vertex(new_b);
167
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 remove_vertex(other_b);
168 }
169 } else {
170
2/4
✓ Branch 1 taken 57 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 57 times.
✗ Branch 5 not taken.
 57 Wire wb = adj_wires(new_b).at(0);
171
3/4
✓ Branch 1 taken 57 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 7 times.
✓ Branch 4 taken 50 times.
2/2
✓ Decision 'true' taken 7 times.
✓ Decision 'false' taken 50 times.
 57 if (get_wire_type(wb) == ZXWireType::H) {
172
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 6 times.
✓ Decision 'false' taken 1 times.
 7 if (wp.type == ZXWireType::Basic)
173 6 wp.type = ZXWireType::H;
174 else
175 1 wp.type = ZXWireType::Basic;
176 }
177
1/2
✓ Branch 1 taken 57 times.
✗ Branch 2 not taken.
 57 ZXVert adj = other_end(wb, new_b);
178 std::optional<unsigned> adj_port =
179
5/8
✓ Branch 1 taken 57 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 20 times.
✓ Branch 4 taken 37 times.
✓ Branch 6 taken 20 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 37 times.
✗ Branch 10 not taken.
 57 (source(wb) == adj) ? source_port(wb) : target_port(wb);
180
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 27 times.
2/2
✓ Decision 'true' taken 30 times.
✓ Decision 'false' taken 27 times.
 57 if (w.second == WireEnd::Source) {
181 30 wp.source_port = adj_port;
182
2/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 30 times.
✗ Branch 5 not taken.
 30 add_wire(adj, target(w.first), wp);
183 } else {
184 27 wp.target_port = adj_port;
185
2/4
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 27 times.
✗ Branch 5 not taken.
 27 add_wire(source(w.first), adj, wp);
186 }
187
1/2
✓ Branch 1 taken 57 times.
✗ Branch 2 not taken.
 57 remove_vertex(new_b);
188 }
189 }
190
5/8
✓ Branch 3 taken 29 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 29 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 56 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 29 times.
✓ Branch 12 taken 27 times.
0/1
? Decision couldn't be analyzed.
 56 for (const ZXVert& v : to_replace.verts_) {
191
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 remove_vertex(v);
192 }
193 27 }
194
195 } // namespace zx
196
197 } // namespace tket
198