library/_internal/graph-base.hpp

• View this file on GitHub
• Last update: 2025-08-17 00:21:01+09:00
• Include: #include "library/_internal/graph-base.hpp"

Required by

• 連結判定 (library/graph/connection.hpp)
• サイクル検出 (library/graph/cycle.hpp)
• オイラー路 (library/graph/eulerian-walk.hpp)
• SCC (Strongly Connected Components) (library/graph/scc.hpp)

Verified with

• tests/graph/cycle/libchecker-directed.test.cpp
• tests/graph/cycle/libchecker-undirected.test.cpp
• tests/graph/eulerian-walk/libchecker-directed.test.cpp
• tests/graph/eulerian-walk/libchecker-undirected.test.cpp
• tests/graph/scc/abc256-e.test.cpp
• tests/graph/scc/abc296-e.test.cpp
• tests/graph/scc/libchecker.test.cpp

Code

#pragma once

#include <concepts>
#include <cstddef>
#include <ranges>
#include <utility>
using namespace std;

namespace asalib::_internal {
  // vector<vector<int>> とかの隣接リストを表す型
  template<class T>
  concept adjacency_list = requires(T t) {
    { t.size() } -> convertible_to<size_t>;
    { t[0] } -> ranges::range;
    { *ranges::begin(t[0]) } -> convertible_to<size_t>;
  };

  // 辺のリストを表す型
  // 重み付きも考慮し pair<int, int> と tuple<int, int, int> の両方を許容
  template<class T>
  concept edge_list = requires(T t) {
    { t.size() } -> convertible_to<size_t>;
    { get<0>(t[0]) } -> convertible_to<size_t>;
    { get<1>(t[0]) } -> convertible_to<size_t>;
  };
}  // namespace asalib::_internal

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

#include <concepts>
#include <cstddef>
#include <ranges>
#include <utility>
using namespace std;

namespace asalib::_internal {
  // vector<vector<int>> とかの隣接リストを表す型
  template<class T>
  concept adjacency_list = requires(T t) {
    { t.size() } -> convertible_to<size_t>;
    { t[0] } -> ranges::range;
    { *ranges::begin(t[0]) } -> convertible_to<size_t>;
  };

  // 辺のリストを表す型
  // 重み付きも考慮し pair<int, int> と tuple<int, int, int> の両方を許容
  template<class T>
  concept edge_list = requires(T t) {
    { t.size() } -> convertible_to<size_t>;
    { get<0>(t[0]) } -> convertible_to<size_t>;
    { get<1>(t[0]) } -> convertible_to<size_t>;
  };
}  // namespace asalib::_internal

Back to top page