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

Boost.Graph 入辺と出辺

C++

こういうグラフがあったとき、頂点Dへの入辺、頂点Dからの出辺を抽出してみます。


#include <iostream>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/spirit/home/phoenix/algorithm.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS> Graph;
typedef std::pair<int, int> Edge;

enum { A, B, C, D, E, F, G, N };
const std::string name = "ABCDEFG";

template <class Graph, class Name>
struct print_edge_t {
    print_edge_t(const Graph& g, const Name& name) : graph_(g), name_(name) {}

    template <class Edge>
    void operator()(const Edge& edge) const
    {
        print(boost::source(edge, graph_), boost::target(edge, graph_));
    }

private:
    template <class Vertex>
    void print(const Vertex& src, const Vertex& target) const
    {
        std::cout << "  (" << name_[src] << "," << name_[target] << ")" << std::endl;
    }

    const Graph& graph_;
    const Name& name_;
};

template <class Graph, class Name>
print_edge_t<Graph, Name> print_edge(const Graph& g, const Name& name)
{
    return print_edge_t<Graph, Name>(g, name);
}

int main()
{
    const std::vector<Edge> edges = {
        {A, D}, {B, D}, {C, D},
        {D, E}, {D, F}, {D, G}
    };

    const Graph g(edges.begin(), edges.end(), N);

    std::cout << "in-edges:" << std::endl;
    boost::phoenix::for_each(boost::in_edges(D, g), print_edge(g, name))();

    std::cout << "out-edges:" << std::endl;
    boost::phoenix::for_each(boost::out_edges(D, g), print_edge(g, name))();
}
in-edges:
  (A,D)
  (B,D)
  (C,D)
out-edges:
  (D,E)
  (D,F)
  (D,G)

boost::in_edges, boost::out_edgesに渡すグラフはbidirectionalSでないといけないようです。
directedSだとコンパイルエラーになりました。