cp-library
競技プログラミング用 C++ ライブラリ
区間辺グラフ
graph/range_edge_graph.hpp · GitHub で見る
共通ページ
番号が連続する頂点集合への有向辺をまとめて追加します。頂点から区間、区間から頂点、区間から区間への辺を扱えます。
#include "lib/graph/range_edge_graph.hpp"
#include "lib/graph/dijkstra.hpp"
int main() {
RangeEdgeGraph<> graph(5);
graph.add_to_range(0, 1, 4, 3); // 0 -> 1,2,3 にそれぞれ重み 3
graph.add_from_range(1, 3, 4, 2); // 1,2 -> 4 にそれぞれ重み 2
graph.add_range_to_range(3, 4, 1, 3, 1); // 3 -> 1,2 にそれぞれ重み 1
graph.add_edge(0, 4, 10);
auto compressed = graph.build();
auto distance = dijkstra(compressed, 0);
distance.resize(graph.size()); // 元の頂点への距離だけを残す
// distance = {0,3,3,3,5}
auto [cost, path] = dijkstra_path(compressed, 0, 4);
auto vertices = graph.original_path(path);
// cost = 5。vertices は {0,1,4} または {0,2,4}
}
| 操作 | 内容・返り値 |
|---|---|
RangeEdgeGraph<Cost=std::int64_t>(n=0) |
元の頂点数を指定して構築 |
size() |
元の頂点数を int で返す |
vertex_count() |
補助頂点を含む頂点数を int で返す |
edge_count() |
補助辺を含む辺数を std::size_t で返す |
reserve_edges(m) |
圧縮後の辺を m 本まで格納できる容量を予約。返り値は void
|
add_edge(from,to,weight=1) |
頂点 from から頂点 to への辺を追加 |
add_to_range(from,l,r,weight=1) |
from から [l,r) の各頂点への辺を追加 |
add_from_range(l,r,to,weight=1) |
[l,r) の各頂点から to への辺を追加 |
add_range_to_range(l1,r1,l2,r2,weight=1) |
[l1,r1) の各頂点から [l2,r2) の各頂点への辺を追加 |
edges() |
圧縮後の全辺を const std::vector<Edge>& で返す。Edge は int from,to; Cost weight; を持つ |
build() |
圧縮後のグラフを DirectedCSR<Cost> で返す |
adjacency_list() |
圧縮後のグラフを std::vector<std::vector<std::pair<int,Cost>>> で返す。各辺は (行き先,重み)
|
original_path(path) |
圧縮後の頂点列から補助頂点を取り除き、元の頂点列を std::vector<int> で返す |
4 種類の辺追加関数の返り値は void です。いずれも、指定した重みの辺が各始点・終点の組に 1 本ずつある場合と同じ経路と重みを表します。区間から区間への移動でも、指定した重みを払うのは 1 回です。
元の頂点番号は [0,n)、各区間は 0 <= l <= r <= n の半開区間です。点を引数に取る辺追加関数には元の頂点番号を渡してください。自己ループ・多重辺・重なる区間に対応します。空区間への追加は何も行わず、区間から区間への追加も一方が空なら何も行いません。
0 <= n <= INT_MAX/3 とし、補助頂点を含む頂点数は INT_MAX 以下にしてください。空のグラフも作成できます。
重みはコピー可能で Cost(0) を構築できる型を指定します。build() を使う場合は Cost のデフォルト構築も必要です。重みの省略には Cost(1) も構築できる必要があります。負の重みも追加できますが、Dijkstra を使う場合は全て非負にします。負の重みを含む最短経路には Bellman–Ford など、重みに適したアルゴリズムを使ってください。
元の頂点番号は圧縮後も変わらず、補助頂点は n 以上の番号になります。build()・adjacency_list() の頂点数と、最短距離配列の長さは vertex_count() です。元の頂点への答えだけが必要な場合は、先頭の n 要素を使います。CSR 版の Dijkstra は 32 bit 以下の整数重みを 64 bit 整数の距離へ拡張します。隣接リスト版の距離は Cost と同じ型です。到達不能値や距離型・無限大の指定は、利用する最短経路ライブラリに従います。
original_path は dijkstra_path などが返す圧縮後の経路を渡して使います。到達不能な空の経路は空のまま返し、始点と終点が同じなら通常はその頂点だけが残ります。渡す番号は [0,vertex_count()) とします。論理的な辺の ID は返しません。
隣接リストを使う場合は、例の auto compressed = graph.build(); を auto compressed = graph.adjacency_list(); に置き換えられます。グラフを取り出した後も辺を追加できますが、取り出し済みのグラフへは反映されません。再び build() または adjacency_list() を呼んでください。コピーは独立します。edges() の参照とその要素には、通常の std::vector と同じ有効期間の規則が適用されます。
元の頂点数を \(N\)、点から点の辺追加回数を \(P\)、区間を含む辺追加回数を \(Q\)、両区間が空でない区間間の辺追加回数を \(R\) とします。圧縮後の頂点数は \(O(N+R)\)、辺数は \(O(N+P+Q\log N)\) です。
構築は \(O(N)\)、点から点への追加は償却 \(O(1)\)、区間を含む追加は償却 \(O(\log N)\) 時間です。対数を含む評価は \(N\ge2\) に対するもので、単一頂点のグラフや空区間の追加は定数時間です。単一頂点のグラフでは辺数は \(O(P+Q)\) です。圧縮後の頂点数・辺数を \(V,E\) とすると、保持空間は \(O(V+E)\)、グラフの取り出しは \(O(V+E)\) 時間・追加空間です。original_path は渡した列の長さに比例する時間・追加空間、reserve_edges は既存辺数に比例する時間、その他の取得は \(O(1)\) 時間です。型のコピー・構築を定数時間とします。
依存ライブラリ
コード
#ifndef RANGE_EDGE_GRAPH_HPP
#define RANGE_EDGE_GRAPH_HPP
#include "../components/directed_csr.hpp"
#include <limits>
template<class Cost = std::int64_t>
class RangeEdgeGraph {
int n_, vertices_;
std::vector<typename DirectedCSR<Cost>::Edge> edges_;
int out_(int k) const { return k >= n_ ? k - n_ : n_ + k - 1; }
int in_(int k) const { return k >= n_ ? k - n_ : 2 * n_ + k - 2; }
void vertex_([[maybe_unused]] int v) const { assert(0 <= v && v < n_); }
void range_([[maybe_unused]] int l, [[maybe_unused]] int r) const { assert(0 <= l && l <= r && r <= n_); }
template<class Emit> void cover_(int l, int r, Emit emit) const {
if (l == r) return;
if (l == 0 && r == n_) { emit(1); return; }
for (l += n_, r += n_; l < r; l >>= 1, r >>= 1) {
if (l & 1) emit(l++);
if (r & 1) emit(--r);
}
}
public:
using weight_type = Cost;
using Edge = typename DirectedCSR<Cost>::Edge;
explicit RangeEdgeGraph(int n = 0) : n_(n), vertices_(0) {
assert(0 <= n && n <= std::numeric_limits<int>::max() / 3);
vertices_ = n ? 3 * n - 2 : 0;
edges_.reserve(n ? std::size_t(n - 1) * 4 : 0);
for (int k = 1; k < n_; ++k) for (int child : {2 * k, 2 * k + 1}) {
edges_.push_back({out_(k), out_(child), Cost(0)});
edges_.push_back({in_(child), in_(k), Cost(0)});
}
}
int size() const { return n_; }
int vertex_count() const { return vertices_; }
std::size_t edge_count() const { return edges_.size(); }
void reserve_edges(std::size_t m) { edges_.reserve(m); }
void add_edge(int from, int to, Cost weight = Cost(1)) {
vertex_(from), vertex_(to);
edges_.push_back({from, to, std::move(weight)});
}
void add_to_range(int from, int l, int r, Cost weight = Cost(1)) {
vertex_(from), range_(l, r);
cover_(l, r, [&](int k) { edges_.push_back({from, out_(k), weight}); });
}
void add_from_range(int l, int r, int to, Cost weight = Cost(1)) {
range_(l, r), vertex_(to);
cover_(l, r, [&](int k) { edges_.push_back({in_(k), to, weight}); });
}
void add_range_to_range(int l1, int r1, int l2, int r2, Cost weight = Cost(1)) {
range_(l1, r1), range_(l2, r2);
if (l1 == r1 || l2 == r2) return;
if (r1 - l1 == 1) { add_to_range(l1, l2, r2, std::move(weight)); return; }
if (r2 - l2 == 1) { add_from_range(l1, r1, l2, std::move(weight)); return; }
assert(vertices_ < std::numeric_limits<int>::max());
int via = vertices_++;
cover_(l1, r1, [&](int k) { edges_.push_back({in_(k), via, weight}); });
cover_(l2, r2, [&](int k) { edges_.push_back({via, out_(k), Cost(0)}); });
}
const std::vector<Edge> &edges() const { return edges_; }
DirectedCSR<Cost> build() const { return DirectedCSR<Cost>(vertices_, edges_); }
std::vector<std::vector<std::pair<int, Cost>>> adjacency_list() const {
std::vector<std::vector<std::pair<int, Cost>>> graph(vertices_);
std::vector<std::size_t> degrees(vertices_);
for (const auto &edge : edges_) ++degrees[edge.from];
for (int v = 0; v < vertices_; ++v) graph[v].reserve(degrees[v]);
for (const auto &edge : edges_) graph[edge.from].emplace_back(edge.to, edge.weight);
return graph;
}
std::vector<int> original_path(const std::vector<int> &path) const {
std::vector<int> result;
for (int v : path) {
assert(0 <= v && v < vertices_);
if (v < n_) result.push_back(v);
}
return result;
}
};
#endif
#line 1 "graph/range_edge_graph.hpp"
#line 1 "components/directed_csr.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <memory>
#include <span>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>
namespace directed_csr_detail { struct Access; }
template<class T>
class DirectedCSR {
public:
struct Edge { int from, to; T weight; };
using Arc = std::pair<int, T>;
using weight_type = T;
using distance_type = std::conditional_t<std::is_integral_v<T> && sizeof(T) < 8, std::int64_t, T>;
private:
friend struct directed_csr_detail::Access;
std::vector<std::size_t> offset_;
std::vector<Arc> arcs_;
int single_gap_ = -2;
bool unique_incoming_ = true;
void reset(int n, std::size_t m) {
assert(n >= 0);
offset_.assign(std::size_t(n) + 1, 0);
single_gap_ = -2;
unique_incoming_ = m <= std::size_t(n);
}
void count_edge(const Edge &edge, std::vector<std::uint64_t> &seen) {
assert(0 <= edge.from && edge.from < size() && 0 <= edge.to && edge.to < size());
++offset_[edge.from];
if (unique_incoming_) {
auto mask = std::uint64_t(1) << (edge.to % 64);
auto &word = seen[edge.to / 64];
unique_incoming_ = !(word & mask);
word |= mask;
}
}
void finish(std::span<const Edge> edges) {
const auto n = offset_.size() - 1;
single_gap_ = -2;
if (edges.size() >= n - (n != 0) && edges.size() <= n &&
std::all_of(offset_.begin(), offset_.end() - 1, [](std::size_t x) { return x <= 1; })) {
single_gap_ = -1;
if (edges.size() != n) single_gap_ = int(std::find(offset_.begin(), offset_.end() - 1, 0) - offset_.begin());
for (std::size_t v = 0; v <= n; ++v) offset_[v] = v - (single_gap_ >= 0 && v > std::size_t(single_gap_));
arcs_.resize(edges.size());
for (const auto &edge : edges) arcs_[edge.from - (single_gap_ >= 0 && edge.from > single_gap_)] = {edge.to, edge.weight};
return;
}
std::size_t active = offset_[0] != 0;
for (std::size_t v = 1; v < offset_.size(); ++v) {
active += offset_[v] != 0;
offset_[v] += offset_[v - 1];
}
arcs_.resize(edges.size());
std::size_t i = edges.size();
#if defined(__GNUC__) || defined(__clang__)
if (active >= 8192) {
for (; i > 32; --i) {
const auto from = edges[i - 33].from;
__builtin_prefetch(&offset_[from], 1, 3);
__builtin_prefetch(&arcs_[offset_[from] - 1], 1, 3);
const auto &edge = edges[i - 1];
arcs_[--offset_[edge.from]] = {edge.to, edge.weight};
}
}
#endif
for (; i; --i) {
const auto &edge = edges[i - 1];
arcs_[--offset_[edge.from]] = {edge.to, edge.weight};
}
}
void clear_edges() {
single_gap_ = -2;
unique_incoming_ = true;
std::fill(offset_.begin(), offset_.end(), 0);
arcs_.clear();
}
public:
explicit DirectedCSR(int n = 0) {
assert(n >= 0);
offset_.assign(std::size_t(n) + 1, 0);
}
DirectedCSR(int n, std::span<const Edge> edges) { build(n, edges); }
template<class Producer>
DirectedCSR(int n, std::size_t m, Producer &&produce) { build(n, m, std::forward<Producer>(produce)); }
void build(int n, std::span<const Edge> edges) {
reset(n, edges.size());
try {
std::vector<std::uint64_t> seen(unique_incoming_ ? (std::size_t(n) + 63) / 64 : 0);
for (const auto &edge : edges) count_edge(edge, seen);
finish(edges);
}
catch (...) { clear_edges(); throw; }
}
template<class Producer>
void build(int n, std::size_t m, Producer &&produce) {
reset(n, m);
try {
std::vector<std::uint64_t> seen(unique_incoming_ ? (std::size_t(n) + 63) / 64 : 0);
auto edges = std::make_unique_for_overwrite<Edge[]>(m);
std::size_t count = 0;
auto emit = [&](Edge edge) {
if (count == m) throw std::length_error("DirectedCSR edge count");
count_edge(edge, seen);
edges[count++] = std::move(edge);
};
std::forward<Producer>(produce)(emit);
if (count != m) throw std::length_error("DirectedCSR edge count");
finish(std::span<const Edge>(edges.get(), m));
} catch (...) { clear_edges(); throw; }
}
int size() const { return offset_.empty() ? 0 : int(offset_.size() - 1); }
bool empty() const { return size() == 0; }
std::size_t edge_count() const { return arcs_.size(); }
std::span<const Arc> operator[](int v) const {
assert(0 <= v && v < size());
return std::span<const Arc>(arcs_).subspan(offset_[v], offset_[v + 1] - offset_[v]);
}
};
namespace directed_csr_detail {
template<class T>
struct SingleEdgeView {
std::span<const typename DirectedCSR<T>::Arc> arcs;
int n, gap;
int size() const { return n; }
std::span<const typename DirectedCSR<T>::Arc> operator[](int v) const {
if (v == gap) return {};
return arcs.subspan(v - (gap >= 0 && v > gap), 1);
}
};
struct Access {
template<class T>
static bool unique_incoming(const DirectedCSR<T> &g) { return g.offset_.empty() || g.unique_incoming_; }
template<class T>
static bool has_single_edge_layout(const DirectedCSR<T> &g) { return !g.offset_.empty() && g.single_gap_ >= -1; }
template<class T>
static SingleEdgeView<T> single_edge_view(const DirectedCSR<T> &g) { return {g.arcs_, g.size(), g.single_gap_}; }
};
}
#line 5 "graph/range_edge_graph.hpp"
#include <limits>
template<class Cost = std::int64_t>
class RangeEdgeGraph {
int n_, vertices_;
std::vector<typename DirectedCSR<Cost>::Edge> edges_;
int out_(int k) const { return k >= n_ ? k - n_ : n_ + k - 1; }
int in_(int k) const { return k >= n_ ? k - n_ : 2 * n_ + k - 2; }
void vertex_([[maybe_unused]] int v) const { assert(0 <= v && v < n_); }
void range_([[maybe_unused]] int l, [[maybe_unused]] int r) const { assert(0 <= l && l <= r && r <= n_); }
template<class Emit> void cover_(int l, int r, Emit emit) const {
if (l == r) return;
if (l == 0 && r == n_) { emit(1); return; }
for (l += n_, r += n_; l < r; l >>= 1, r >>= 1) {
if (l & 1) emit(l++);
if (r & 1) emit(--r);
}
}
public:
using weight_type = Cost;
using Edge = typename DirectedCSR<Cost>::Edge;
explicit RangeEdgeGraph(int n = 0) : n_(n), vertices_(0) {
assert(0 <= n && n <= std::numeric_limits<int>::max() / 3);
vertices_ = n ? 3 * n - 2 : 0;
edges_.reserve(n ? std::size_t(n - 1) * 4 : 0);
for (int k = 1; k < n_; ++k) for (int child : {2 * k, 2 * k + 1}) {
edges_.push_back({out_(k), out_(child), Cost(0)});
edges_.push_back({in_(child), in_(k), Cost(0)});
}
}
int size() const { return n_; }
int vertex_count() const { return vertices_; }
std::size_t edge_count() const { return edges_.size(); }
void reserve_edges(std::size_t m) { edges_.reserve(m); }
void add_edge(int from, int to, Cost weight = Cost(1)) {
vertex_(from), vertex_(to);
edges_.push_back({from, to, std::move(weight)});
}
void add_to_range(int from, int l, int r, Cost weight = Cost(1)) {
vertex_(from), range_(l, r);
cover_(l, r, [&](int k) { edges_.push_back({from, out_(k), weight}); });
}
void add_from_range(int l, int r, int to, Cost weight = Cost(1)) {
range_(l, r), vertex_(to);
cover_(l, r, [&](int k) { edges_.push_back({in_(k), to, weight}); });
}
void add_range_to_range(int l1, int r1, int l2, int r2, Cost weight = Cost(1)) {
range_(l1, r1), range_(l2, r2);
if (l1 == r1 || l2 == r2) return;
if (r1 - l1 == 1) { add_to_range(l1, l2, r2, std::move(weight)); return; }
if (r2 - l2 == 1) { add_from_range(l1, r1, l2, std::move(weight)); return; }
assert(vertices_ < std::numeric_limits<int>::max());
int via = vertices_++;
cover_(l1, r1, [&](int k) { edges_.push_back({in_(k), via, weight}); });
cover_(l2, r2, [&](int k) { edges_.push_back({via, out_(k), Cost(0)}); });
}
const std::vector<Edge> &edges() const { return edges_; }
DirectedCSR<Cost> build() const { return DirectedCSR<Cost>(vertices_, edges_); }
std::vector<std::vector<std::pair<int, Cost>>> adjacency_list() const {
std::vector<std::vector<std::pair<int, Cost>>> graph(vertices_);
std::vector<std::size_t> degrees(vertices_);
for (const auto &edge : edges_) ++degrees[edge.from];
for (int v = 0; v < vertices_; ++v) graph[v].reserve(degrees[v]);
for (const auto &edge : edges_) graph[edge.from].emplace_back(edge.to, edge.weight);
return graph;
}
std::vector<int> original_path(const std::vector<int> &path) const {
std::vector<int> result;
for (int v : path) {
assert(0 <= v && v < vertices_);
if (v < n_) result.push_back(v);
}
return result;
}
};