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

Boost.Graph 複数ソースの幅優先探索

C++

Boost MLで、「アンドキュメントだけど複数ソースバージョンのbreadth_first_search()あるよ」という話が出てたので、使ってみました。使い方が合ってるかはよくわからない。

namespace boost {
  template <class VertexListGraph, class SourceIterator,
            class Buffer, class BFSVisitor,
            class ColorMap>
  void breadth_first_search
    (const VertexListGraph& g,
     SourceIterator sources_begin, SourceIterator sources_end,
     Buffer& Q, BFSVisitor vis, ColorMap color);
}
#include <iostream>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/pending/queue.hpp>

enum { A,B,C,D,E, F,G,H,I,J, N };
const std::string names = "ABCDEFGHIJ";

struct custom_bfs_visitor : public boost::default_bfs_visitor {
  template <typename Vertex, typename Graph>
  void discover_vertex(Vertex u, const Graph& g) const
  {
    std::cout << names[u] << std::endl;
  }
};

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

graph make_graph1()
{
    const std::vector<std::pair<int, int>> edges = {
        {A, B},
        {B, C},
        {D, E}
    };
    return graph(edges.begin(), edges.end(), N);
}

graph make_graph2()
{
    const std::vector<std::pair<int, int>> edges = {
        {F, G},
        {G, H},
        {I, J}
    };
    return graph(edges.begin(), edges.end(), N);
}

int main()
{
    const graph g1 = make_graph1();
    const graph g2 = make_graph2();

    boost::graph_traits<graph>::vertex_iterator vi, vend;
    boost::tie(vi, vend) = boost::vertices(g2);

    custom_bfs_visitor vis;
    boost::queue<boost::graph_traits<graph>::vertex_descriptor> que;
    std::vector<boost::default_color_type> color(N, boost::white_color);
    boost::breadth_first_search(g1, vi, vend, que, vis, color.data());
}
A
B
C
D
E
F
G
H
I
J

内部で使用するキューに、pendingディレクトリのboost::queueを使ってしまってますが、内部的にstd::queueクラスにはないtop()メンバ関数を使ってるようなので、内部実装用のクラスでしょうけど仕方なく使ってます。


File Dependency Example with updates - Boost User ML