| 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 <utility> | |||
| 18 | #include <vector> | |||
| 19 | ||||
| 20 | #include "Graphs/TreeSearch_impl.hpp" | |||
| 21 | #include "Graphs/Utils.hpp" | |||
| 22 | ||||
| 23 | /* A wrapper around the BFS and DFS implementation of boost graph. The hope is | |||
| 24 | * that this is less awkward (albeit less flexible) to use than the direct boost | |||
| 25 | * code. | |||
| 26 | * | |||
| 27 | * The helpers `run_bfs` and `run_dfs`, as well as `longest_simple_path` are | |||
| 28 | * provided (defined at the bottom) to be used in most situations. | |||
| 29 | * | |||
| 30 | * This file contains the public interface to be used, | |||
| 31 | * and the file `TreeSearch_impl.hpp` contains the implementation details. | |||
| 32 | * Note that these files are header-only as they rely all on templates. | |||
| 33 | * | |||
| 34 | * Examples (pseudo-code): | |||
| 35 | * > // get distances of each vertex from root as vector | |||
| 36 | * > auto dists = graphs::run_bfs(root, graph).get_dists(); | |||
| 37 | * > // get parent of each vertex of depth-first-search (DFS) | |||
| 38 | * > auto parents = graphs::run_dfs(root, graph).get_parents() | |||
| 39 | * > | |||
| 40 | * > // BFS and DFS require an integer vertex index. | |||
| 41 | * > // This exists by default when the underlying edge type is vecS. | |||
| 42 | * > // Otherwise, we can also pass a map-like Property Map that is used as | |||
| 43 | * vertex index > auto dfs = graphs::run_dfs(root, graph, vertex_index_map) | |||
| 44 | * | |||
| 45 | * `run_bfs` and `run_dfs` return instances of the BFS and DFS classes | |||
| 46 | * defined in the `TreeSearch_impl.hpp` file. These store the result of the tree | |||
| 47 | * search and allows the user to retrieve the relevant information as in the | |||
| 48 | * examples above. | |||
| 49 | */ | |||
| 50 | ||||
| 51 | namespace tket::graphs { | |||
| 52 | ||||
| 53 | /* Tree search: Breadth First Search (BFS) and Depth First Search (DFS) | |||
| 54 | * | |||
| 55 | * Use the following helper functions to run BFS or DFS on boost graphs. | |||
| 56 | * The returned instances are used to retrieve the computed results in the | |||
| 57 | * desired form. See class TreeSearchBase for the list of member functions | |||
| 58 | * available. | |||
| 59 | */ | |||
| 60 | template <typename Graph, typename PMap> | |||
| 61 | BFS<Graph, PMap> run_bfs(utils::vertex<Graph> root, Graph&& g, PMap& pmap) { | |||
| 62 | BFS<Graph, PMap> impl(root, std::forward<Graph>(g), pmap); | |||
| 63 | impl.run(); | |||
| 64 | return impl; | |||
| 65 | } | |||
| 66 | template <typename Graph> | |||
| 67 | 618 | BFS<Graph> run_bfs(utils::vertex<Graph> root, Graph&& g) { | ||
| 68 | 618 | BFS<Graph> impl(root, std::forward<Graph>(g)); | ||
| 69 |
1/2✓ Branch 1 taken 309 times.
✗ Branch 2 not taken.
|
618 | impl.run(); | |
| 70 | 618 | return impl; | ||
| 71 | } | |||
| 72 | template <typename Graph, typename PMap> | |||
| 73 | DFS<Graph, PMap> run_dfs(utils::vertex<Graph> root, Graph&& g, PMap& pmap) { | |||
| 74 | DFS<Graph, PMap> impl(root, std::forward<Graph>(g), pmap); | |||
| 75 | impl.run(); | |||
| 76 | return impl; | |||
| 77 | } | |||
| 78 | template <typename Graph> | |||
| 79 | 24 | DFS<Graph> run_dfs(utils::vertex<Graph> root, Graph&& g) { | ||
| 80 | 24 | DFS<Graph> impl(root, std::forward<Graph>(g)); | ||
| 81 |
1/2✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
|
24 | impl.run(); | |
| 82 | 24 | return impl; | ||
| 83 | } | |||
| 84 | template <typename Graph, typename Visitor> | |||
| 85 | DFS<Graph> run_dfs_with_visitor( | |||
| 86 | utils::vertex<Graph> root, Graph&& g, Visitor vis) { | |||
| 87 | DFS<Graph> impl(root, std::forward<Graph>(g)); | |||
| 88 | impl.run(vis); | |||
| 89 | return impl; | |||
| 90 | } | |||
| 91 | ||||
| 92 | /* Computes the longest simple path in a graph using DFS | |||
| 93 | * | |||
| 94 | * This is a naive implementation starting a new search from every | |||
| 95 | * possible vertex | |||
| 96 | */ | |||
| 97 | template <typename Graph> | |||
| 98 | 24 | std::vector<utils::vertex<Graph>> longest_simple_path( | ||
| 99 | const Graph& g, std::size_t cutoff_length = 0) { | |||
| 100 | 24 | std::vector<utils::vertex<const Graph>> longest; | ||
| 101 | 24 | auto root = boost::vertex(0, g); | ||
| 102 |
1/2✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
|
24 | auto dfs = run_dfs(root, g); | |
| 103 |
5/8✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 56 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 80 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 64 times.
✓ Branch 12 taken 16 times.
|
0/1? Decision couldn't be analyzed.
|
80 | for (auto [it, end] = boost::vertices(g); it != end; ++it) { |
| 104 |
1/2✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
|
64 | root = *it; | |
| 105 |
1/2✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
|
64 | dfs.change_root(root); | |
| 106 |
3/4✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 26 times.
✓ Branch 5 taken 38 times.
|
2/2✓ Decision 'true' taken 26 times.
✓ Decision 'false' taken 38 times.
|
64 | if (dfs.max_depth() + 1 > longest.size()) { |
| 107 |
1/2✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
|
26 | longest = dfs.longest_path(); | |
| 108 |
6/6✓ Branch 0 taken 9 times.
✓ Branch 1 taken 17 times.
✓ Branch 3 taken 8 times.
✓ Branch 4 taken 1 times.
✓ Branch 5 taken 8 times.
✓ Branch 6 taken 18 times.
|
2/2✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 18 times.
|
26 | if (cutoff_length > 0 && longest.size() >= cutoff_length) { |
| 109 | 8 | break; | ||
| 110 | } | |||
| 111 | } | |||
| 112 | } | |||
| 113 | 48 | return longest; | ||
| 114 | 24 | } | ||
| 115 | ||||
| 116 | } // namespace tket::graphs | |||
| 117 |