グラフのエッジを辿る（depth first search、Boost Graph Library 利用）

こんにちは。
Boost Graph Library の depth_first_visit を利用し、サブグラフ（連結グラフ）を処理してみました。Graph traversal を行い、与えた始点から辿ることができるエッジを列挙しています^{1 2}。下記例で、始点 a b h を与え、エッジ 0 1 2 5 6 を得ました。エッジ 3 4 は辿られません。

$ g++ -std=c++11 -I/usr/local/include dfs_visit.cpp
$ ./a.out
number of (nodes, edges) in a graph = (8, 7)
starting nodes: a b h 
visited edges: 0 1 2 5 6 

dfs_visit.cpp

#include <vector>
#include <iostream>
#include <boost/range/adaptor/indexed.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

struct VertexProperty {
    std::string label;
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, int64_t> graph_t;

typedef graph_t::vertex_descriptor vertex_t;

struct edge {
    int F, T;  // vertices
};

enum { a, b, c, d, e, f, g, h };  // labels

graph_t make_graph() {
    graph_t graph;
    std::vector<std::string> labels = { "a", "b", "c", "d", "e", "f", "g", "h"};
    std::vector<edge> edges = {
        {a, b},
        {a, c},
        {c, b},
        {d, e},
        {e, f},
        {g, h},
        {g, h}
    };

    for(auto&& it : edges | boost::adaptors::indexed()){
        edge e = it.value();
        add_edge(e.F, e.T, it.index(), graph);
    }
    for (int i = 0; i < num_vertices(graph); i++) {
        graph[i].label = labels[i];
    }
    return graph;
}

class MyVisitor : public boost::default_dfs_visitor
{
public:
    MyVisitor(std::vector<bool>& connectedEdges)
     : edges_(connectedEdges) {}
    void initialize_vertex(vertex_t v, const graph_t& g) const {}
    void examine_edge(const graph_t::edge_descriptor &e, const graph_t &g) const {
        edges_[g[e]] = true;
    }
private:
    std::vector<bool>& edges_;
};

void print_edges(graph_t graph, std::vector<vertex_t> nodes, std::vector<bool> edges) {
    std::cout << "starting nodes: ";
    for (const auto& u : nodes) {
        std::cout << graph[u].label << " ";
    }
    std::cout << '\n';

    std::cout << "visited edges: ";
    for(auto&& it : edges | boost::adaptors::indexed()){
        if (it.value()) {
            std::cout << it.index() << " ";
        }
    }
    std::cout << '\n';
}

void visit_edges(graph_t graph) {
    std::vector<vertex_t> nodes = {a, b, h};

    std::vector<bool> edges(boost::num_edges(graph));
    MyVisitor vis(edges);
    auto indexmap = boost::get(boost::vertex_index, graph);
    auto colormap = boost::make_vector_property_map<boost::default_color_type>(indexmap);

    for (const auto& u : boost::make_iterator_range(vertices(graph))) {
        colormap[u] = boost::white_color;
        vis.initialize_vertex(u, graph);
    }

    for (const auto& u : nodes) {
      if (colormap[u] == boost::white_color) {
        boost::depth_first_visit(graph, u, vis, colormap);
      }
    }

    print_edges(graph, nodes, edges);
}

int main() {
    graph_t graph = make_graph();
    std::cout << "number of (nodes, edges) in a graph = (" << boost::num_vertices(graph);
    std::cout << ", " << boost::num_edges(graph) << ")\n";
    print_graph(graph);
    visit_edges(graph);
}

---

1. なお depth_first_search の方を利用すると、与えた始点から辿ることができない頂点・エッジに関わらず、辿ります（Graph traversal）。 ↩

2. なお Go で同等なことを行ったのはこちら：「グラフの連結成分（エッジを列挙）」。 ↩