#include "Graph/Shortest-Path/bfs.hpp"
#pragma once #include <cassert> #include <functional> #include <queue> #include <utility> #include <vector> #include "../../Util/at.hpp" #include "../../Util/int-infinity.hpp" /** * @brief bfs() (幅優先探索による単一始点最短経路, 次元拡張に対応) * * @param dist: * start からの距離を格納する配列。 * 要素数は頂点数以上でなければならない。-1やINFなど、距離として正当でない値でfillされている必要がある。 * 多次元配列でもOK。 * * @param start: * 頂点を表すdistの添字。 * distが一次元配列なら整数型, * distが二次元配列ならstd::pair<integer, integer> または std::tuple<integer, integer> または std::array<integer, 2>, * distが三次元配列ならstd::tuple<integer, integer, integer> または std::array<integer, 3>。 * start = {i, j, k} のとき dist[i][j][k] でアクセスする。 * * @param enumerateNextVertex: * fn(from: Vertex, fn(to: Vertex) => void) => void * 第一引数にVertex, 第二引数に関数をとる関数。 * この関数が第一引数の頂点fromから次の頂点の遷移先を列挙し、第二引数に渡すことで bfs() に遷移処理を委譲する。 */ template <class DistArray, class Vertex, class NextVertexEnumerator> DistArray bfs(DistArray&& dist, Vertex start, NextVertexEnumerator enumerateNextVertex) { using arumakan::at; assert(!dist.empty()); assert(at(dist, start) == -1 || at(dist, start) >= INF); std::queue<Vertex> que({start}); const auto yetReachedMarker = at(dist, start); at(dist, start) = 0; while (!que.empty()) { const Vertex v = std::move(que.front()); que.pop(); const auto curDist = at(dist, v); enumerateNextVertex(v, [&](Vertex nxt) { if (at(dist, nxt) == yetReachedMarker) { at(dist, nxt) = curDist + 1; que.push(nxt); } }); } return dist; }
#line 2 "Graph/Shortest-Path/bfs.hpp" #include <cassert> #include <functional> #include <queue> #include <utility> #include <vector> #line 2 "Util/at.hpp" #include <tuple> #line 4 "Util/at.hpp" #include <type_traits> /** * @brief at() () */ namespace arumakan { //! at(a, i) returns a[i] template <class Array, class Integer, std::enable_if_t<std::is_integral<Integer>::value, std::nullptr_t> = nullptr> inline auto at(Array&& a, Integer i) -> decltype(a[0])& { return a[i]; } //! at(a, Tuple{i}) returns a[i] template <class Array, class Tuple, std::enable_if_t<std::tuple_size<Tuple>::value == 1, std::nullptr_t> = nullptr> inline auto at(Array&& a, Tuple index) -> decltype(a[0])& { return a[std::get<0>(index)]; } //! at(mat, Tuple{y, x}) returns mat[y][x] template <class Matrix, class Tuple, std::enable_if_t<std::tuple_size<Tuple>::value == 2, std::nullptr_t> = nullptr> inline auto at(Matrix&& mat, Tuple index) -> decltype(mat[0][0])& { return mat[std::get<0>(index)][std::get<1>(index)]; } //! at(cube, Tuple{z, y, x}) returns cube[z][y][x] template <class Cube, class Tuple, std::enable_if_t<std::tuple_size<Tuple>::value == 3, std::nullptr_t> = nullptr> inline auto at(Cube&& cube, Tuple index) -> decltype(cube[0][0][0])& { return cube[std::get<0>(index)][std::get<1>(index)][std::get<2>(index)]; } } // namespace arumakan #line 2 "Util/int-infinity.hpp" #include <cstdint> /** * @brief int-infinity (整数のデカイ値) * 2倍してもオーバーフローしない & memset()にも使える (需要ある?) */ constexpr int32_t INF = 0x3f3f3f3f; constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL; #line 10 "Graph/Shortest-Path/bfs.hpp" /** * @brief bfs() (幅優先探索による単一始点最短経路, 次元拡張に対応) * * @param dist: * start からの距離を格納する配列。 * 要素数は頂点数以上でなければならない。-1やINFなど、距離として正当でない値でfillされている必要がある。 * 多次元配列でもOK。 * * @param start: * 頂点を表すdistの添字。 * distが一次元配列なら整数型, * distが二次元配列ならstd::pair<integer, integer> または std::tuple<integer, integer> または std::array<integer, 2>, * distが三次元配列ならstd::tuple<integer, integer, integer> または std::array<integer, 3>。 * start = {i, j, k} のとき dist[i][j][k] でアクセスする。 * * @param enumerateNextVertex: * fn(from: Vertex, fn(to: Vertex) => void) => void * 第一引数にVertex, 第二引数に関数をとる関数。 * この関数が第一引数の頂点fromから次の頂点の遷移先を列挙し、第二引数に渡すことで bfs() に遷移処理を委譲する。 */ template <class DistArray, class Vertex, class NextVertexEnumerator> DistArray bfs(DistArray&& dist, Vertex start, NextVertexEnumerator enumerateNextVertex) { using arumakan::at; assert(!dist.empty()); assert(at(dist, start) == -1 || at(dist, start) >= INF); std::queue<Vertex> que({start}); const auto yetReachedMarker = at(dist, start); at(dist, start) = 0; while (!que.empty()) { const Vertex v = std::move(que.front()); que.pop(); const auto curDist = at(dist, v); enumerateNextVertex(v, [&](Vertex nxt) { if (at(dist, nxt) == yetReachedMarker) { at(dist, nxt) = curDist + 1; que.push(nxt); } }); } return dist; }