| 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 <vector> | |||
| 18 | ||||
| 19 | #include "AbstractGraph.hpp" | |||
| 20 | ||||
| 21 | namespace tket::graphs { | |||
| 22 | ||||
| 23 | template <typename T> | |||
| 24 | class CompleteGraph : public AbstractGraph<T> { | |||
| 25 | public: | |||
| 26 | using AbstractGraph<T>::node_exists; | |||
| 27 | using AbstractGraph<T>::edge_exists; | |||
| 28 | using AbstractGraph<T>::get_all_nodes_vec; | |||
| 29 | using AbstractGraph<T>::get_all_edges_vec; | |||
| 30 | using AbstractGraph<T>::n_nodes; | |||
| 31 | using typename AbstractGraph<T>::Edge; | |||
| 32 | ||||
| 33 | /** Construct an empty graph. */ | |||
| 34 | CompleteGraph() {} | |||
| 35 | ||||
| 36 | /** All edges as a vector. */ | |||
| 37 | std::vector<Edge> get_all_edges_vec() const override { | |||
| 38 | std::vector<Edge> edges; | |||
| 39 | std::vector<T> nodes = get_all_nodes_vec(); | |||
| 40 | unsigned n = nodes.size(); | |||
| 41 | for (unsigned i = 0; i < n; i++) { | |||
| 42 | for (unsigned j = i + 1; j < n; j++) { | |||
| 43 | edges.push_back({nodes[i], nodes[j]}); | |||
| 44 | } | |||
| 45 | } | |||
| 46 | return edges; | |||
| 47 | } | |||
| 48 | ||||
| 49 | /** Add a new node to the graph. */ | |||
| 50 | 4 | void add_node(const T& node) { nodes_.insert(node); } | ||
| 51 | ||||
| 52 | /** Test whether two nodes are connected. */ | |||
| 53 | bool edge_exists(const T& node1, const T& node2) const override { | |||
| 54 | if (!node_exists(node1) || !node_exists(node2)) { | |||
| 55 | throw NodeDoesNotExistError( | |||
| 56 | "The UIDs passed to CompleteGraph::edge_exists must exist."); | |||
| 57 | } | |||
| 58 | return true; | |||
| 59 | } | |||
| 60 | ||||
| 61 | unsigned get_distance(const T& node1, const T& node2) const override { | |||
| 62 | if (!node_exists(node1) || !node_exists(node2)) { | |||
| 63 | throw NodeDoesNotExistError( | |||
| 64 | "The UIDs passed to CompleteGraph::edge_exists must exist."); | |||
| 65 | } | |||
| 66 | if (node1 == node2) return 0; | |||
| 67 | return 1; | |||
| 68 | } | |||
| 69 | ||||
| 70 | unsigned get_diameter() override { | |||
| 71 | switch (n_nodes()) { | |||
| 72 | case 0: | |||
| 73 | throw std::logic_error("Graph is empty."); | |||
| 74 | case 1: | |||
| 75 | return 0; | |||
| 76 | default: | |||
| 77 | return 1; | |||
| 78 | } | |||
| 79 | } | |||
| 80 | ||||
| 81 | bool operator==(const CompleteGraph<T>& other) const { | |||
| 82 | return nodes_ == other.nodes_; | |||
| 83 | } | |||
| 84 | ||||
| 85 | protected: | |||
| 86 | using AbstractGraph<T>::nodes_; | |||
| 87 | }; | |||
| 88 | ||||
| 89 | } // namespace tket::graphs | |||
| 90 |