Boost.Graph property to Boost.Fusion

Boost.Graph のグラフ構造体で使用される property を fusion::for_each で使用できるようにしてみました. ソースは こちら にあげています.

property に bundle (ユーザが定義した構造体)が含まれる場合, bundle は fusion::for_each 上には現れないので注意です.

以下は使用例で, グラフを graphviz の dot 言語に書き出す際に node attributes を fusion::for_each で出力しています(attribute の名前は面倒なので typeinfo::name に使用しています).

使用例:

#include <iostream>
#include <boost/fusion/algorithm/iteration/for_each.hpp>
#include <boost/fusion/container/map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include "canard/property_sequence.hpp"

// 長い property のリスト
using vertex_property
    = boost::property<
        boost::vertex_index_t, std::size_t
    , boost::property<
        boost::vertex_color_t, std::string
    , boost::property<
        boost::vertex_name_t, std::string
    , boost::property<
        boost::vertex_rank_t, std::size_t
    >>>>;
using graph = boost::adjacency_list<boost::listS, boost::listS, boost::directedS, vertex_property>;

struct print_property
{
    explicit print_property(std::ostream& out)
        : out{out}
    {
    }

    template <class Tag, class T, class Base>
    void operator()(boost::property<Tag, T, Base>& p) const
    {
        (is_first ? out : (out << ", ")) << typeid(Tag).name() << "=" << p.m_value;
        is_first = false;
    }

    std::ostream& out;
    mutable bool is_first = true;
};

struct vertex_property_writer
{
    using all_property_map = boost::property_map<graph, boost::vertex_all_t>::type;

    template <class Vertex>
    void operator()(std::ostream& out, Vertex const v) const
    {
        // node attirbutes を出力
        out << "[";
        boost::fusion::for_each(get(all_map, v), print_property{out});
        out << "]";
    }

    all_property_map all_map;
};

int main()
{
    auto g = graph{};
    add_vertex(vertex_property{0, {"blue", {"tokyo", {2}}}}, g);
    add_vertex(vertex_property{1, {"red", {"sapporo", {1}}}}, g);
    boost::write_graphviz(std::cout, g, vertex_property_writer{get(boost::vertex_all, g)});
}

実行結果:

digraph G {
0[N5boost14vertex_index_tE=0, N5boost14vertex_color_tE=blue, N5boost13vertex_name_tE=tokyo, N5boost13vertex_rank_tE=2];
1[N5boost14vertex_index_tE=1, N5boost14vertex_color_tE=red, N5boost13vertex_name_tE=sapporo, N5boost13vertex_rank_tE=1];
}

Boost.Program_optionsで名前を持たないオプションの扱い方

Boost.Program_optionsについて調べてみたので，備忘録として．

名前を持たないオプションの対応

以下が名前を持たないオプション値の例です．オプション値hogeはoptionという名前に関連づけされていますが，huga.txtには関連づけされた名前がありません．

$ command --option=hoge huga.txt

以下のような一般的なProgram_optionsの使用方法ではhuga.txtが手に入りません．

#include <iostream>
#include <boost/program_options.hpp>

using namespace boost::program_options;

int main(int argc, char* argv[])
{
    auto desc = options_description{"options"};
    desc.add_options()
        ("option", value<std::string>(), "some option");
    auto vm = variables_map{};
    store(parse_command_line(argc, argv, desc), vm);
    notify(vm);

    if (vm.count("option")) {
        std::cout << vm["option"].as<std::string>() << std::endl;
    }
}

positional_options_descriptionを使用する方法

この場合，huga.txtを扱うには二通り方法があります． 一つ目がpositional_options_descriptionを使用する方法です．これはドキュメントにも載っている方法なので例だけ示します．

auto desc = options_description{"options"};
desc.add_options()
    ("option", value<std::string>(), "some option")
    // 名前をつけないオプションにも名前をつける
    ("unnamed-option", value<std::string>(), "unnamed option")
    ;

auto vm = variables_map{};
store(command_line_parser{argc, argv}
        .options(desc)
        .positional(
            positional_options_description{}
                // 名前の付いていないオプション一つをunnamed-optionで名前づけする
                .add("unnamed-option", 1))
        .run()
    , vm);
notify(vm);

if (vm.count("option")) {
    std::cout << vm["option"].as<std::string>() << std::endl;
}

if (vm.count("unnamed-option")) {
    std::cout << vm["unnamed-option"].as<std::string>() << std::endl;
}

ちなみにpositional_options_description::addの第二引数の整数値は，第一引数に指定した名前を持つオプション値の個数を表します． 位置を指定している訳ではありませんので注意してください．-1を指定すると個数は無制限になります．

positional_options_description{}
    .add("unnamed1", 2)
    .add("unnamed2", 1)
    .add("unnamed3", -1)
    .add("unnamed4", 2);

上記のような場合，コマンドライン上に表れる名前を持たないオプション値のうち，左から二つはunnamed1に関連づけられ，その次の一つ，さらにその次の二つはそれぞれunnamed2，unnamed4に関連づけられます．残りのオプション値はunnamed3に関連づけられることになります．

さらに.add("unnamed5", -1)と書くとunnamed3にはオプション値は一つも関連づけられず，代わりにunnamed5に関連づけられます．

collect_unrecognizedを使用する方法

positional_options_description使用する方法の欠点は，名前を必要としないオプション値に対しても名前付けする必要があることです．

名前が不要のオプションに対して名前を付けてしまうと，helpオプション等の出力にoptions_descriptionインスタンスを用いた場合，不要なオプションが見えてしまいます．Program_optionsのtutorialでは，options_descriptionの複数のインスタンスを用いることでこの問題を解決していましたが，出力と実際のparsingで使用するインスタンスが異なるのはあまりよいとは思えません．

ここでは関数collect_unrecognizedを使用して，options_descriptionインスタンスに変更を加えずに名前を持たないオプションを取得します．

collect_unrecognizedは指定したoptions_descriptorインスタンスが知らないオプションを取得する関数です（デフォルトではparserは，'-'で始まるオプションが知らないものだった場合，例外を投げるため，これを許容するようにする必要があります）．

collect_unrecognizedの第一引数はstd::vector<basic_option>であり，これはparsing結果から取得できます．

第二引数はcollect_unrecognized_mode型の値であり，include_positionalとexclude_optionalの二つの値が存在します．前者を指定すると'-'から始まらないオプションも取得することができます．

以下が例です．

auto desc = options_description{"options"};
desc.add_options()
    ("option", value<std::string>(), "some option");
auto vm = variables_map{};
// parsingの結果を保持
auto const parsing_result = parse_command_line(argc, argv, desc);
store(parsing_result, vm);
notify(vm);

if (vm.count("option")) {
    std::cout << vm["option"].as<std::string>() << std::endl;
}

std::cout << "unnamed options:" << std::endl;
// parsingの結果からoptions_descriptionに関係しないものを取得
for (auto const& str : collect_unrecognized(parsing_result.options, include_positional)) {
    std::cout << "    " << str << std::endl;
}

先読みiteratorアダプタ作ってみた

指定した値分だけiteratorが進んで見える(つまりstd::advance(it, n))ようなiteratorアダプタを作ってみました.

Boost.Rangeのslicedでも同じようなことができるのですが, このアダプタはbase()では元の場所を指したiteratorを返します. 式で書くと*it == *(it.base() + n)になります.

gist8730956

findやlower_boundなどiteratorを返すアルゴリズムで目的の値の一つ手前の要素が欲しいときに使うことを想定しました.

#include "slide_view_iterator.hpp"
#include <algorithm>
#include <boost/range/irange.hpp>
#include <iostream>

int main()
{
    auto numbers = boost::irange(0, 10);
    {
        auto it = std::lower_bound(
                canard::make_slide_view_iterator(numbers.begin(), 1)
              , canard::make_slide_view_iterator(numbers.end())
              , 9);
        std::cout << *it.base() << " is one step short of " << *it << std::endl;
    }
    {
        auto it = std::find(
                canard::make_slide_view_iterator(numbers.begin(), 2)
              , canard::make_slide_view_iterator(numbers.end())
              , 8);
        std::cout << *it.base() << " is two step short of " << *it << std::endl;
    }
}

iterator_category等のチェックは未実装です.

std::pair<Iterator, Iterator>をrange based forで使用する

C++11にはrange based forが加わり，rangeに対する走査処理を書くのが楽になりました．しかしながら，このstd::pair<Iterator, Iterator>で表されるIterator対はこのrangeには含まれません*1． そのため以下のようなコードはコンパイルエラーになります．

#include <iostream>
#include <map>

int main() {
    auto const map = std::multimap<int, int>{{2, 3}, {2, 4}, {2, 5}};
    for (auto const& entry : map.equal_range(2)) { // equal_rangeはIterator対を返す!!
        std::cout << "key: " << entry.first << " value: " << entry.second << std::endl;
    }
}

こういった場合は，Boost.Rangeのfor_eachとlambda式を組み合わせることで解決できます．

#include <iostream>
#include <map>
#include <boost/range/algorithm/for_each.hpp>

int main() {
    auto const map = std::multimap<int, int>{{2, 3}, {2, 4}, {2, 5}};
    boost::for_each(map.equal_range(2), [](std::pair<int, int> const& entry) {
        std::cout << "key: " << entry.first << " value: " << entry.second << std::endl;
    });
}

しかしながら，lambda式の引数の型名が長くなってくると，このやり方は少々面倒なことになります．特にBoost.Graphではそれが顕著になります．

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/range/algorithm/for_each.hpp>

int main() {
    boost::adjacency_list<> graph;
    // lambda式の引数の型名が長い
    boost::for_each(vertices(graph), [&](boost::graph_traits<decltype(graph)>::vertex_descriptor const v) {
        std::cout << "v index: " << get(boost::vertex_index, graph, v) << std::endl;
    });
}

こうなってくると，range based forを通した型推論を使って型名を書くのを避けたくなります．しかしながら，既に述べた通りstd::pairによるIterator対を使うとコンパイルエラーになってしまうため，そのままでは使用できません．自分でstd::pairに対するwrapperを書いてもいいですが，Boost.Rangeにiterator_rangeがあるのでこれを使用します．

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/range/algorithm/for_each.hpp>

int main() {
    boost::adjacency_list<> graph;
    // autoでOK!!
    for (auto v : boost::make_iterator_range(vertices(graph))) {
        std::cout << "v index: " << get(boost::vertex_index, graph, v) << std::endl;
    };
}

make_iterator_rangeはfiltered等のadaptorとは異なり(adaptorもiterator_rangeを使ってました)，Iteratorをコピーするので元のIterator対の寿命を気にする必要がありません(上記ではvertices(graph)が返すIterator対の寿命)*2．

まとめ

Generic lambdaサイコー!!

*1:http://stackoverflow.com/questions/6167598/why-was-pair-range-access-removed-from-c11?rq=1

*2:std::vector等のテンポラリオブジェクトを渡すのはダメです

Boost1.55でMultiple Source Dijkstra

この記事はC++ (fork) Advent Calendar 2013の22日目の記事になります．
今回も軽めの記事です．ご了承ください．

Boost1.55ではBoost.Graphの関数boost::dijkstra_shortes_pathsがマルチソースに対応しましたので，本記事ではこれを紹介します．

dijkstra_shortest_paths

関数dijkstra_shortest_pathsはその名前からも分かる通り，ダイクストラ法を用いた最短経路木を探索するためのアルゴリズムです．通常，ダイクストラ法ではスタート地点となる節点を一つ選択し，この節点から他の節点までの最短経路を求めます．

マルチソースの場合はスタート地点(ルート)となる節点が複数になります．実際に図で見てみるとこのようになります(見た目上枝の長さは違いますが，論理的にはすべて同じにしてます)．
二重線で囲まれている節点(ラベルが0, 20, 40, 60, 80の節点)がルートになります．
マルチソースダイクストラでは，ルート以外の節点vと，各ルート間のすべての最短経路が計算されるのではなく，経路距離が最小となるルートとの経路のみが計算されます．そのため図中ではルート以外の節点は経路距離が最小となるようなルートと同じ色で塗り分けしています．
この図はグラフのボロノイ分割と呼ばれ，勢力図等を作成するのに役立ちます．例えば，ルートを消防署と考えれば，ある節点で火事が起きた際にどこの消防署から消防車を出せばよいかの指標になります．

マルチソース版の実装で，シングルソース版との違いは探索開始時に優先度付きキューの中身に複数のルートがあるという点だけですので，容易に実装できます(私も昔作りました)．

上記のような図をboost::dijkstra_shortes_pathsを用いて作成するコードは以下になります．

A example of multiple source dijkstra.

ルート節点の指定

注目すべき箇所は関数multisource_dijkstra内のboost::dijkstra_shortest_pathsの呼び出しです．
第一引数はシングルソースの場合と同じで探索対象のグラフですが，第二，第三引数がルートとなる節点の集合を示すイテレータペアになっています(Rangeで渡したいですね!!)．シングルソースの場合は，第二引数にルートとなる節点一つを指定していた場合とは異なります．それ以外の引数はシングルソースの場合と同じです．

各節点から最短のルートの記録

ここではparent_recorderという名前のEventVisitorを新たに作成しています(root_recorderという名前にすればよかった)．これは新たに探索された節点がどのルートから探索されたかを記憶します．親(predecessorであってparentではない)のルートを自節点のルートに設定するだけです．あらかじめルートとなる節点のルートをその節点に設定しておく必要はありますが，そこは我慢します．

void operator()(Edge const e, Graph const& g) const {
    auto value = get(parent_map_, source(e, g));
    put(parent_map_, target(e, g), value);
}

getとputを合わせて一行にせずにわざわざgetで取得した値をコピーしているのは，put時にparent_map_の内部で保持するvectorのresize()が呼ばれてgetで取得した値が破棄されるのを防ぐためです(というか一行で書いて嵌りました)．

引数の数

上記のdijkstra_shortes_pathsの呼び出しでは12個の引数を指定していますが，これらを省略することはできません．
通常Boost.Graphの関数はdjikstra_shortest_pathsも含め，Named Parameter Idiomを用いた名前付き引数によってデフォルト引数を持つパラメータに対して引数を指定する必要はありません．しかしながら，マルチソースの場合名前付き引数を持つオーバロードが一つもないので，すべての引数を指定する必要があります(さらにVertexColorMapを指定するオーバロードならありました．これで引数の数は13個!!)．
使い勝手はかなり悪いので，名前付き引数版をオーバロード可能かどうか調査して追加するか独自にラッパを作成する必要がありそうです．

グラフの視覚化

出力されたファイルはgraphvizを使えばいい感じにレイアウトしてくれます.

fdp -Nstyle=filled -Nshape=circle -Nperipheries=peripheries -Tpng -O graph.dot

まとめ

マルチソースダイクストラは現状undocumentedですが，シングルソース版の使い方が分かっていれば使用方法が分からないことはないと思います．また，Boost1.55ではダイクストラだけではなく，幅優先探索もマルチソースに対応しているので利用してみるといいかもしれません(今回の例では枝の長さがすべて等しいので本当はこっちを使うべきでした)．

アルゴリズムとか意味がなかった

https://paiza.jp/poh/ec-campaign に挑戦してみましたので，そのコードを載せておきます．

#include <iostream>
#include <vector>
#include <algorithm>

template <class Iterator>
inline int calc(Iterator const first, Iterator const last, int const value)
{
    if (*(last - 1) + *(last - 2) <= value) {
        return *(last - 1) + *(last - 2);
    }
    Iterator upper = std::lower_bound(first + 1, last, value / 2);
    if (upper + 1 != last && *upper + *(upper + 1) == value) {
        return value;
    }
    int best_price = 0;
    for (Iterator lower = std::upper_bound(first, upper, value - *upper);
         lower != first && upper != last;
         lower = std::upper_bound(first, lower - 1, value - *upper)) {
        upper = std::upper_bound(upper + 1, last, value - *(lower - 1));
        best_price = std::max(best_price, *(upper - 1) + *(lower - 1));
        if (best_price == value) {
            break;
        }
    }
    return best_price;
}

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    int N, D;
    std::cin >> N >> D;
    std::vector<int> prices;
    prices.reserve(N);
    for (int i = 0; i < N; ++i) {
        int p;
        std::cin >> p;
        prices.push_back(p);
    }
    std::sort(prices.begin(), prices.end());
    for (int i = 0; i < D; ++i) {
        int m;
        std::cin >> m;
        std::cout << calc(prices.begin(), prices.end(), m) << '\n';
    }
}

結果は http://paiza.jp/poh/ec-campaign/result/16051cf4bd6d13df012bc008d1fdad13 です．case3は0.13secでした．

boost::adjacency_listのVertexListテンプレート引数とvertex_indexの関係

id:faith_and_brave:20131003:1380788496に関して少しばかし補足.

まず，知るべきことはboost::adjaceny_listのテンプレート引数を省略した場合である．この場合，以下の引数を指定したものとして扱われる．

boost::adjacency_list<
    boost::vecS,		// OutEdgeList
    boost::vecS,		// VertexList
    boost::directedS,	// Directed
    boost::no_property,	// VertexProperty
    boost::no_property,	// EdgeProperty
    boost::no_property,	// GraphProperty
    boost::listS		// EdgeList
>

ここでは各引数の詳細は説明しないが，ここで注目していただきたいのは2番目のVertexListとコメントしたテンプレート引数である．

このVertexListテンプレート引数にはグラフの節点（Vertex）を格納するコンテナを指定する．デフォルトではvecSとなっており，これはstd::vectorに対応している．ここで注意して頂きたいことはVertexListがvecSの場合，adjaceny_listは自動的に各節点にindex番号が割り当てられたIndexedGraph*1になるということである．

このときもう一つ注意すべきことは，このIndexedGraphではindexの値が自動で割り振られ，外部からは変更不可能ということである．このときの節点のindex値は[0, num_vertices(g))中の値に一対一に対応する（gはadjacency_listのオブジェクトである）．つまり，indexに任意の値を割り当てることができないことになる．

よって，VertexListがvecSでない場合はデフォルトではIndexedGraphにならない．以下のコードはエラーになる．

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/counting_range.hpp>

int main()
{
    using Graph = boost::adjacency_list<
        boost::listS,
        boost::listS,		// VertexListはlistS
        boost::directedS,
        boost::no_property	// VertexPropertyはなし
	>;

    Graph g;
    for (auto i : boost::counting_range(0, 5)) {
        add_vertex(g);
    }

    using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
    boost::for_each(vertices(g), [&](Vertex const v) {
        std::cout << get(boost::vertex_index, g, v) << std::endl;	// error gはIndexedGraphではない
    });
}

この場合，以下のように手動でグラフにindexを持たせる必要がある．

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/counting_range.hpp>

int main()
{
    using IndexProp = boost::property<boost::vertex_index_t, std::size_t>;
    using Graph = boost::adjacency_list<
        boost::listS,
        boost::listS,	// VertexListはListS
        boost::directedS,
        IndexProp	// VertexPropertyはvertex_indexを持つproperty
    >;

    Graph g;
    for (auto i : boost::counting_range(0, 5)) {
        add_vertex(IndexProp(i * 2), g);	// ついでなのでindexを2の倍数とする
    }

    using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
    boost::for_each(vertices(g), [&](Vertex const v) {
        std::cout << get(boost::vertex_index, g, v) << std::endl;
    });
}

ここではadjacency_listのVertexPropertyにvertex_indexを持つpropertyを指定した．これにより，get(boost::vertex_index, g, v)で節点vからindexを取得することが可能となる．

また，ここでは関数add_vertexの呼び出し時に各節点のindexの値を設定している．

実際はvertex_indexの値は上記のような不連続な値にせず，[0, num_vertices(g))に対応するように割り当てるべきである*2．こういったindex付けをしたい場合は，vertex_indexの代わりにvertex_index1やvertex_index2が用意されているのでこちらを用いるとよい．

*1:公式にはこのような呼び方はない

*2:この理由についてはいつか述べるかもしれない