GCC Code Coverage Report

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				#pragma once
16
17				#include "Circuit/Circuit.hpp"
18
19				namespace tket {
20
21				typedef std::pair<Edge, Edge> edge_pair_t;
22
23				// CycleCom stores minimum command information required for FrameRandomisation
24				struct CycleCom {
25				OpType type;
26				std::vector<unsigned> indices;
27				Vertex address;
28
29				bool operator==(const CycleCom& other) const {
30				return this->type == other.type && this->indices == other.indices;
31				}
32				};
33
34				// Cycle stores minimum subcircuit information requried for FrameRandomisation
35				class Cycle {
36				public:
37			372	Cycle() {}
38			✗	Cycle(
39				const std::vector<edge_pair_t>& _boundary_edges,
40				const std::vector<CycleCom>& _coms)
41			✗	: boundary_edges_(_boundary_edges), coms_(_coms) {}
42
43				// Returns size of boundary_edges_
44				unsigned size() const;
45
46				// For edge_pair_t ep in boundary_edges_, if ep.first == source_edge,
47				// ep.second = replacement_edge
48				void update_boundary(const Edge& source_edge, const Edge& replacement_edge);
49
50				// Adds coms_ from new_cycle to end of this->coms_
51				// Extends this->boundary_edges_ with new_cycles.boundary_edges_
52				void merge(Cycle& new_cycle);
53
54				// if CycleCom.indices has unsigned equal to key in new_indices, change to
55				// value
56				void update_coms_indices(const std::map<unsigned, unsigned>& new_indices);
57
58				// Cycle has noop vertices wired into edges in _boundary_edges for purpose of
59				// Frame Randomisation This method these vertices in frame_vertices
60				void add_vertex_pair(const std::pair<Vertex, Vertex>& verts);
61
62				// Returns frame_vertices
63				std::vector<std::pair<Vertex, Vertex>> get_frame() const;
64
65				bool operator==(const Cycle& other) const {
66				return this->size() == other.size() && this->coms_ == other.coms_;
67				}
68
69				std::vector<edge_pair_t> boundary_edges_;
70				std::vector<CycleCom> coms_;
71
72				private:
73				std::vector<std::pair<Vertex, Vertex>> frame_vertices;
74				};
75
76				// CycleHistory stores information used to find minimal number of boundaries
77				struct CycleHistory {
78				// Every time a new cycle is made it's assigned a key of type unsigned
79				// The size of key is used to track the causal ordering of cycles
80				unsigned key;
81				// history.size() == key always
82				// Tracks which UnitID were in which Cycle
83				std::vector<std::vector<UnitID>> history;
84				// Map from UnitID to key, where key maps in key_to_cycle to "active" Cycle
85				std::map<UnitID, unsigned> uid_to_key;
86				// Map from key to cycle, where a key n refers to the nth cycle made
87				std::map<unsigned, Cycle> key_to_cycle;
88				};
89
90				class CycleFinder {
91				public:
92			19	CycleFinder(const Circuit& _circ, const OpTypeSet& _cycle_types)
93			19	: circ(_circ), cycle_types_(_cycle_types){};
94
95				// Cycles are sub-circuits of circ where every gate has OpType in cycle_types_
96				// get_cycles() returns the minimum number of cycles such that every
97				// cycle_types_ gate in circ is in one cycle
98				std::vector<Cycle> get_cycles();
99
100				private:
101				// Circuit cycles are found in
102				const Circuit& circ;
103				// OpType cycle gates have
104				const OpTypeSet cycle_types_;
105
106				// CycleFinder uses SliceIterator to find get circ gates in cycle_types_
107				// In Edges to a new slice are checked for equality with the last boundary out
108				// edge stored for their UnitID If equal a cycle may be extended, if not equal
109				std::map<Edge, UnitID> cycle_out_edges;
110
111				// Stores data structures for tracking created Cycles and associated UnitID's
112				CycleHistory bt;
113
114				// Given a new CutFrontier object, creates new cycles from interior vertices
115				// and merges them with previous cycles where possible
116				void extend_cycles(const CutFrontier& cut);
117
118				// Makes a new Cycle object from given dag information
119				// Return type used to identify whether cycle should be merged with previous
120				// cycles
121				std::pair<unsigned, std::set<unsigned>> make_cycle(
122				const Vertex& v, const EdgeVec& out_edges, const CutFrontier& cut);
123
124				// Uses CycleHistory to merge Cycle attributed to new_key with Cycles
125				// attributed to old_keys Cycles are merged in to Cycle with smallest key
126				void merge_cycles(unsigned new_key, std::set<unsigned>& old_keys);
127
128				// Updates cycle_out_edges with new Edge
129				// UnitID should not be new, so error thrown if not found
130				void update_cycle_out_edges(const UnitID& uid, const Edge& e);
131
132				// Getter for UnitID from unit_frontier_t in Cut
133				UnitID unitid_from_unit_frontier(
134				const std::shared_ptr<unit_frontier_t>& u_frontier, const Edge& e) const;
135
136				// if unsigned in erase_from is <= to_erase, removes from erase_from
137				void erase_keys(
138				const unsigned& to_erase, std::set<unsigned>& erase_from) const;
139
140				// removes unsigned from old_keys that have cycles that can't merge with
141				// new_key adds new_key to old_keys
142				void order_keys(unsigned& new_key, std::set<unsigned>& old_keys) const;
143				};
144				} // namespace tket
145