| 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 <optional> | |||
| 18 | #include <set> | |||
| 19 | #include <stdexcept> | |||
| 20 | #include <utility> | |||
| 21 | #include <vector> | |||
| 22 | ||||
| 23 | namespace tket::graphs { | |||
| 24 | ||||
| 25 | class NodeDoesNotExistError : public std::logic_error { | |||
| 26 | using std::logic_error::logic_error; | |||
| 27 | }; | |||
| 28 | ||||
| 29 | class EdgeDoesNotExistError : public std::logic_error { | |||
| 30 | using std::logic_error::logic_error; | |||
| 31 | }; | |||
| 32 | ||||
| 33 | /** | |||
| 34 | * Abstract class for representing graphs. | |||
| 35 | * | |||
| 36 | * @tparam T type of nodes in the graph | |||
| 37 | */ | |||
| 38 | template <typename T> | |||
| 39 | class AbstractGraph { | |||
| 40 | // TODO Add "requires std::totally_ordered<T>" (and implement spaceship for | |||
| 41 | // UnitID) when apple-clang supports it. | |||
| 42 | protected: | |||
| 43 | using Edge = std::pair<T, T>; | |||
| 44 | std::set<T> nodes_; | |||
| 45 | std::optional<unsigned> diameter_; | |||
| 46 | ||||
| 47 | public: | |||
| 48 | /** Construct an empty graph */ | |||
| 49 | ✗ | AbstractGraph() : nodes_() {} | ||
| 50 | ||||
| 51 | /** Construct from vector of nodes */ | |||
| 52 | 79 | explicit AbstractGraph(const std::vector<T> &nodes) | ||
| 53 | 79 | : nodes_({nodes.begin(), nodes.end()}) {} | ||
| 54 | ||||
| 55 | /** Check if an edge exists between two nodes */ | |||
| 56 | virtual bool edge_exists(const T &node1, const T &node2) const = 0; | |||
| 57 | ||||
| 58 | /** Check if an edge exists between two nodes */ | |||
| 59 | 11471 | bool bidirectional_edge_exists(const T &node1, const T &node2) const { | ||
| 60 |
4/4✓ Branch 1 taken 9433 times.
✓ Branch 2 taken 2038 times.
✓ Branch 4 taken 1996 times.
✓ Branch 5 taken 7437 times.
|
11471 | return (edge_exists(node1, node2) || edge_exists(node2, node1)); | |
| 61 | } | |||
| 62 | ||||
| 63 | /** Check if a node exists */ | |||
| 64 | ✗ | bool node_exists(const T &node) const { return nodes_.contains(node); } | ||
| 65 | ||||
| 66 | /** Reference to the underlying node set */ | |||
| 67 | ✗ | const std::set<T> &nodes() const { return nodes_; } | ||
| 68 | ||||
| 69 | /** All nodes as a vector */ | |||
| 70 | ✗ | std::vector<T> get_all_nodes_vec() const { | ||
| 71 | ✗ | return {nodes_.begin(), nodes_.end()}; | ||
| 72 | } | |||
| 73 | ||||
| 74 | /** Number of nodes */ | |||
| 75 | ✗ | unsigned n_nodes() const { return nodes_.size(); } | ||
| 76 | ||||
| 77 | /** All edges as a vector */ | |||
| 78 | virtual std::vector<Edge> get_all_edges_vec() const = 0; | |||
| 79 | ||||
| 80 | /** Graph distance between two nodes. */ | |||
| 81 | virtual unsigned get_distance(const T &node1, const T &node2) const = 0; | |||
| 82 | ||||
| 83 | /** Diameter of graph. */ | |||
| 84 | virtual unsigned get_diameter() = 0; | |||
| 85 | ||||
| 86 | ✗ | virtual ~AbstractGraph() {} | ||
| 87 | }; | |||
| 88 | ||||
| 89 | } // namespace tket::graphs | |||
| 90 |