グラフ探索 breadth first search (Boost Graph Library 利用)

こんにちは。
[Boost Graph Library](http://www.boost.org/doc/libs/release/libs/graph/doc/index.html) を利用しグラフ探索（breadth first search）の経過を表示させてみました（```default_bfs_visitor``` 内）。その際、vertex_index, edge_index について vertex/edge property 内にそれらの相当物を定義し（任意の整数値付与が可能）、その値を表示させました（g[v].id、g[e].id）[^1]。

2 種類の探索（(1) と (2)）を行いましたが、探索自体は同等なので結果も同じです。ただし後半の (2) では仕組みを用意し（```MyVertices```）、この vertex_index 相当物の整数値から vertex を指定できるようにして使いやすくしてみました（```MyVertices.find()```）

[^1]: Boost Graph Library 本来の vertex_index は、自動的に vertex の vector 内の並び順の値が使われます（adjacency_list の VertexList (2番目の引数)に vecS と指定している場合）。

```console
$ g++ -std=c++11 -I/usr/local/include bfs_visitor.cpp
$ ./a.out 
vertex 0 initialize
vertex 1 initialize
vertex 2 initialize
vertex 3 initialize
vertex 4 initialize
vertex 0 discover
vertex 0 examine
edge   0 examine
edge   0 tree
vertex 1 discover
edge   1 examine
edge   1 tree
vertex 2 discover
vertex 0 finish
vertex 1 examine
edge   0 examine
edge   0 non-tree
edge   0 black target
edge   2 examine
edge   2 non-tree
edge   2 gray target
vertex 1 finish
vertex 2 examine
edge   1 examine
edge   1 non-tree
edge   1 black target
edge   2 examine
edge   2 non-tree
edge   2 black target
vertex 2 finish
```

```bfs_visitor.cpp
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

struct VertexId {
    uint64_t id;
};

struct EdgeId {
    uint64_t id;
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexId, EdgeId, boost::no_property> graph_t;

struct my_visitor : boost::default_bfs_visitor{
    void initialize_vertex(const graph_t::vertex_descriptor &v, const graph_t &g) const {
      std::cout << "vertex " << g[v].id << " initialize" << "\n";
    }
    void discover_vertex(const graph_t::vertex_descriptor &v, const graph_t &g) const {
      std::cout << "vertex " << g[v].id << " discover" << "\n";
    }
    void examine_vertex(const graph_t::vertex_descriptor &v, const graph_t &g) const {
      std::cout << "vertex " << g[v].id << " examine"  << "\n";
    }
    void finish_vertex(const graph_t::vertex_descriptor &v, const graph_t &g) const {
      std::cout << "vertex " << g[v].id << " finish"  << "\n";
    }
    void examine_edge(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "edge   " << g[e].id << " examine"  << "\n";
    }
    void tree_edge(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "edge   " << g[e].id << " tree"  << "\n";
    }
    void non_tree_edge(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "edge   " << g[e].id << " non-tree"  << "\n";
    }
    void gray_target(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "edge   " << g[e].id << " gray target"  << "\n";
    }
    void black_target(const graph_t::edge_descriptor &e, const graph_t &g) const {
      std::cout << "edge   " << g[e].id << " black target"  << "\n";
    }
  };


struct MyVertices{
private:
    std::vector<uint64_t> vertices;
public:
    size_t size() {return vertices.size();}
    uint64_t& operator[] (int i) {return vertices[i];}
    size_t find(uint64_t i) {
        return distance(vertices.begin(), std::find(vertices.begin(), vertices.end(), i));
    }
    MyVertices(std::initializer_list<int> init_list) {
        for (int i : init_list) {vertices.push_back(i);}
    }
};


int main() {
    graph_t g;
    graph_t::vertex_descriptor a, b, c, d, e, start;
// (1)
    a = add_vertex({0}, g);
    b = add_vertex({1}, g);
    c = add_vertex({2}, g);
    d = add_vertex({3}, g);
    e = add_vertex({4}, g);
	
    add_edge(a, b, {0}, g);
    add_edge(a, c, {1}, g);
    add_edge(c, b, {2}, g);
    add_edge(d, e, {3}, g);
	
    start = a;
    my_visitor vis;
    breadth_first_search(g, start, visitor(vis));
    std::cout << "\n";

// (2)
    graph_t g2;
    MyVertices verts{0, 1, 2, 3, 4};
    for (auto i = 0; i < verts.size(); i++) {
        add_vertex({verts[i]}, g2);
    }

    a = verts.find(0);
    b = verts.find(1);
    c = verts.find(2);
    d = verts.find(3);
    e = verts.find(4);

    add_edge(a, b, {0}, g2);
    add_edge(a, c, {1}, g2);
    add_edge(c, b, {2}, g2);
    add_edge(d, e, {3}, g2);
	
    start = a;
    my_visitor vis2;
    breadth_first_search(g2, start, visitor(vis2));
	
    return 0;
}
```