cp-library

競技プログラミング用 C++ ライブラリ

View the Project on GitHub qandori/cp-library

:heavy_check_mark: 有向グラフの CSR

components/directed_csr.hpp · GitHub で見る

共通ページ

DirectedCSR<T> は、各頂点の出辺を一つの連続配列にまとめて保存する有向グラフです。辺の重みを T で保存します。

#include "lib/components/directed_csr.hpp"
#include "lib/graph/dijkstra.hpp"
#include <cstdint>
#include <vector>

int main() {
	using Graph = DirectedCSR<std::uint32_t>;
	std::vector<Graph::Edge> edges = { {0, 2, 9}, {1, 2, 3}, {0, 1, 2}, {0, 1, 5} };
	Graph g(4, edges);
	auto dist = dijkstra(g, 0); // {0,2,5,-1}
	auto [cost, path] = dijkstra_path(g, 0, 2); // 5, {0,1,2}
}

入力の辺は {始点, 終点, 重み}、頂点番号は 0 始まりです。自己辺・多重辺も保存します。無向グラフとして使う場合は、両方向の辺を入力します。

g[v] は頂点 v から出る辺の範囲です。各要素は {行き先, 重み} なので、for (const auto &[to, weight] : g[v]) で走査できます。同じ始点を持つ辺は入力された順に並びます。上の例の g[0] は {2,9}, {1,2}, {1,5} の順です。

操作・型 内容・返り値 計算量
DirectedCSR<T>(n=0) n 頂点・辺なしで構築 \(O(n)\)
DirectedCSR<T>(n,edges) std::span<const Edge> から構築。std::vector<Edge> も渡せる \(O(n+m)\)
DirectedCSR<T>(n,m,produce) produce(emit) を呼び、emit(Edge) で渡された m 本の辺から構築 \(O(n+m)\) と produce の実行
build(n,edges) 頂点数と辺を指定して再構築 \(O(n+m)\) と旧辺の破棄
build(n,m,produce) 辺を生成する関数を指定して再構築 \(O(n+m)\) と produce の実行・旧辺の破棄
size() 頂点数を int で返す \(O(1)\)
empty() 頂点数が 0 なら true \(O(1)\)
edge_count() 辺数を std::size_t で返す \(O(1)\)
operator[](v) 出辺を std::span<const Arc> で返す \(O(1)\)
Edge 入力の辺の型。int from, to と T weight を持つ —（型）
Arc 隣接辺の型。std::pair<int,T> —（型）
weight_type 保存する辺の重みの型 T —（型）
distance_type 最短経路で既定の距離型として使う型 —（型）

distance_type は、8 byte 未満の整数型では std::int64_t、それ以外では T です。例えば DirectedCSR<std::uint32_t> は辺を 32 bit で保存し、dijkstra の距離を 64 bit で計算します。64 bit 整数・浮動小数点型の距離型は変わりません。

辺を読みながら構築する場合は、次のように produce を渡します。produce は 1 回呼ばれ、受け取った emit を m 回呼んで辺を渡します。辺を受け取る処理と出次数の集計をまとめるため、辺配列を別に用意して走査する必要がありません。

#include "lib/components/directed_csr.hpp"
#include <iostream>

int n, m;
std::cin >> n >> m;
using Graph = DirectedCSR<std::uint32_t>;
Graph g(n, m, [&](auto emit) {
	for (int i = 0; i < m; ++i) {
		Graph::Edge edge;
		std::cin >> edge.from >> edge.to >> edge.weight;
		emit(edge);
	}
});

emit の呼び出し順が辺の入力順です。辺数が m と異なる場合は std::length_error を送出します。produce・辺の格納中に例外が出た場合は、指定した頂点数の辺なしグラフに戻して例外を送出します。emit は produce の呼び出し中だけ使い、保存しないでください。一時的に \(O(m)\) の辺配列を内部で確保し、構築後に解放します。

全頂点の出次数が高々 1 で、出辺のない頂点が高々 1 個なら、辺の格納位置を頂点番号から直接計算します。通常の CSR と同じ辺配列を使い、g[v] の返り値や辺の順序は変わりません。dijkstra_path もこの構造を自動で利用します。

入次数が全頂点で高々 1 かも構築中に判定します。辺数が頂点数以下の場合だけ、一時的に頂点当たり 1 bit の配列を使います。dijkstra_path はこの条件を満たすグラフでも優先度キューを省略できます。

入力の辺はコピーするため、構築後に入力配列を変更・破棄してもグラフは変わりません。辺の追加・変更には build で再構築します。g[v] の返す範囲やその要素への参照は辺配列を参照します。build・代入・移動の後は取得し直し、グラフの破棄後には使わないでください。

T はデフォルト構築・コピー・代入できる型とします。グラフの保存自体は重みの符号を制限しません。最短経路アルゴリズムに渡す場合は、そのアルゴリズムの重みの条件に従います。

\(n\) 頂点・\(m\) 辺として、重み 1 個の構築・コピー・代入を \(O(1)\) とすると構築は \(O(n+m)\) 時間・空間です。再構築時には旧辺の破棄も行い、確保した配列の容量は保持します。繰り返し再構築する場合の確保領域は、過去最大の頂点数・辺数に比例します。

検証コード

コード

#ifndef DIRECTED_CSR_HPP
#define 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_}; }
};
}

#endif
Back to top page