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

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

#コンセプト:Graph
一般的に、グラフの効率的な実装は状況により異なる。
そのため、様々なグラフの実装が用いられるが、[Graphコンセプト](http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/Graph.html)は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では定められており、また、複数のタグを組み合わせたコンセプトも定められている物もある。
詳しくは[リファレンス](http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/table_of_contents.html)の[12章](http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/graph_concepts.html)参照。

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

#その他のコンセプト

Graphコンセプトそのものはグラフを操作する方法をまったく提供していない。
グラフを操作する方法を提供するコンセプトは[MutableGraphコンセプト](http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/MutableGraph.html)である。MutableGraphコンセプトは頂点やエッジを操作するメンバ関数を要件として持つ。
例えば、add_edge,add_vertex等である。ここではこれ以上説明しない。

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

#例:adjacency_list
[adjacency_listクラステンプレート](http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/adjacency_list.html)はVertexListGraphコンセプト・EdgeListGraphコンセプト・MutableGraphコンセプト・PropertyGraphコンセプトを満たすクラスのテンプレートである。
宣言は

```cpp
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は頂点、辺、グラフのプロパティを設定するための型だが、後ほど解説する。

さっそく使ってみよう。

```cpp
#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)を用いる。

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

```cpp
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のページ](http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/adjacency_list.html)に書いてある。

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

```cpp
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の間に辺を結んでみよう。

```cpp
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だけを取得する。

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

```cpp
boost::remove_edge(e1,graph1);
```

とすれば良い。

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

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

```cpp
boost::adjacency_list<> graph1(100);
```

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

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

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

```cpp
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には種々のプロパティをメンバに持つクラスを指定する。
例えば、

```cpp
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;
```
の様にする。

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

```cpp
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';
```

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

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

プロパティについては以上で終わるが、説明していないこととしてPropertyMapがある。
これはプロパティの値をアルゴリズム中で使う時に（例えばエッジの重みをプロパティとして与えるとか）主に用いるは、[ここ](http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/bundles.html)のProperties maps from bundled propertiesの節に書いてある。

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