Compressed Sparse Row
(graph/csr.hpp)

• View this file on GitHub
• Last update: 2026-08-11 23:01:09+09:00
• Include: #include "graph/csr.hpp"

グラフを Compressed Sparse Row 形式で表す．

グラフ g の辺を連続領域へ格納する．構築後の隣接辺は変更できない．辺型 E は入力グラフの辺型と一致するものとする．

• CSR<E>()：空の CSR を構築する．
• CSR<E>(g)：グラフ g から構築する．
• build(g)：グラフ g から再構築する．
• size()：頂点数を返す．
• edge_count()：有向辺として数えた辺数を返す．
• operator[](x)：頂点 $x$ から出る辺を span<const E> として返す．

構築は $O(N+M)$ 時間，空間計算量は $O(N+M)$．隣接辺列の取得は $O(1)$ 時間．

Verified with

• verify/graph/UNIT_graph.test.cpp

Code

#pragma once

// Compressed Sparse Row format
template <class E>
struct CSR {
  CSR() : start(1, 0) {}
  template <class G>
  CSR(const G& g) { build(g); }
  size_t size() const { return start.size() - 1; }
  size_t edge_count() const { return edges.size(); }
  span<const E> operator[](int x) const {
    assert(0 <= x && x < static_cast<int>(size()));
    return span<const E>(edges).subspan(start[x], start[x + 1] - start[x]);
  }
  template <class G>
  void build(const G& g) {
    int n = g.size();
    start.assign(n + 1, 0);
    for (int i = 0; i < n; i++) start[i + 1] = start[i] + g[i].size();
    edges.clear();
    edges.reserve(start[n]);
    for (int x = 0; x < n; x++)
      for (const auto& e : g[x]) edges.push_back(e);
  }

 private:
  vector<E> edges;
  vector<int> start;
};

/**
 * @brief Compressed Sparse Row
 * @docs docs/graph/csr.md
 */

#line 2 "graph/csr.hpp"

// Compressed Sparse Row format
template <class E>
struct CSR {
  CSR() : start(1, 0) {}
  template <class G>
  CSR(const G& g) { build(g); }
  size_t size() const { return start.size() - 1; }
  size_t edge_count() const { return edges.size(); }
  span<const E> operator[](int x) const {
    assert(0 <= x && x < static_cast<int>(size()));
    return span<const E>(edges).subspan(start[x], start[x + 1] - start[x]);
  }
  template <class G>
  void build(const G& g) {
    int n = g.size();
    start.assign(n + 1, 0);
    for (int i = 0; i < n; i++) start[i + 1] = start[i] + g[i].size();
    edges.clear();
    edges.reserve(start[n]);
    for (int x = 0; x < n; x++)
      for (const auto& e : g[x]) edges.push_back(e);
  }

 private:
  vector<E> edges;
  vector<int> start;
};

/**
 * @brief Compressed Sparse Row
 * @docs docs/graph/csr.md
 */

Back to top page