オイラー路 (Eulerian trail) 有向グラフ版
(include/emthrm/graph/eulerian_trail_in_directed_graph.hpp)

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

オイラー路 (Eulerian trail)

グラフのすべての辺を一度だけ通る路である。

準オイラーグラフ (semi-Eulerian graph)

閉路でないオイラー路が存在するグラフである。

連結グラフ $G$ が準オイラーグラフである必要十分条件は

• $G$ が無向グラフのとき、奇数次数の頂点がちょうど $2$ 個存在することであり、
• $G$ が有向グラフのとき、相対出次数 $1$、相対入次数 $1$ の頂点が一つずつ存在し、他の頂点の相対次数が $0$ であることである。

オイラーグラフ (Eulerian graph)

オイラー閉路 (Euler circuit) が存在するグラフである。

連結グラフ $G$ がオイラーグラフである必要十分条件は

• $G$ が無向グラフのとき、任意の頂点の次数が偶数であることであり、
• $G$ が有向グラフのとき、任意の頂点の相対次数が $0$ であることである。

時間計算量

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

仕様

Hierholzer’s algorithm 有向グラフ版

名前	戻り値
template <typename CostType> std::vector<Edge<CostType>> eulerian_trail_in_directed_graph(std::vector<std::vector<Edge<CostType>>> graph, int s = -1);	有向グラフ $\mathrm{graph}$ における始点 $s$ のオイラー路。ただし存在しないときは空配列を返す。

Hierholzer’s algorithm 無向グラフ版

struct EulerianTrailInUndirectedGraph;

メンバ変数

名前	説明
std::vector<int> trail	オイラー路。ただし存在しないときは空配列となる。

メンバ関数

名前	効果・戻り値
explicit EulerianTrailInUndirectedGraph(const int n);	頂点数 $N$ の無向グラフのオブジェクトを構築する。
void add_edge(const int u, const int v);	辺 $(u, v)$ を加える。
bool build(int s = -1);	始点 $s$ のオイラー路を構築できたか。

参考文献

• Carl Hierholzer: Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren, *Mathematische Annalen *, Vol. 6, pp. 30–32 (1873). https://doi.org/10.1007/BF01442866
• https://kokiymgch.hatenablog.com/entry/2017/12/07/193238

オイラー路 有向グラフ版

• http://www.prefield.com/algorithm/graph/directed_euler_path.html

オイラー路 無向グラフ版

• https://github.com/spaghetti-source/algorithm/blob/2c70d7af4d132513fa699a5de5b2aaf21aaf7890/graph/eulerian_path_undirected.cc

Submissons

• オイラー路 有向グラフ版
• オイラー路 無向グラフ版

Depends on

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

Verified with

• グラフ/オイラー路 有向グラフ版 (test/graph/eulerian_trail_in_directed_graph.test.cpp)

Code

#ifndef EMTHRM_GRAPH_EULERIAN_TRAIL_IN_DIRECTED_GRAPH_HPP_
#define EMTHRM_GRAPH_EULERIAN_TRAIL_IN_DIRECTED_GRAPH_HPP_

#include <algorithm>
#include <iterator>
#include <ranges>
#include <utility>
#include <vector>

#include "emthrm/graph/edge.hpp"

namespace emthrm {

template <typename CostType>
std::vector<Edge<CostType>> eulerian_trail_in_directed_graph(
    std::vector<std::vector<Edge<CostType>>> graph, int s = -1) {
  const int n = graph.size();
  int edge_num = 0;
  std::vector<int> deg(n, 0);
  for (int i = 0; i < n; ++i) {
    edge_num += graph[i].size();
    deg[i] += graph[i].size();
    for (const int e : graph[i] | std::views::transform(&Edge<CostType>::dst)) {
      --deg[e];
    }
  }
  if (edge_num == 0) [[unlikely]] return {};
  const int not0 = n - std::count(deg.begin(), deg.end(), 0);
  if (not0 == 0) {
    if (s == -1) {
      s = std::distance(
          graph.begin(),
          std::find_if_not(
              graph.begin(), graph.end(),
              [](const std::vector<Edge<CostType>>& edges) -> bool {
                return edges.empty();
              }));
    }
  } else if (not0 == 2) {
    bool t_exists = false;
    for (int i = 0; i < n; ++i) {
      if (deg[i] == 0) continue;
      if (deg[i] == 1) {
        if (s == -1) s = i;
        if (s != i) return {};
      } else if (deg[i] == -1) {
        if (t_exists) return {};
        t_exists = true;
      } else {
        return {};
      }
    }
  } else {
    return {};
  }
  std::vector<Edge<CostType>> res;
  const auto dfs = [&graph, &res](auto dfs, const int ver) -> void {
    while (!graph[ver].empty()) {
      const Edge<CostType> e = graph[ver].back();
      graph[ver].pop_back();
      dfs(dfs, e.dst);
      res.emplace_back(e);
    }
  };
  dfs(dfs, s);
  if (std::cmp_equal(res.size(), edge_num)) {
    std::reverse(res.begin(), res.end());
    return res;
  }
  return {};
}

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EULERIAN_TRAIL_IN_DIRECTED_GRAPH_HPP_

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



#include <algorithm>
#include <iterator>
#include <ranges>
#include <utility>
#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 11 "include/emthrm/graph/eulerian_trail_in_directed_graph.hpp"

namespace emthrm {

template <typename CostType>
std::vector<Edge<CostType>> eulerian_trail_in_directed_graph(
    std::vector<std::vector<Edge<CostType>>> graph, int s = -1) {
  const int n = graph.size();
  int edge_num = 0;
  std::vector<int> deg(n, 0);
  for (int i = 0; i < n; ++i) {
    edge_num += graph[i].size();
    deg[i] += graph[i].size();
    for (const int e : graph[i] | std::views::transform(&Edge<CostType>::dst)) {
      --deg[e];
    }
  }
  if (edge_num == 0) [[unlikely]] return {};
  const int not0 = n - std::count(deg.begin(), deg.end(), 0);
  if (not0 == 0) {
    if (s == -1) {
      s = std::distance(
          graph.begin(),
          std::find_if_not(
              graph.begin(), graph.end(),
              [](const std::vector<Edge<CostType>>& edges) -> bool {
                return edges.empty();
              }));
    }
  } else if (not0 == 2) {
    bool t_exists = false;
    for (int i = 0; i < n; ++i) {
      if (deg[i] == 0) continue;
      if (deg[i] == 1) {
        if (s == -1) s = i;
        if (s != i) return {};
      } else if (deg[i] == -1) {
        if (t_exists) return {};
        t_exists = true;
      } else {
        return {};
      }
    }
  } else {
    return {};
  }
  std::vector<Edge<CostType>> res;
  const auto dfs = [&graph, &res](auto dfs, const int ver) -> void {
    while (!graph[ver].empty()) {
      const Edge<CostType> e = graph[ver].back();
      graph[ver].pop_back();
      dfs(dfs, e.dst);
      res.emplace_back(e);
    }
  };
  dfs(dfs, s);
  if (std::cmp_equal(res.size(), edge_num)) {
    std::reverse(res.begin(), res.end());
    return res;
  }
  return {};
}

}  // namespace emthrm

Back to top page