futada diary

Boost.Graphの概要

プログラミング, C/C++ | 22:51

これはBoost Advent Calendar 2011の20日目の記事です。

この記事の前半の方はBoost.Graphを使ったことがない人をターゲットとしており、なんとなくBoost.Graphの雰囲気を知ってもらうことを目的としています。

後半の方はBoost.Graphを使う上ではまったく知っておく必要がないことを書いてあり、私がなんとなく気になって調べたことをかいてあります。

Boost.Graphとは？

頂点(vertex)と辺(edge)の集合からなるグラフのデータを扱ったり、グラフのアルゴリズムが実装されているライブラリです。

たとえば、3個のvertexからなり、vertex 0 -> 1、0 -> 2、1 -> 2の3個のエッジを持つ有向グラフのデータをBoost.Graphを使って作るには以下のようなコードになります。

#include <vector>
#include <boost/graph/adjacency_list.hpp>

int main()
{
  std::vector<std::pair<int, int> > edge_list = {{0, 1}, {0, 2}, {1, 2}};
    
  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
				boost::no_property,
				boost::no_property,
				boost::no_property> Graph;

  Graph graph(edge_list.begin(), edge_list.end(), 3); // コンストラクタの引数は、エッジイテレータの最初, 最後, vertex数の順

  return 0;
}

これで変数graphには、以下のようなグラフ構造ができます。

vertexにプロパティを付ける

各頂点(vertex)には、それに紐付いたデータ(プロパティ)を付けることができます(エッジやグラフ自体にもプロパティを付けることは可能です)。たとえば、各vertexにstd::stringとintのデータを持たせたい場合は、

• プロパティを区別するためのタグであるenumを定義する(今回はvertex_vname_tにstd::string、vertex_vid_tにintとする。enumの命名規則はルールがあるので注意)
• BOOST_INSTALL_PROPERTYマクロでプロパティを設定する。
• boost::propertyを入れ子状に使って、必要なvertexプロパティを定義

という感じです。詳しくは以下のソースです

#include <vector>
#include <boost/graph/adjacency_list.hpp>

enum vertex_vname_t {
  vertex_vname
};
enum vertex_vid_t {
  vertex_vid
};
namespace boost {
  BOOST_INSTALL_PROPERTY(vertex, vname);
  BOOST_INSTALL_PROPERTY(vertex, vid);
}

int main()
{
  std::vector<std::pair<int, int> > edge_list = {{0, 1}, {0, 2}, {1, 2}};

  // vertexのプロパティを定義。
  // std::string(識別のタグとしてvertex_vname_t)とint(タグはvertex_vid_t)をvertexのデータにする
  typedef boost::property<vertex_vname_t, std::string,
                          boost::property<vertex_vid_t, int> > VertexProperty;
  
  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
				VertexProperty, // VertexPropertyにする
				boost::no_property,
				boost::no_property> Graph;

  Graph graph(edge_list.begin(), edge_list.end(), 3);

  return 0;
}

必要に応じて、typedef ... VertexPropertyの部分に新しいboost::propertyを追加することで柔軟なプロパティを扱えるようになっているようです。もし3個のプロパティを使うなら以下のような感じになります。

  typedef boost::property<vertex_vname_t, std::string,
                          boost::property<vertex_vid_t, int,
                                          boost::property<vertex_hoge_t, double> > > VertexProperty;

さて、実際に値を設定するには、put関数を使います(引数は、タグ, グラフオブジェクト, vertexの番号, valueの順)。具体的な使い方は以下のソースのような感じです

  boost::put(vertex_vname_t(), graph, 0, "abc"); // タグを指定(vertex_vname_t)して値を設定する
  boost::put(vertex_vname_t(), graph, 1, "def");
  boost::put(vertex_vname_t(), graph, 2, "ghi");

  boost::put(vertex_vid_t(), graph, 0, 100);
  boost::put(vertex_vid_t(), graph, 1, 200);
  boost::put(vertex_vid_t(), graph, 2, 500);

このように書くと、以下のようにグラフに値が設定されます。

vertexのプロパティを取得するにはget関数を使います。put関数と同様にタグを指定します。たとえば以下のような感じです。

  std::string a = boost::get(vertex_vname_t(), graph, 1);
  int         b = boost::get(vertex_vid_t(),   graph, 2);

これで、変数aには"def"、bには500が入ります。

実際はどんなクラスでプロパティが保存されているのか？

Boost.Graphを使う上ではまったく関係ありませんが、実際にはどんなクラスでプロパティが保存されているか確認してみます。

これはboostのpendingディレクトリにあるproperty.hppを見れば分かります。たとえば上記で使ったプロパティ

  boost::property<vertex_vname_t, std::string,
                  boost::property<vertex_vid_t, int> >

が以下のように具体的にはなります。

struct boost::no_property
{
};

template <>
struct boost::property<vertex_vid_t, int,
                       boost::no_property>
  : public boost::no_property
{
  typedef boost::no_property next_type;
  typedef vertex_vid_t tag_type;
  typedef int value_type;

  int m_value;
};

template <>
struct boost::property<vertex_vname_t, std::string,
                       boost::property<vertex_vid_t, int> >
  : public boost::property<vertex_vid_t, int>
{
  typedef boost::property<vertex_vid_t, int> next_type;
  typedef vertex_vname_t tag_type;
  typedef std::string value_type;

  std::string m_value;
};

つまり、自分よりも一つ子供のデータ(上で定義したVertexPropertyを見ればわかるように、std::stringの一つ子供はint、intのさらに子供は無しのように)が入ったpropertyクラスを次々と継承していくようになっています(最初はno_propertyから始まりますが)。

getの戻り値の型はどう決まる？

さらに脱線しまして、Boost.Graphを使う上では全然全く知る必要がありませんが、ちょっと気になることがあるので調べてみました。

vertexについているプロパティを取得するためには、

  std::string a = boost::get(vertex_vname_t(), graph, 1);
  int         b = boost::get(vertex_vid_t(),   graph, 2);

のようなコードを書きました。このコードを良く見てみますと、引数に渡しているのはvertex_vname_t()等のenumを渡しているだけなのに、きちんと期待した戻り値の型で関数が呼ばれているようです。どうやってboost::getの戻り値の型を決めているのでしょうか。

コードを追ってみますと、同じくproperty.hppにあるpropety_value構造体で戻り値の型を求めているようです。property_valueは以下のような構造体になっています(property.hppから抜粋)。

  template <class PropertyList, class Tag>
  struct property_value {
    typedef typename detail::build_property_tag_value_alist<PropertyList>::type AList;
    typedef typename detail::extract_value<AList,Tag>::type type;
  };

どうやら、

  // 他の部分は省略...

  boost::property_value<VertexProperty, vertex_vname_t>::type ret1;
  boost::property_value<VertexProperty, vertex_vid_t>::type   ret2;  

のように書くと、ret1やret2の型をタグによって決めてくれ、ret1の型はstd::string、ret2の型はintにしてくれるようです。

もう少しproperty_valueを追ってみます。build_property_tag_value_alist<PropertyList>の部分で、PropertyListがVertexPropertyの場合の展開について確認しますと以下のようになるようです。

template <>
struct build_property_tag_value_alist<no_property>
{
  typedef no_property type;
};

template<>
struct build_property_tag_value_alist<boost::property<vertex_vid_t, int> >
{
  typedef no_property NextProperty;
  typedef int Value;
  typedef vertex_vid_t Tag;
  typedef uild_property_tag_value_alist<no_property>::value Next;

  typedef std::pair<std::pair<vertex_vid_t, int>,
                    build_property_tag_value_alist<no_property>::type> type;
};

template<>
struct build_property_tag_value_alist<boost::property<vertex_vname_t, std::string,
                                                    boost::property<vertex_vid_t, int> >
{
  typedef boost::property<vertex_vid_t, int> NextProperty;
  typedef std::string Value;
  typedef vertex_vname_t  Tag;
  typedef build_property_tag_value_alist<boost::property<vertex_vid_t, int> >::type Next;

  typedef std::pair<std::pair<vertex_vname_t, std::string>,
                    build_property_tag_value_alist<boost::property<vertex_vid_t, int> >::type> type;
};

自分よりも子供の子供のタグ(vertex_vname_tの子供はvertex_vid_t、そのさらに子供は無し)についてbuild_property_tag_value_alistを読んでいるようでした。

したがってbuild_property_tag_value_alist<PropertyList>::typeがPropetyListがVertexPropertyの場合の最終的な型は以下のようになります

std::pair<std::pair<vertex_vname_t, std::string>,
                    std::pair<std::pair<vertex_vid_t, int>,
                              no_property> > >

property_valueのもう一つのtypedefのextract_value<AList,Tag>::typeで最終的にそのタグについた型を決めています。この部分は以下のようになっています(property.hppから抜粋)。

    template <class Value, class Tag1, class Tag2, class Rest>
    struct extract_value< std::pair<std::pair<Tag1,Value>,Rest>, Tag2> {
      typedef typename extract_value<Rest,Tag2>::type type;
    };
    template <class Value, class Tag, class Rest>
    struct extract_value< std::pair<std::pair<Tag,Value>,Rest>, Tag> {
      typedef Value type;
    };

探そうとしているタグが

• pair<pair<タグがここと一致なら, Value, Rest> →そのときのValueがタグに関連する型
• pair<pair<タグがここと不一致なら, Value, Rest> →さらに深くもぐって探す

のようにやっているようです。

これで、getの戻り値の型が与えられたタグ(enum)から決まるようです。

まとめ

前半では、Boost.Graphの簡単な説明、後半では脱線して、プロパティの中身の話をかきました。

今度機会があれば、Boost.Graphのvisitorの話もしたいと思っています。

明日担当の@eagle_raptor さんもGraphの予定なようなので、私のよりも訳にたつ話が聞けると思います。