Boost Graph Libraryでグラフ構造を可視化するまで(1)

2014年8月20日水曜日 Akihiko Sato

はじめまして、ヴァル研究所の佐藤と申します。
ソフトウェアエンジニアとして日々開発をする中で知ったことを、この場で皆さんと共有できればと思います。

というわけで、今回はみんなだいすきC++ネタです。


皆さん、Boost Graph Library(BGL)というライブラリをご存知でしょうか。
BGLは、名前の通りグラフ構造を扱うためのライブラリで、グラフを表現するクラスの他、グラフを扱う基本的なアルゴリズムも用意されています。

扱うのに少し癖のあるライブラリですが、木構造やネットワーク構造を簡単に使いたいとき、威力を発揮してくれます。

それでは、今回はBGLで簡単なグラフ構造を構築し、Graphvizで画像にするところまで見てみましょう。

インストール


BGLはBoostの一部であるため、Boostがインストールされていればそのまま使用できます。

Boostのインストール方法は一般的なやり方で問題ありません。
Macであれば、Homebrewでインストールできます。

$ brew install boost

Graphvizも適当にインストールしてください。
Macであれば、Homebrewでインストールできます。

$ brew install graphviz

グラフ定義


まずは、何はともあれグラフの定義からです。

BGLではグラフの実装が予め幾つか用意されていますが、今回は、そのうちの一つboost::adjacency_listというクラスを使います。
以下のヘッダファイルをincludeしましょう。

#include <boost/graph/adjacency_list.hpp>

あとはグラフを生成し、そこに頂点や辺を足していくだけです。
試しに、1つの頂点から始まる深さ2の完全二分木を定義してみましょう。

// グラフ生成。

boost::adjacency_list<> g;



// 頂点(vertex)の追加。頂点には、addした順に0からの連番が振られます。

auto root = boost::add_vertex(g);

auto node1 = boost::add_vertex(g);

auto node2 = boost::add_vertex(g);

auto leaf1 = boost::add_vertex(g);

auto leaf2 = boost::add_vertex(g);

auto leaf3 = boost::add_vertex(g);

auto leaf4 = boost::add_vertex(g);



// 辺(edge)の追加

boost::add_edge(root, node1, g);

boost::add_edge(root, node2, g);

boost::add_edge(node1, leaf1, g);

boost::add_edge(node1, leaf2, g);

boost::add_edge(node2, leaf3, g);

boost::add_edge(node2, leaf4, g);


Graphviz形式で出力


boost::adjacency_listは、Graphviz形式(DOTフォーマット)で出力が可能です。

この機能を使うには、以下のヘッダファイルのincludeが必要です。

#include <boost/graph/graphviz.hpp>

あとは、boost::write_graphviz()関数を呼ぶだけ。

// 標準出力(std::cout)にGraphviz形式で出力

boost::write_graphviz(std::cout, g);

実行すると、以下の様な出力が得られると思います。これをsample.dotとして保存してください。

digraph G {

  0;

  1;

  2;

  3;

  4;

  5;

  6;

  0->1 ;

  0->2 ;

  1->3 ;

  1->4 ;

  2->5 ;

  2->6 ;

}

Graphvizで画像生成


保存したsample.dotをGraphvizでPNGに変えてみましょう。

$ dot -Tpng -o sample.png sample.dot

sample.pngとして、以下のような画像が生成されるはずです。



まとめ


今回はBGLとGraphvizを使い、C++上で定義したグラフ構造を画像形式で可視化しました。
しかし、ただ連番が振られた頂点が辺で結ばれているだけでは、まだあまり役に立たないかもしれません。

次回は各頂点に属性を持たせて、画像にもわかりやすいラベルを付けてみます。