[c++,boost] boost::graphのお勉強

Boost Graph Library

BGL(Boost Graph Library)自体が何であるか、目的は何であるかはこのページにある。
重要な事はBGL自体で完結したグラフライブラリを提供する事ではなく、BGLを使って、汎用的で持続可能なグラフ理論のアルゴリズム作成を支援する事である。
これに関連して、興味深い例が先に掲げたページにあるので、興味のある人は参照して欲しい。

コンセプト:Graph

一般的に、グラフの効率的な実装は状況により異なる。
そのため、様々なグラフの実装が用いられるが、GraphコンセプトはBoost Graphで用いられるグラフの実装に共通の要件を提供する。

Graphコンセプトを満たす型は次の条件を満たさなければならない。

. vertex_descriptor typedef名を持つ
. edge_descriptor typedef名を持つ
. directed_category typedef名を持つ
. edge_parallel_category typedef名を持つ
. traversal_category typedef名を持つ
. static vertex_descriptor null_vertex()静的メンバ関数を持つ

vertex_descriptorとedge_descriptorはデフォルトコンストラクタ、コピーコンストラクタ、コピー代入演算子を持ち、等値比較可能、つまりbool operator==を持たなければならない。

vertex_descriptorとedge_descriptorはそれぞれ、グラフの頂点、辺を表すクラスである。
vertex_descriptorとedge_descriptorはint型となる事が多いが、それはGraphコンセプトでは保証されない。実装によっては、intでない事も当然ありうる。

directed_categoryは、グラフの有向、無向を指定する。
boost::directed_tag又はboost::undirected_tagに変換可能な型を指定しなければならない。

edge_parallel_categoryは有向グラフ指定されている時に、エッジが追加された場合、逆向きのエッジを追加するかどうかを指定する。
boost::allow_parallel_edge_tag又はboost::disallow_parallel_edge_tagに変換可能な型を指定しなければならない。

traversal_categoryはグラフの持つ頂点やエッジにどの様にアクセスできるかを指定する。
すなわち、イテレート可能か、等であり、この指定によって多くのアルゴリズムの計算量が規定されるので、自分の解こうとしている問題や、アルゴリズムの実装の要件に合わせて、慎重に選択しなければならない。
以下にこのtypedef名が受け入れ可能な型とそれぞれの性質を示す。

型名(boost::XXX)	性質
incidence_graph_tag	接続グラフ。ある頂点から出るエッジ達をイテレートできる。
adjacency_graph_tag	隣接グラフ。ある頂点から出るエッジの先の頂点をイテレートできる。接続グラフと似ている。
bidirectional_graph_tag	双方向グラフ。接続グラフの性質に加えて、ある頂点に入るエッジ達をイテレートできる。
vertex_list_graph_tag	頂点リストグラフ。全ての頂点をイテレートできる。
edge_list_graph_tag	辺リストグラフ。全ての辺をイテレートできる。
adjacency_matrix_tag	隣接行列。２つの頂点の間にエッジがあるかどうかを素早く判定できる。

これらのタグは、typedef名がこれらに変換可能かによって有効無効が決まるので、複数のタグを有効にする事もできる。
また、これらのタグに対応するコンセプトもBGLでは定められており、また、複数のタグを組み合わせたコンセプトも定められている物もある。
詳しくはリファレンスの12章参照。

以上がGraphコンセプトの全容である。

その他のコンセプト

Graphコンセプトそのものはグラフを操作する方法をまったく提供していない。
グラフを操作する方法を提供するコンセプトはMutableGraphコンセプトである。MutableGraphコンセプトは頂点やエッジを操作するメンバ関数を要件として持つ。
例えば、add_edge,add_vertex等である。ここではこれ以上説明しない。

グラフ、頂点、エッジにプロパティを設定できると便利である。
このための方法を提供するコンセプトとしてPropertyGraphコンセプトがある。PropertyGraphコンセプトは、グラフ、頂点、エッジに対して、PropertyMapコンセプト、より正確には、ReadWritePropertyMapコンセプトを満たすオブジェクトを取得、設定するメンバ関数を要件として持つ。
詳しくは、リンク先を読んで欲しい。

例:adjacency_list

adjacency_listクラステンプレートはVertexListGraphコンセプト・EdgeListGraphコンセプト・MutableGraphコンセプト・PropertyGraphコンセプトを満たすクラスのテンプレートである。
宣言は

template<OutEdgeList, VertexList, Directed,
               VertexProperties, EdgeProperties,
               GraphProperties, EdgeList>
class adjacency_list;

である。

adjacency_listは頂点全てを格納する一次元配列と、各頂点から出るエッジの接続先を格納する２重配列によってグラフの情報を保持する。
頂点数V、辺数Eに対し、メモリオーダーはO(V+E)となる。
エッジの追加はO(1)である。
頂点Aから頂点Bに行くエッジがあるかどうかを調べようとすると、二重配列の深さだけ典型的には時間がかかる。

Edgelist<OutEdgeList>は各頂点から出るエッジの接続先を格納する二重配列の型であり、VertexListは頂点全てを格納する一次元配列の型である。

Directedは有向、無向、双方向を指定するタグで、boost::directedS, boost::undirectedS, boost:bidirectionalSを取る事ができる。

VertexProperties, EdgeProperties, GraphPropertiesは頂点、辺、グラフのプロパティを設定するための型だが、後ほど解説する。

さっそく使ってみよう。

#include <boost/graph/adjacency_list.hpp>

int main()
{
  boost::adjacency_list<> graph;
  return 0;
}

boost::adjacency_listはデフォルトテンプレートパラメタでは、VartexList,Edgelistにはboost::vecS(中身はstd::vector)を用い、
Directedはboost::directedSで、プロパティは全てboost::no_propertyで、Edgelistはboost::listS(中身はstd::list)を用いる。

テンプレートを自分で指定してみても良いだろう。
例えば

boost::adjacency_list<
  boost::vecS,
  boost::listS,
  boost::directedS,
  boost::no_property,
  boost::no_property,
  boost::no_property,
  boost::vecS
> graph2;

ところでこれらの型のvertex_descriptorや、edge_descriptorを調べてみるとどうであろう。
typeidを使ってしらべると、
decltype(graph1)::vertex_descriptorはunsigned int
decltype(graph2)::vertex_descriptorはvoid *
である事が分かる。

VertexListにboost::vecSを用いた場合、頂点配列はランダムアクセスできるので、頂点の識別子として配列のインデックスを配布しておけば良いので、vertex_descriptorはstd::size_tになっている。
一方、VertexListにboost::listSを用いた場合、頂点配列へのランダムアクセスが遅いので、頂点の識別子として配列のノードのポインタを配布する事で、ランダムアクセスを速くしている。

また、boost::vecSを用いている場合、vertex_descriptorやedge_descriptorは常に一つのオブジェクトを指しているとは限らない。
頂点の削除や辺の追加等によって、要素の並びが変わってしまい、識別子が不正となる事がある。
どの様な操作で識別子が不正になるかはadjacency_listのページに書いてある。

それでは頂点を追加してみよう。

decltype(graph1)::vertex_descriptor v1 = boost::add_vertex(graph1);
decltype(graph1)::vertex_descriptor v2 = boost::add_vertex(graph1);

boost::add_vertex関数テンプレートはグラフに頂点を追加し、追加した頂点を表すvertex_descriptorを返す。
これらの操作はMutableGraphコンセプトにより保証されている。
今は分かりやすくするようにv1,v2の型をこの様に書いているが、もちろんautoで受けてもよいし、型を全部手書きしても良い。

v1とv2の間に辺を結んでみよう。

decltype(graph1)::edge_descriptor e1 = std::get<0>(boost::add_edge(v1,v2,graph1));

頂点を追加する時と違って、辺を追加する時は、すでに辺があった場合は辺を追加できないため、辺を追加できたかできなかったを報告する必要がある。
そのため、boost::add_edgeはedge_descriptorとboolのタプルで結果を返す。
今回はstd::get<0>でedge_descriptorだけを取得する。

このエッジを消したくなったら

boost::remove_edge(e1,graph1);

とすれば良い。

ところで、グラフの全ての頂点とエッジの識別子を自分で管理するのは何ともあほらしい。
とくに要素が大量にある時は識別子だけでもスペースを取る。
あるいは、要素の追加と同時に識別子がいつでも得られる分けではない。

例えば、adjacency_listはコンストラクタに整数を取って、その数だけコンストラクト時に頂点を確保できる。

boost::adjacency_list<> graph1(100);

しかし、識別子は得られない。

この様な場合のために、adjacency_listは頂点をイテレートする方法を提供している。
これはVertexListGraphコンセプトやEdgeListGraphコンセプトによって保証されている。

例えば、頂点をイテレートしたい場合、vertices関数を用いればよい。

auto range = boost::vertices(graph1);

vertices関数はstd::pair<decltype(graph1)::vertex_iterator,decltype(graph1)::vertex_iterator>を返す。
これは、beginとendの組の様な物だ。
vertex_iterator typedef名が定義されている事もやはりVertexListGraphコンセプトで保証されている。
これらのイテレータの値はvertex_descriptorとなる。

adjacency_listはEdgeListGraphコンセプトも満たすので、頂点と同様にedges関数を使ってイテレータを取得できる。

ここまでが基本の操作で、これさえ理解できれば、後は種々のアルゴリズムを組み合わせていくだけである。

また、adjacency_list以外にも、BGLは接続行列表現のグラフや疎行列表現のグラフの実装も持つ。
いろいろと遊んでみて欲しい。

adjacency_list: property

この節のプロパティの説明はBGL一般というよりは、adjacency_listについての話である。

前節では、adjacency_listのテンプレートパラメタ、VertexProperties,EdgeProperties,GraphPropertiesについて省略した。
プロパティの指定の仕方にはinternal propertiesとbundled propertiesがある。
internal propertiesは基本的には、後方互換性のために残された遺物で、C++標準規格を守ろうとしない某コンパイラのためにある。
(これはC++11とかC++14の話ではなくもっと昔からあるC++の話）
もっとも、最近では多くのメジャーなコンパイラがある程度まともな実装をする様になったので、ここではbundled propertiesを説明する。

SPARCプロセッサに特に最適化した、極東アジア製のベンダーロックインを受けた某ヘンテココンパイラを使ってる人は諦めてください。
半導体ベンダーの巨人が作っている最近はそんなに速くない某コンパイラも駄目かもしれません。

XXXPropertiesには種々のプロパティをメンバに持つクラスを指定する。
例えば、

struct myGraphProperty
{
  std::string name;
  int foo;
};

struct myVertexProperty
{
 std::string name;
 double verver;
};

struct myEdgeProperty
{
  std::string name;
  char hoge;
};

boost::adjacency_list<
  boost::vecS,
  boost::vecS,
  boost::undirectedS,
  myVertexProperty,
  myEdgeProperty,
  myGraphProperty
> graph;

の様にする。

プロパティへのアクセスは添え字演算子で非常に簡単に行える。

auto v1 = boost::add_vertex(graph);
auto v2 = boost::add_vertex(graph);
graph[v1].name = "vertex 1";
graph[v2].name = "vertex 1";
graph[v2].verver = 3.1415;

auto e1 = std::get<0>(boost::add_edge(v1,v2,graph));
graph[e1].name = "edge 1";
graph[e1].hoge = 'p';

グラフそのもののプロパティへのアクセスは次の様に行う。

graph[boost::graph_bundle].name = "This is the graph."

プロパティについては以上で終わるが、説明していないこととしてPropertyMapがある。
これはプロパティの値をアルゴリズム中で使う時に（例えばエッジの重みをプロパティとして与えるとか）主に用いるは、ここのProperties maps from bundled propertiesの節に書いてある。

終わりに

非常に基礎的な事ばかりを長々と書いたが、これさえ理解できればBGLは全て理解できる。
自分の勉強がてらにまとめたものなので、他の人に上手く伝わるかは分からない。
がんばって清く正しいグラフライフを送って欲しい。