読者です 読者をやめる 読者になる 読者になる

Boost.Graph パスを追加する

C++

Boost.Graphには、頂点を追加するadd_vertex()関数と、辺を追加するadd_edge()関数があります。
一連のパスが決まっているときにadd_edge()を繰り返し使用するのはめんどくさいので、パスを追加するadd_path()関数を書きました。


私のGitHubにあるBoost.Rangeの拡張ライブラリOvenToBoostの、fused_for_each()とadjacent_zippedを使っています。
頂点のリストから隣接頂点をタプル化したリストに変換した上で、add_edge()で辺を追加しています。
いちおう、std::initializer_list以外も受け取れるようにオーバーロードを用意してあります。

#define BOOST_RESULT_OF_USE_DECLTYPE
#include <initializer_list>
#include <boost/range/adaptor/adjacent_zipped.hpp>
#include <boost/range/algorithm_ext/fused_for_each.hpp>
#include <boost/range/value_type.hpp>
#include <boost/fusion/include/boost_tuple.hpp>

template <class Graph, class VertexList>
void add_path(Graph& g, const VertexList& vertices)
{
    typedef typename boost::range_value<VertexList>::type vertex_type;
    boost::fused_for_each(vertices | boost::adaptors::adjacent_zipped,
        [&](const vertex_type& u, const vertex_type& v) {
            add_edge(vertex(u, g), vertex(v, g), g);
        });
}

template <class Graph>
void add_path(Graph& g, std::initializer_list<int> init)
{
    add_path<Graph, decltype(init)>(g, init);
}


#include <iostream>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>

enum { A, B, C, D, N };
const std::string names = "ABCD";

int main()
{
    boost::adjacency_list<> g(N);
    add_path(g, {A, B, C});
    add_path(g, {A, D, C});

    std::ofstream file("test.dot");
    boost::write_graphviz(file, g, boost::make_label_writer(names.c_str()));
}

参考:
Graph.add_path - NetworkX