無向グラフの CSR

components/undirected_csr.hpp · GitHub で見る

共通ページ

#include "lib/components/undirected_csr.hpp"

std::vector<std::pair<int, int>> edges;
edges.emplace_back(0, 1);
UndirectedCSR graph(2, edges);
for (auto [to, id] : graph[0]) {
}

関数・メンバ	内容・返り値	計算量
UndirectedCSR(n,edges)	無向グラフの隣接配列を構築。辺一覧は span<const pair<int,int>>	\(O(n+m)\)
UndirectedVertexCSR(n,edges)	辺 ID を保持せず、行き先だけの隣接配列を構築	\(O(n+m)\)
graph[v]	頂点 v の出辺を span<const Arc> で返す	\(O(1)\)
Arc::to / Arc::id	行き先／入力順の辺 ID	\(O(1)\)
n	頂点数	\(O(1)\)
start[v] / start[v+1]	頂点 v の出辺を格納した半開区間	\(O(1)\)
adj[i]	平坦な隣接配列の要素	\(O(1)\)

頂点番号は 0 始まりで、多重辺・自己ループ・孤立点・空グラフに対応します。各辺を両方向に保存するため、自己ループも 2 個の出辺になります。同じ頂点からの出辺は入力順です。

辺 ID が不要なら UndirectedVertexCSR を使えます。n・start の意味は同じで、adj の要素は行き先の int、graph[v] は span<const int> を返します。

入力の辺一覧は構築後に破棄して構いません。構築後にメンバを変更しないでください。コピーはできず、ムーブはできます。頂点数は INT_MAX 未満、辺数は INT_MAX/2 以下としてください。

頂点数を \(n\)、辺数を \(m\) として、構築は \(O(n+m)\) 時間・空間、graph[v] の取得は \(O(1)\) 時間です。

検証コード

• test/biconnected_components.test.cpp
• test/dsu_on_tree_subtree_sum.test.cpp
• test/low_link_articulation.test.cpp
• test/low_link_bridge.test.cpp
• test/rerooting.test.cpp
• test/rerooting_diameter.test.cpp
• test/steiner_tree.test.cpp
• test/two_edge_connected_components.test.cpp

コード

#ifndef UNDIRECTED_CSR_HPP
#define UNDIRECTED_CSR_HPP

#include <cassert>
#include <cstddef>
#include <limits>
#include <memory>
#include <span>
#include <type_traits>
#include <utility>
#include <vector>

namespace undirected_csr_detail {
template <class Arc>
void build(int n, std::span<const std::pair<int, int>> edges, std::vector<int>& start, std::unique_ptr<Arc[]>& adj) {
	assert(0 <= n && n < std::numeric_limits<int>::max());
	assert(edges.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
	start.assign(std::size_t(n) + 1, 0);
	for (auto [u, v] : edges) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		++start[u + 1], ++start[v + 1];
	}
	for (int v = 0; v < n; ++v) start[v + 1] += start[v];
	adj.reset(new Arc[2 * edges.size()]);
	std::vector<int> cursor(start.begin(), start.end() - 1);
	for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
		auto [u, v] = edges[i];
		if constexpr (std::is_same_v<Arc, int>) adj[cursor[u]++] = v, adj[cursor[v]++] = u;
		else adj[cursor[u]++] = {v, i}, adj[cursor[v]++] = {u, i};
	}
}
}

struct UndirectedCSR {
	struct Arc { int to, id; };
	int n;
	std::vector<int> start;
	std::unique_ptr<Arc[]> adj;
	UndirectedCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
		undirected_csr_detail::build(n, edges, start, adj);
	}
	std::span<const Arc> operator[](int v) const {
		assert(0 <= v && v < n);
		return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
	}
};

struct UndirectedVertexCSR {
	int n;
	std::vector<int> start;
	std::unique_ptr<int[]> adj;
	UndirectedVertexCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
		undirected_csr_detail::build(n, edges, start, adj);
	}
	std::span<const int> operator[](int v) const {
		assert(0 <= v && v < n);
		return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
	}
};

#endif

Back to top page