Boost.Graph 複数ソースの幅優先探索
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