読者です 読者をやめる 読者になる 読者になる

メモ帳

メモ帳です.

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

疎行列

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

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

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

Eigen

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

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

brew install eigen

使用例

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

f:id:tomov3:20160623173546p:plain

#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は疎行列の他にもベクトルなどが定義されているため,線形代数の基本的なライブラリとして扱うことができる.