道 (path) の検出
(include/emthrm/graph/detect_path.hpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Include: #include "emthrm/graph/detect_path.hpp"

歩道 (walk) の検出

時間計算量

$O(\lvert V \rvert + \lvert E \rvert)$

仕様

道の検出

名前	戻り値
template <typename CostType> std::vector<Edge<CostType>> detect_path(const std::vector<std::vector<Edge<CostType>>>& graph, const int s, const int t);	有向グラフ $\mathrm{graph}$ における始点 $s$、終点 $t$ の道。ただし存在しないときは空配列を返す。

有向閉路の検出

名前	戻り値
template <typename CostType> std::vector<Edge<CostType>> detect_directed_cycle(const std::vector<std::vector<Edge<CostType>>>& graph);	有向グラフ $\mathrm{graph}$ における閉路。ただし存在しないときは空配列を返す。

参考文献

有向閉路の検出

• https://qiita.com/drken/items/a803d4fc4a727e02f7ba#4-6-%E3%82%B5%E3%82%A4%E3%82%AF%E3%83%AB%E6%A4%9C%E5%87%BA

TODO

• 無向閉路の検出
  • https://judge.yosupo.jp/problem/cycle_detection_undirected
• 閉路の列挙
  • https://github.com/spaghetti-source/algorithm/blob/master/graph/cycle_enumeration.cc

Submissons

• 道の検出
• 有向閉路の検出

Depends on

• 辺 (include/emthrm/graph/edge.hpp)

Verified with

• グラフ/道の検出 (test/graph/detect_path.test.cpp)

Code

#ifndef EMTHRM_GRAPH_DETECT_PATH_HPP_
#define EMTHRM_GRAPH_DETECT_PATH_HPP_

#include <vector>

#include "emthrm/graph/edge.hpp"

namespace emthrm {

template <typename CostType>
std::vector<Edge<CostType>> detect_path(
    const std::vector<std::vector<Edge<CostType>>>& graph,
    const int s, const int t) {
  std::vector<bool> is_visited(graph.size(), false);
  std::vector<Edge<CostType>> path;
  const auto dfs = [&graph, t, &is_visited, &path](auto dfs, const int ver)
      -> bool {
    if (ver == t) return true;
    is_visited[ver] = true;
    for (const Edge<CostType>& e : graph[ver]) {
      if (!is_visited[e.dst]) {
        path.emplace_back(e);
        if (dfs(dfs, e.dst)) return true;
        path.pop_back();
      }
    }
    return false;
  };
  dfs(dfs, s);
  return path;
}

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_DETECT_PATH_HPP_

#line 1 "include/emthrm/graph/detect_path.hpp"



#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 7 "include/emthrm/graph/detect_path.hpp"

namespace emthrm {

template <typename CostType>
std::vector<Edge<CostType>> detect_path(
    const std::vector<std::vector<Edge<CostType>>>& graph,
    const int s, const int t) {
  std::vector<bool> is_visited(graph.size(), false);
  std::vector<Edge<CostType>> path;
  const auto dfs = [&graph, t, &is_visited, &path](auto dfs, const int ver)
      -> bool {
    if (ver == t) return true;
    is_visited[ver] = true;
    for (const Edge<CostType>& e : graph[ver]) {
      if (!is_visited[e.dst]) {
        path.emplace_back(e);
        if (dfs(dfs, e.dst)) return true;
        path.pop_back();
      }
    }
    return false;
  };
  dfs(dfs, s);
  return path;
}

}  // namespace emthrm

Back to top page