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

こんにちは。
[Boost Graph Library](http://www.boost.org/doc/libs/release/libs/graph/doc/index.html) の [depth_first_visit](https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/depth_first_visit.html) を利用し、サブグラフ（[連結グラフ](https://ja.wikipedia.org/wiki/連結グラフ)）を処理してみました。[Graph traversal](https://en.wikipedia.org/wiki/Graph_traversal) を行い、与えた始点から辿ることができるエッジを列挙しています[^1] [^2]。下記例で、始点 ```a b h``` を与え、エッジ ```0 1 2 5 6``` を得ました。エッジ ```3 4``` は辿られません。
![labels.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/54617/ecf8e6bb-9606-b81e-4408-0308967dab0e.jpeg)

[^1]: なお [depth_first_search](https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/depth_first_search.html) の方を利用すると、与えた始点から辿ることができない頂点・エッジに関わらず、辿ります（[Graph traversal](https://en.wikipedia.org/wiki/Graph_traversal)）。
[^2]: なお Go で同等なことを行ったのはこちら：「[グラフの連結成分（エッジを列挙）](https://qiita.com/kkdd/items/615c19226f30e86e79d3)」。

```console
$ 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);
}
```