C++のBoostでグラフの実装/操作を効率爆上げしよう

Boostで車輪の再発明を防ぐ

エンジニアに求められるのは問題解決であり、既に議論され尽くされたアルゴリズムの再実装ではありません。Boostというライブラリは、極めて強力でありながら、バイナリ配布であれば商用利用でもライセンス表示が必要ありません。¹

しかし、Boostのクラスのテンプレート引数などがかなり多種多様で、ドキュメントは網羅的なため読みにくいです。
というわけで、必要最低限のスモールゴールを立てて、Boostをつまみ食いしてみましょう。

Boost環境構築(ミニマムに)

Linuxにインストール

sudo apt-get install libboost-all-dev

自分のc++ファイルにインクルード

# include <boost/graph/adjacency_list.hpp>

無向グラフを作る

自家製グラフの初期設定

隣接リスト, adjacent listを作成します。
これがグラフの実態のようなものであり、テンプレートの引数をいろいろ変えると多彩な表現があります。が、初めはテンプレートの中身は深く考えないでください。

  typedef boost::adjacency_list<boost::vecS, boost::vecS,
                                boost::undirectedS,
                                > SimpleGraph;

1,2の引数は裏でグラフを実装する際に用いられるタイプを指定してます。裏でstd::vecなどが働いているのですが、その辺は今は考えないで大丈夫です。ここはパフォーマンスに影響しますが、今は考えないで大丈夫です。²

3つ目の引数ではundirectedSとありますが、これは見たままの無向グラフのことですね。
そして、その後の引数は指定せずデフォルトに任せましょう。

そして実際のグラフのインスタンスを作りましょう

SimpleGraph G;

はい、これでグラフを作ったのでこのチュートリアルは終了です。
とはいうものの、頂点を追加しないと意味ないですよね。

頂点を追加したり、それらを辺で結んだり

頂点(vertex)を追加してみましょう。

// 名前をつけてもいいですし
auto vertexAlpha = add_vertex(G);
auto vertexBeta = add_vertex(G);
// 名前？そんなのいらねえというあなたには、名無しの権兵衛でもいいです
add_vertex(G);

なお、頂点に名前をつけないと点と点に辺(Edge)をつけることが難しいです

次に、以下のように辺を繋げます。

// alpha, betaの点は簡単に繋げられる
add_edge(vertexAlpha, vertexBeta,G);

// 辺　に名前つけたかったらどうぞ
// auto myFavoriteEdge = add_edge({頂点} ,{頂点}, G)

全ての頂点の情報を得てみる

これから示すコードのようにすれば実現できます。

頂点を調べてみよう

  // -- イテレーターを得るためのオブジェクトに名前をつける (Optional) --
  auto vpair = vertices(G);
  // ん？vertices(G)のfirst, secondとかってなんやねん？それは後述
  for(auto iter=vpair.first; iter!=vpair.second; iter++) {
    std::cout << "vertex " << *iter << std::endl;
  }

  // -- 名前つけないとこんな感じ --
  for(auto iter=vertices(G).first; iter!=vertices(G).second; iter++) {
    std::cout << "vertex " << *iter << std::endl;
  }

以下のようにイテレータを使うと0,1,2,...のような頂点の中身が出力されてきます。この数字は深く考えないでください。*

(頂点を表すために***ドラえもん, アンパンマン, バイキンマン, ...***のような一意な識別子を別に割り当ててもいいけど、より単純な識別子として整数値を割り当てたんでしょうね。)

イテレータのfirst, secondってなんなん？

イテレータでよく出てくるbegin(), end()の形と違い、上のイテレータではfirst, secondというメンバ変数を用いています。これはどういうことでしょうか。

vertex(G)は以下のような"vertex_iterator"をを返します³

Name: Vertex Set of the Graph
Return Type: boost::graph_traits::vertex_iterator
Description: Returns an iterator-range providing access to all the vertices in the graphg.

さらに、その"vertex_iterator"に関する公式の記述として以下を発見しました。⁴

This function returns a std::pair of vertex iterators (the first iterator points to the "beginning" of the vertices and the second iterator points "past the end").

つまり、
メンバ変数firstは一番最初の要素へのポインタであり、メンバ変数secondは一番最後の頂点の終わりを示すポイント
ということだそうです。

"past the end"は日本語で説明が難しいですが、区間で表すと[first, second)という感じですね。イテレータでありがちなbegin(), end()と同様に使っていいようです。

はい、first, secondという名前が舌足らずですよね。。
ネット上調べても直接的な回答がなく、公式ドキュメント読んでやっとわかりました。
やはり公式ドキュメントしか勝たん。。。ですね。。。

なお、辺に関してイテレートする際も同様にfirst, secondを用います。辺に関するイテレーションはこの記事では省きます。

[FYI]頂点の数を知るには

num_vertices(G)が使えます。forループで重宝します。

std::cout<<num_vertices(g)<<std::endl;

ある頂点に繋がってる頂点を調べてみる

無向グラフを考えていたので、せっかくなら、ある頂点からの連結性を知りたいですよね。⁵
必要なヘッダーをさらにぶちこみましょう。

# include <boost/graph/connected_components.hpp>

    // ある頂点に繋がってる頂点を格納する
    std::vector<int> component(num_vertices(G));
    // ある要素に連結している要素の数を得る
    int num = connected_components(G, &component[0]);

    // 型推論を利用。これは後述
    for (auto i = 0; i != component.size(); ++i){
      // 整数値i自体が頂点を表す
      std::cout << "Vertex " << i <<" is in component " << component[i] << std::endl;
    }

connected_componentsの第二変数はちょっとよくわかりませんが、公式ドキュメントを参照したコードなので大丈夫でしょう。

とにもかくにも、公式の記述ではconnected_componentsの第二変数に関して以下の記載があります。⁶

ComponentMap comp

The ComponentMap type must be a model of Writable Property Map. The value type should be an integer type, preferably the same as the vertices_size_type of the graph. The key type must be the graph's vertex descriptor type.

std::vector<int> component(num_vertices(G));
で定義されているcomponentはvectorですが、Writable Property Mapとして扱われるみたいです。
とりあえず空のvectorcomponentの0番目要素のアドレスを渡せば、頂点を表す前に述べたような整数値をvectorcomponent[]全体にぶち込んでくれるみたいですね。MapというのはラベリングのMappingのことを表しているのでしょうかね。よくわかりませんが、動くのでよしとしましょう。

挙動の例

例として0,1,2,3のうち、0と2をくっつけます。これで先ほどのコードを実行しましょう。

頂点の例

  // 0
  auto v1 = add_vertex(G);
  // 1
  auto v2 = add_vertex(G);
  // 2
  auto v3 = add_vertex(G);
  // 3
  add_vertex(G);

  // 0-2
  add_edge(v1,v3,G);

実際の挙動

Vertex 0 is in component 0
Vertex 1 is in component 1
Vertex 2 is in component 0
Vertex 3 is in component 2

ちゃんと0,2は連結していて、それ以外は別々にラベリングされているのが確認できました。

Boostでは型推論autoを使うと便利

ある頂点に連結している頂点のコードにおいて、forループのループ変数iはわざわざ型を明示するのがだるいのでautoで型推論というC++の仕様としては新しい書き方にしました。
Boostでは型がいちいち長いので入力するのは面倒です。これまでのコードスニペットでもしれっとauto使ってました、すみまっせん。
なお、型推論を用いない場合は以下のようにできます。

    std::vector<int>::size_type i;

最後に

Boostは強力なグラフやデータの格納コンテナのライブラリですが、機能が豊富ということは
(i)どのクラスのどのオプションを使えばいいのか把握しづらい
(ii)瑣末な事項に気が散って、学習が進まない
などといった状況に陥りがちです。

最初から全体像を把握すると結局こうした状況になり、効率がよくないので、
(A)業務などでユースケースが定まっている場合は、より明確にして、それを公式ドキュメントを参照しながら実現してみる
(B)もし、自分で学習するために、そうしたゴールが明確でない場合も、とりあえず当てぎめして、絞った範囲を探索する
などとすることにより、結果として効率よく背景知識が、一口サイズで脳にインストールできることが実感できました。

今後もBoostに関して学びながら得た知識を、信頼できるソースへの引用付きで、一口サイズでQiitaにアウトプットしていこうと思います。
ここまでお読みいただきありがとうございました!

それでは、Boostとともに素晴らしいC++ライフをお過ごしください！

1. "Must not require that the license appear with executables or other binary uses of the library." from https://www.boost.org/users/license.html ↩

2. グラフで要素の削除を高速に行いたいか、そうでないかなどが指定するタイプによって異なります。この辺のトレードオフは自分で実装するときにstd::vec使うか、連結リスト使うかとか検討することと結局は同じことですね。 https://www.boost.org/doc/libs/1_66_0/libs/graph/doc/using_adjacency_list.html#sec:choosing-graph-type ↩

3. https://www.boost.org/doc/libs/1_76_0/libs/graph/doc/VertexListGraph.html ↩

4. https://www.boost.org/doc/libs/1_35_0/libs/graph/doc/quick_tour.html ↩

5. https://www.boost.org/doc/libs/1_68_0/libs/graph/example/connected_components.cpp ↩

6. https://www.boost.org/doc/libs/1_68_0/libs/graph/doc/connected_components.html ↩