Static Graph
(graph/static-graph.hpp)

• View this file on GitHub
• Last update: 2020-12-05 07:59:51+09:00
• Include: #include "graph/static-graph.hpp"

Static Graph

静的なグラフライブラリ。通常のグラフライブラリと同様に隣接リストで辺を保存しているが、全ての辺を連続領域に保存することでアクセス時のキャッシュミスを減らし高速化している。

使い方

• StaticGraph<T>(N, M): N頂点M辺で重みの型がT(重み無しの場合はvoid)であるグラフを作成する。
• add_edge(u, args...): uからvへ向かう重みcの辺を追加する。args...にはv, cあるいはvが入る。

Required by

• ダイクストラ法(定数倍高速化) (shortest-path/dijkstra-fast.hpp)
• ダイクストラ法(Skew Heap) (shortest-path/dijkstra-skew-heap.hpp)

Verified with

• verify/verify-aoj-grl/aoj-grl-1-a-fast-dijkstra.test.cpp
• verify/verify-aoj-other/aoj-2995-hashmap.test.cpp
• verify/verify-aoj-other/aoj-2995.test.cpp
• verify/verify-unit-test/dijkstra.test.cpp
• verify/verify-yosupo-ds/yosupo-vertex-add-path-sum-euler-tour.test.cpp
• verify/verify-yosupo-ds/yosupo-vertex-add-subtree-sum-dst-on-tree.test.cpp
• verify/verify-yosupo-ds/yosupo-vertex-add-subtree-sum-euler-tree.test.cpp
• verify/verify-yosupo-graph/yosupo-shortest-path-3.test.cpp
• verify/verify-yosupo-graph/yosupo-shortest-path-4.test.cpp
• verify/verify-yuki/yuki-1320.test.cpp

Code

#pragma once

namespace StaticGraphImpl {

template <typename T, bool Cond = is_void<T>::value>
struct E;
template <typename T>
struct E<T, false> {
  int to;
  T cost;
  E() {}
  E(const int& v, const T& c) : to(v), cost(c) {}
  operator int() const { return to; }
};
template <typename T>
struct E<T, true> {
  int to;
  E() {}
  E(const int& v) : to(v) {}
  operator int() const { return to; }
};

template <typename T = void>
struct StaticGraph {
 private:
  template <typename It>
  struct Es {
    It b, e;
    It begin() const { return b; }
    It end() const { return e; }
    int size() const { return int(e - b); }
    auto&& operator[](int i) const { return b[i]; }
  };
  
  int N, M, ec;
  vector<int> head;
  vector<pair<int, E<T>>> buf;
  vector<E<T>> es;

  void build() {
    partial_sum(begin(head), end(head), begin(head));
    es.resize(M);
    for (auto&& [u, e] : buf) es[--head[u]] = e;
  }

 public:
  StaticGraph(int _n, int _m) : N(_n), M(_m), ec(0), head(N + 1, 0) {
    buf.reserve(M);
  }

  template <typename... Args>
  void add_edge(int u, Args&&... args) {
#pragma GCC diagnostic ignored "-Wnarrowing"
    buf.emplace_back(u, E<T>{std::forward<Args>(args)...});
#pragma GCC diagnostic warning "-Wnarrowing"
    ++head[u];
    if ((int)buf.size() == M) build();
  }

  Es<typename vector<E<T>>::iterator> operator[](int u) {
    return {begin(es) + head[u], begin(es) + head[u + 1]};
  }
  const Es<typename vector<E<T>>::const_iterator> operator[](int u) const {
    return {begin(es) + head[u], begin(es) + head[u + 1]};
  }
  int size() const { return N; }
};

}  // namespace StaticGraphImpl

using StaticGraphImpl::StaticGraph;

/**
 * @brief Static Graph
 * @docs docs/graph/static-graph.md
 */

#line 2 "graph/static-graph.hpp"

namespace StaticGraphImpl {

template <typename T, bool Cond = is_void<T>::value>
struct E;
template <typename T>
struct E<T, false> {
  int to;
  T cost;
  E() {}
  E(const int& v, const T& c) : to(v), cost(c) {}
  operator int() const { return to; }
};
template <typename T>
struct E<T, true> {
  int to;
  E() {}
  E(const int& v) : to(v) {}
  operator int() const { return to; }
};

template <typename T = void>
struct StaticGraph {
 private:
  template <typename It>
  struct Es {
    It b, e;
    It begin() const { return b; }
    It end() const { return e; }
    int size() const { return int(e - b); }
    auto&& operator[](int i) const { return b[i]; }
  };
  
  int N, M, ec;
  vector<int> head;
  vector<pair<int, E<T>>> buf;
  vector<E<T>> es;

  void build() {
    partial_sum(begin(head), end(head), begin(head));
    es.resize(M);
    for (auto&& [u, e] : buf) es[--head[u]] = e;
  }

 public:
  StaticGraph(int _n, int _m) : N(_n), M(_m), ec(0), head(N + 1, 0) {
    buf.reserve(M);
  }

  template <typename... Args>
  void add_edge(int u, Args&&... args) {
#pragma GCC diagnostic ignored "-Wnarrowing"
    buf.emplace_back(u, E<T>{std::forward<Args>(args)...});
#pragma GCC diagnostic warning "-Wnarrowing"
    ++head[u];
    if ((int)buf.size() == M) build();
  }

  Es<typename vector<E<T>>::iterator> operator[](int u) {
    return {begin(es) + head[u], begin(es) + head[u + 1]};
  }
  const Es<typename vector<E<T>>::const_iterator> operator[](int u) const {
    return {begin(es) + head[u], begin(es) + head[u + 1]};
  }
  int size() const { return N; }
};

}  // namespace StaticGraphImpl

using StaticGraphImpl::StaticGraph;

/**
 * @brief Static Graph
 * @docs docs/graph/static-graph.md
 */

Back to top page