Boost Graph Libraryのグラフから疎行列を生成

疎行列

非零要素数がn²（nはグラフのノード数）よりも著しく少ない行列を疎行列という．要するに，ほとんどの要素が0である行列を指す．
グラフの隣接行列はたいてい疎行列となる．

n×n行列はn²個の記憶領域を必要とするが，疎行列は非零要素の値と座標のみを記憶すれば良いため，空間効率的に格納できる．

疎行列を扱うライブラリとして，Eigenを用いた．

Eigen

EigenにはSparseMatrixというクラスが用意されているため，自分で実装する必要がない．

brewでインストールしたが，その他の方法は調査していない．

brew install eigen

使用例

次のグラフの疎行列を生成する．グラフの生成はBGLで行った．

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <eigen3/Eigen/Sparse>

using namespace std;

typedef boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::bidirectionalS
    > graph;

int main()
{
    graph g;

    add_edge(0, 1, g);
    add_edge(0, 2, g);
    add_edge(1, 4, g);
    add_edge(2, 3, g);
    add_edge(3, 0, g);
    add_edge(4, 3, g);

    int num = num_vertices(g);

    Eigen::SparseMatrix<double> matrix(num, num);

    int from, to;
    for (auto i=vertices(g); i.first!=i.second; i.first++) {
        from = *i.first;
        for (auto j=inv_adjacent_vertices(*i.first, g); j.first!=j.second; j.first++) {
            to = *j.first;
            matrix.insert(from, to) = 1.0;
        }
    }

    cout << matrix << endl;
}

グラフのノードの走査の部分（for文）が少しややこしいが，疎行列の生成は

Eigen::SparseMatrix<double> matrix(num, num);

要素の代入は

matrix.insert(from, to) = 1.0;

といったように，簡単に行うことができる．生成時には0に初期化されている．

実行結果

Nonzero entries:
(1,1) (1,2) (1,4) (_,_) (1,3) (_,_) (1,0) (_,_) (1,3) (_,_)

Outer pointers:
0 2 4 6 8  $
Inner non zeros:
2 1 1 1 1  $

0 0 0 1 0
1 0 0 0 0
1 0 0 0 0
0 0 1 0 1
0 1 0 0 0

このプログラフでは登場していないが，要素の参照はcoeff()で行う．

value = matrix.coeff(row, column);

関数の詳細は

Eigen: SparseMatrix< _Scalar, _Options, _Index > Class Template Reference

に書いてある（詳細は省く）．

まとめ

Eigenを用いることで，簡単に疎行列を扱うことができた．
Eigenは疎行列の他にもベクトルなどが定義されているため，線形代数の基本的なライブラリとして扱うことができる．