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
*/