メモ帳

メモ帳です.

Boost Graph Library の Compressed Sparse Row を使う

Compressed Sparse Row (CSR)

CSR は疎なグラフの効率的な表現方法である.adjacency_list といった他のフォーマットよりもオーバヘッドが小さいという特徴がある.

BGL にも CSR 方式に基づいたクラスが用意されているが,adjacency_list と使い方が大きく異なる.
adjacency_list は頂点や辺の追加や削除が自由に行えるが,compressed_sparse_row_grpah は一度初期化してしまうと辺の追加や削除ができない.
したがって,動的なグラフには向いていないため,基本的には静的なグラフに用いる.

サンプルコード

compressed_sparse_row_graph クラスを用いたサンプルコードを作成した.

gist.github.com

あらかじめ作成した vector によって初期化している.

adjacency_list のような add_edge() や add_vertex() が実装されていないが,vertex_iterator や edge_iterator によるグラフの走査は同様に実行可能である.

実行結果

A --> B, D, F,
B --> C, D,
C --> D, A,
D --> A,
E --> B, C, D,
F --> E,

まとめ

BGL の compressed_sparse_row_graph クラスを用いてグラフを表現した.
一度初期化してしまうと頂点や辺の追加や削除を行うことができない.
adjacency_list と同様に iterator が用意されているため,頂点や辺の走査が可能である.