グラフ (隣接リスト形式)
(cpp/graph/graph_list.hpp)

• View this file on GitHub
• Last update: 2024-11-03 09:29:45+09:00
• Include: #include "cpp/graph/graph_list.hpp"

隣接リスト。
最短距離と Dijkstra Tree のうちの一つをもつ

グラフアルゴリズム：

• Bellman-Ford
• Dijkstra
• lowlink
• prim
• Topological Sort
• Warshall-Floyd

コンストラクタ

ListGraph<Cost = ll, E = Edge<Cost>> graph()

$n$ 頂点、結合がない状態で初期化する

add_node

void graph.add_node()

頂点を $1$ つ追加する

計算量

• ならし $ O(1) $

add_edge

void graph.add_edge(int from, int to, Args... args)

頂点 $from → to$ の有向辺を追加する
args は Edge のコンストラクタに渡る

計算量

• ならし $ O(1) $

add_bidirectional_edge

void graph.add_bidirectional_edge(int from, int to, Args... args)

頂点 $from → to$ と $to → from$ の有向辺を追加する
args は Edge のコンストラクタに渡る

計算量

• ならし $ O(1) $

operator[]

vector<E> graph.&operator[](int i)

頂点 $i$ の隣接リストを返す

reset_shortest

void graph.reset_shortest()

最短距離のキャッシュをクリアする。
add_edge か add_node で発動する。

計算量

• キャッシュがある場合 $ O(size) $

get_dist

Cost graph.get_dist(int from, int to)
vector<Cost> graph.get_dist(int from)

キャッシュから最短距離を返す

get_shortest_path

vector<int> graph.get_shortest_path(int from, int to)

キャッシュから最短パスを求める

定数

Cost ListGraph<Cost, E>::UNREACHABLE
Cost ListGraph<Cost, E>::NEGATIVE_CYCLE

• UNREACHABLE : 最短距離において到達不能 $(\infty)$ を表す
• NEGATIVE_CYCLE : 最短距離において負のループ $(-\infty)$ を表す

operator« (出力)

ostream &operator<<(ostream &os, const ListGraph<C_, E_> &graph)

デバッグ用

Depends on

• cpp/graph/edge.hpp
• 共通ヘッダー (cpp/template/small_template.hpp)

Required by

• cpp/graph/bellman_ford.hpp
• cpp/graph/dijkstra.hpp
• cpp/graph/find_cycle.hpp
• cpp/graph/lowlink.hpp
• cpp/graph/prim.hpp
• cpp/graph/topological_sort.hpp

Verified with

• cpp/verify/articulation_points.test.cpp
• cpp/verify/bellman_ford.test.cpp
• cpp/verify/bridges.test.cpp
• cpp/verify/detect_cycle_directed.test.cpp
• cpp/verify/detect_cycle_directed_2.test.cpp
• cpp/verify/dijkstra.test.cpp
• cpp/verify/dijkstra2.test.cpp
• cpp/verify/prim.test.cpp

Code

#pragma once
#include "graph/edge.hpp"

// グラフ(隣接リスト)
template <class Cost = ll, class E = Edge<Cost>> class ListGraph {
  int n_, m_;
  vector<vector<E>> adj;
  unordered_map<int, vector<Cost>> shortest_path_dist;
  unordered_map<int, vector<int>> shortest_path_parent;

public:
  static const Cost UNREACHABLE;
  static const Cost NEGATIVE_CYCLE;
  // 頂点数 0
  ListGraph() : n_(0), m_(0), adj(0) {}
  // 頂点数 n
  ListGraph(int n) : n_(n), m_(0), adj(n) {}

  vector<E> &operator[](int i) { return adj[i]; }

  void add_node() {
    adj.emplace_back();
    n_++;
    reset_shortest();
  }
  template <class... Args> void add_edge(int from, int to, Args... args) {
    adj[from].emplace_back(from, to, args...);
    m_++;
    reset_shortest();
  }
  // 双方向
  template <class... Args>
  void add_bidirectional_edge(int from, int to, Args... args) {
    adj[from].emplace_back(from, to, args...);
    adj[to].emplace_back(to, from, args...);
    m_ += 2;
    reset_shortest();
  }
  void reset_shortest() {
    shortest_path_dist.clear();
    shortest_path_parent.clear();
  }

  // 最短距離
  void dijkstra(int start_node);
  void bellman_ford(int start_node);
  Cost distance(int from, int to) { return shortest_path_dist[from][to]; }
  vector<Cost> distance(int from) { return shortest_path_dist[from]; }
  vector<int> shortest_path(int from, int to) {
    vector<int> path;
    for (int cur = to; cur != -1; cur = shortest_path_parent[from][cur]) {
      path.emplace_back(cur);
    }
    reverse(path.begin(), path.end());
    return path;
  }

  // 最小全域森
  Cost prim();

  // 関節点・橋
  pair<vector<int>, vector<pair<int, int>>> lowlink();

  // トポロジカルソート
  vector<E> find_cycle_directed();
  vector<int> topological_sort();
  vector<int> topological_sort_minimum();

  template <class C_, class E_>
  friend ostream &operator<<(ostream &, const ListGraph<C_, E_> &);
};

template <class Cost, class E>
const Cost ListGraph<Cost, E>::UNREACHABLE = numeric_limits<Cost>::max() >> 2;
template <class Cost, class E>
const Cost ListGraph<Cost, E>::NEGATIVE_CYCLE =
    numeric_limits<Cost>::min() >> 2;

template <class C_, class E_>
ostream &operator<<(ostream &os, const ListGraph<C_, E_> &graph) {
  os << "N = " << graph.n_ << ", M = " << graph.m_ << '\n';
  for (const auto &ev : graph.adj) {
    for (const auto &e : ev) {
      os << e << '\n';
    }
  }
  return os;
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: graph/edge.hpp: line -1: no such header

Back to top page