library/_internal/graph/eulerian-walk.hpp

• View this file on GitHub
• Last update: 2025-03-03 00:33:48+09:00
• Include: #include "library/_internal/graph/eulerian-walk.hpp"

Depends on

• library/_internal/graph-base.hpp
• 無向グラフ (library/data-structure/graph.hpp)

Required by

• オイラー路 (library/graph/eulerian-walk.hpp)

Verified with

• tests/graph/eulerian-walk/libchecker-directed.test.cpp
• tests/graph/eulerian-walk/libchecker-undirected.test.cpp

Code

#pragma once

#include <cassert>
#include <deque>
#include <functional>
#include <queue>
#include <vector>
using namespace std;

#include "../../data-structure/graph.hpp"

namespace asalib {
  namespace _internal {
    namespace graph {
      template<bool is_directed>
      pair<vector<size_t>, vector<size_t>> eulerian_walk(const size_t& n, const edgelist_t& Edges, const size_t& start_v, const size_t& end_v) {
        // グラフを変換するパート
        vector<queue<size_t>> Graph(n);
        for (size_t i = 0; i < Edges.size(); ++i) {
          const auto& [u, v] = Edges[i];
          Graph[u].push(i);
          if constexpr (!is_directed) Graph[v].push(i);
        }
        vector<bool> used(Edges.size(), false);

        // 適当にパスを見つけるやつ (これはオイラー路が存在することが確定してるからできる技)
        auto find_path = [&](size_t from, size_t to, vector<size_t>& vs, vector<size_t>& eds) {
          size_t now = from;
          if (Graph[now].empty()) return false;
          do {
            assert(!Graph[now].empty());
            size_t e_idx = Graph[now].front();
            Graph[now].pop();
            if (used[e_idx]) continue;
            used[e_idx] = true;
            eds.push_back(e_idx);
            vs.push_back(now);
            const auto& [u, v] = Edges[e_idx];
            if (u == now) {
              now = v;
            }
            else {
              assert(now == v);
              now = u;
            }
          } while (now != to);
          vs.push_back(to);
          return true;
        };

        // 適当に start_v -> end_v のパスを作るパート
        vector<size_t> vs = {}, eds = {};
        find_path(start_v, end_v, vs, eds);
        assert(vs.size() == eds.size() + 1);
        constexpr size_t ign = -1;
        eds.push_back(ign);

        // 別の道があれば寄り道して辺を全部使うパート (閉路になるはず)
        vector<size_t> res_vs, res_eds;
        for (size_t i = 0; i < eds.size(); ++i) {
          stack<size_t> v, e;
          v.push(vs[i]), e.push(eds[i]);
          while (!v.empty()) {
            assert(v.size() == e.size());
            size_t now = v.top();
            size_t e_idx = e.top();
            vector<size_t> tmpvs, tmpeds;
            if (find_path(now, now, tmpvs, tmpeds)) {
              assert(tmpvs.front() == now && tmpvs.back() == now);
              assert(tmpvs.size() == tmpeds.size() + 1);
              tmpvs.pop_back();
              reverse(tmpvs.begin(), tmpvs.end());
              reverse(tmpeds.begin(), tmpeds.end());
              for (const auto& ver : tmpvs) v.push(ver);
              for (const auto& edg : tmpeds) e.push(edg);
            }
            else {
              v.pop(), e.pop();
              res_vs.push_back(now);
              res_eds.push_back(e_idx);
            }
          }
        }
        assert(res_eds.back() == ign);
        res_eds.pop_back();
        assert(res_vs.size() == res_eds.size() + 1);
        assert(res_eds.size() == Edges.size());

        return make_pair(res_vs, res_eds);
      }
    }  // namespace graph
  }  // namespace _internal
}  // namespace asalib

#line 2 "library/_internal/graph/eulerian-walk.hpp"

#include <cassert>
#include <deque>
#include <functional>
#include <queue>
#include <vector>
using namespace std;

#line 2 "library/data-structure/graph.hpp"

#line 4 "library/data-structure/graph.hpp"
#include <optional>
#line 6 "library/data-structure/graph.hpp"
using namespace std;

#line 2 "library/_internal/graph-base.hpp"

#include <concepts>
#include <type_traits>
using namespace std;

namespace asalib {
  namespace _internal {
    class graph_base {};
    class notweighted_graph_base: public graph_base {};
    class weighted_graph_base: public graph_base {};

    template<typename T>
    concept is_graph = is_base_of_v<graph_base, T>;

    template<typename T>
    concept notweighted_graph = is_base_of_v<notweighted_graph_base, T>;

    template<typename T>
    concept weighted_graph = is_base_of_v<weighted_graph_base, T>;

    using adjlist_t = vector<vector<pair<size_t, size_t>>>;
    using edgelist_t = vector<pair<size_t, size_t>>;
  }  // namespace _internal
}  // namespace asalib
#line 9 "library/data-structure/graph.hpp"

namespace asalib {
  namespace graph {
    class graph: public _internal::notweighted_graph_base {
      public:
      graph(): n_vertex(0), n_edge(0) {}
      explicit graph(size_t n_vertex): n_vertex(n_vertex), n_edge(0) {
        adj_list.reserve(n_vertex);
        adj_list.resize(n_vertex);
      }

      void add_edge(size_t v1, size_t v2) {
        assert(0 <= v1 && v1 < n_vertex);
        assert(0 <= v2 && v2 < n_vertex);
        adj_list[v1].push_back({ v2, n_edge });
        adj_list[v2].push_back({ v1, n_edge });
        edge_list.push_back({ v1, v2 });
        ++n_edge;
      }

      // (v1, v2)
      pair<size_t, size_t> get_edge(size_t edgeId) const {
        assert(0 <= edgeId && edgeId < n_edge);
        return edge_list[edgeId];
      }

      // (v2, edgeId)
      vector<pair<size_t, size_t>> get_adj(size_t vertex) const {
        assert(0 <= vertex && vertex < n_vertex);
        return adj_list[vertex];
      }

      // ---------- prototype ---------- //
      optional<pair<vector<size_t>, vector<size_t>>> cycle() const;
      bool is_connected() const;
      optional<pair<vector<size_t>, vector<size_t>>> eulerian_walk() const;

      private:
      size_t n_vertex, n_edge;
      asalib::_internal::adjlist_t adj_list;
      asalib::_internal::edgelist_t edge_list;
    };
  }  // namespace graph
}  // namespace asalib
#line 11 "library/_internal/graph/eulerian-walk.hpp"

namespace asalib {
  namespace _internal {
    namespace graph {
      template<bool is_directed>
      pair<vector<size_t>, vector<size_t>> eulerian_walk(const size_t& n, const edgelist_t& Edges, const size_t& start_v, const size_t& end_v) {
        // グラフを変換するパート
        vector<queue<size_t>> Graph(n);
        for (size_t i = 0; i < Edges.size(); ++i) {
          const auto& [u, v] = Edges[i];
          Graph[u].push(i);
          if constexpr (!is_directed) Graph[v].push(i);
        }
        vector<bool> used(Edges.size(), false);

        // 適当にパスを見つけるやつ (これはオイラー路が存在することが確定してるからできる技)
        auto find_path = [&](size_t from, size_t to, vector<size_t>& vs, vector<size_t>& eds) {
          size_t now = from;
          if (Graph[now].empty()) return false;
          do {
            assert(!Graph[now].empty());
            size_t e_idx = Graph[now].front();
            Graph[now].pop();
            if (used[e_idx]) continue;
            used[e_idx] = true;
            eds.push_back(e_idx);
            vs.push_back(now);
            const auto& [u, v] = Edges[e_idx];
            if (u == now) {
              now = v;
            }
            else {
              assert(now == v);
              now = u;
            }
          } while (now != to);
          vs.push_back(to);
          return true;
        };

        // 適当に start_v -> end_v のパスを作るパート
        vector<size_t> vs = {}, eds = {};
        find_path(start_v, end_v, vs, eds);
        assert(vs.size() == eds.size() + 1);
        constexpr size_t ign = -1;
        eds.push_back(ign);

        // 別の道があれば寄り道して辺を全部使うパート (閉路になるはず)
        vector<size_t> res_vs, res_eds;
        for (size_t i = 0; i < eds.size(); ++i) {
          stack<size_t> v, e;
          v.push(vs[i]), e.push(eds[i]);
          while (!v.empty()) {
            assert(v.size() == e.size());
            size_t now = v.top();
            size_t e_idx = e.top();
            vector<size_t> tmpvs, tmpeds;
            if (find_path(now, now, tmpvs, tmpeds)) {
              assert(tmpvs.front() == now && tmpvs.back() == now);
              assert(tmpvs.size() == tmpeds.size() + 1);
              tmpvs.pop_back();
              reverse(tmpvs.begin(), tmpvs.end());
              reverse(tmpeds.begin(), tmpeds.end());
              for (const auto& ver : tmpvs) v.push(ver);
              for (const auto& edg : tmpeds) e.push(edg);
            }
            else {
              v.pop(), e.pop();
              res_vs.push_back(now);
              res_eds.push_back(e_idx);
            }
          }
        }
        assert(res_eds.back() == ign);
        res_eds.pop_back();
        assert(res_vs.size() == res_eds.size() + 1);
        assert(res_eds.size() == Edges.size());

        return make_pair(res_vs, res_eds);
      }
    }  // namespace graph
  }  // namespace _internal
}  // namespace asalib

Back to top page