Testing the boost::depth_first_search algorithm with visitor

readme.md

Make sure that boost is installed locally.

To compile and run the file, execute the following commands:

g++ boost-dfs.cpp -o boost-dfs
./boost-dfs

boost-dfs-2.cpp

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/range/irange.hpp>
#include <boost/pending/indirect_cmp.hpp>

#include <iostream>

template <typename V, typename E, typename G>
class Dfs_visitor : public boost::default_dfs_visitor {
 public:
     Dfs_visitor(
             V root,
             std::vector<boost::default_color_type> &colors,
             G &graph) :
         m_roots(root),
         m_colors(colors),
         m_graph(graph),
         time(0),
         depth(0) {}
     template <typename B_G>
         void initialize_vertex(V v, const B_G&) {
             std::cout << "initialize vertex " << v << "\n";
         }
     template <typename B_G>
         void start_vertex(V v, const B_G&) {
             std::cout << "color " << m_colors[v] << "\n";
             std::cout << "start vertex " << v << "\n";
         }
     template <typename B_G>
         void discover_vertex(V v, const B_G&) {
             std::cout << "color " << m_colors[v] << "\n";
             std::cout << "\ntime " << time++ << "\n";
             std::cout << "discover vertex " << v << "\n";
         }
     template <typename B_G>
         void examine_edge(E e, const B_G&) {
             std::cout << "examine edge " << e << "\n";
         }
     template <typename B_G>
         void tree_edge(E e, const B_G&) {
             std::cout << "tree edge " << e << "\n";
             depth++;
             edge_set.insert(e);
             std::cout << "depth " << depth << "\n";
         }
     template <typename B_G>
         void back_edge(E e, const B_G&) {
             std::cout << "back edge " << e << "\n";
         }
     template <typename B_G>
         void forward_or_cross_edge(E e, const B_G&) {
             std::cout << "forward or cross edge " << e << "\n";
         }
     template <typename B_G>
         void finish_edge(E e, const B_G&) {
             std::cout << "finish edge " << e << "\n";
             if (edge_set.find(e) != edge_set.end()) {
                 depth--;
                 std::cout << "depth " << depth << "\n";
             }
         }
     template <typename B_G>
         void finish_vertex(V v, const B_G&) {
             // The color of the node is printed as 0 always
             std::cout << "color " << m_colors[v] << "\n";
             std::cout << "finish vertex " << v << "\n";
         }

 private:
     V m_roots;
     std::vector<boost::default_color_type> m_colors;
     G &m_graph;
     int64_t time;
     int64_t depth;
     std::set<E> edge_set;
};



int main() {
    typedef boost::adjacency_list <boost::vecS, boost::vecS, boost::directedS> G;
    typedef typename boost::graph_traits <G>::vertex_descriptor V;
    typedef typename boost::graph_traits <G>::edge_descriptor E;

    enum { v1, v2, v3, v4, v5, v6, v7, v8, v9, N };


    typedef std::pair < V, V > Edge;
    Edge edge_array[] = { Edge(v1, v2), Edge(v2, v1), Edge(v3, v2), Edge(v4, v3),
                          Edge(v2, v5), Edge(v5, v2), Edge(v3, v6), Edge(v7, v8),
                          Edge(v8, v7), Edge(v5, v8), Edge(v8, v5), Edge(v5, v6),
                          Edge(v6, v5), Edge(v6, v9), Edge(v9, v6), Edge(v9, v4),
                          Edge(v4, v9)
                        };

    G graph(N);
    for (std::size_t j = 0; j < sizeof(edge_array) / sizeof(Edge); ++j)
        add_edge(edge_array[j].first, edge_array[j].second, graph);

    using dfs_visitor = Dfs_visitor<V, E, G>;

    V root = v1;

    // Here we use std::vector as exterior property storage.
    std::vector<boost::default_color_type> colors(boost::num_vertices(graph));

    auto vis =  dfs_visitor(root, colors, graph);
    auto i_map = get(boost::vertex_index, graph);
    auto color_map = boost::make_iterator_property_map(colors.begin(), i_map);

#if 1
    boost::depth_first_search(graph, vis, color_map, root);
#endif

    // The color of all the nodes is printed as 4
    typename boost::graph_traits < G > ::vertex_iterator v, vend;
    boost::tie(v, vend) = boost::vertices(graph);
    for (boost::tie(v, vend) = boost::vertices(graph); v != vend; ++v) {
        int64_t node = *v;
        int64_t color = colors[*v];
        std::cout << "node " << node << ", color " << color << "\n";
    }

#if 0
    // Named parameter version
    boost::depth_first_search(graph,
                    boost::root_vertex(v1)
                    .visitor(vis)
                    .color_map(color_map)
    );
#endif

    return 0;
}

boost-dfs.cpp

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/range/irange.hpp>
#include <boost/pending/indirect_cmp.hpp>

#include <iostream>
using namespace boost;


template <typename V, typename E, typename G>
class Dfs_visitor : public boost::default_dfs_visitor {
 public:
     Dfs_visitor(
             V root,
             std::vector<E> &data,
             boost::associative_property_map<std::map<E, boost::default_color_type>> &colors,
             G &graph) :
         m_data(data),
         m_roots(root),
         m_colors(colors),
         m_graph(graph),
         time(0),
         depth(0) {}
     template <typename B_G>
         void initialize_vertex(V v, const B_G&) {
             std::cout << "initialize vertex " << v << "\n";
         }
     template <typename B_G>
         void start_vertex(V v, const B_G&) {
             std::cout << "start vertex " << v << "\n";
         }
     template <typename B_G>
         void discover_vertex(V v, const B_G&) {
             std::cout << "\ntime " << time++ << "\n";
             std::cout << "discover vertex " << v << "\n";
         }
     template <typename B_G>
         void examine_edge(E e, const B_G&) {
             std::cout << "color " << m_colors[e] << "\n";
             std::cout << "examine edge " << e << "\n";
         }
     template <typename B_G>
         void tree_edge(E e, const B_G&) {
             std::cout << "tree edge " << e << "\n";
             std::cout << "color " << m_colors[e] << "\n";
             depth++;
             edge_set.insert(e);
             std::cout << "depth " << depth << "\n";
         }
     template <typename B_G>
         void back_edge(E e, const B_G&) {
             std::cout << "back edge " << e << "\n";
         }
     template <typename B_G>
         void forward_or_cross_edge(E e, const B_G&) {
             std::cout << "forward or cross edge " << e << "\n";
         }
     template <typename B_G>
         void finish_edge(E e, const B_G&) {
             std::cout << "finish edge " << e << "\n";
             std::cout << "color " << m_colors[e] << "\n";
             if (edge_set.find(e) != edge_set.end()) {
                 depth--;
                 std::cout << "depth " << depth << "\n";
             }
         }
     template <typename B_G>
         void finish_vertex(V v, const B_G&) {
             std::cout << "finish vertex " << v << "\n";
         }

 private:
     std::vector<E> &m_data;
     V m_roots;
     boost::associative_property_map<std::map<E, boost::default_color_type>> m_colors;
     G &m_graph;
     int64_t time;
     int64_t depth;
     std::set<E> edge_set;
};



int main() {
    typedef adjacency_list < vecS, vecS, directedS > G;
    typedef graph_traits < G >::vertices_size_type size_type;
    typedef typename boost::graph_traits < G >::vertex_descriptor V;
    typedef typename boost::graph_traits < G >::edge_descriptor E;

    enum { v1, v2, v3, v4, v5, v6, v7, v8, v9, N };
    typedef std::pair < int, int > edge;
    edge edge_array[] = { edge(v1, v2), edge(v2, v1), edge(v3, v2), edge(v4, v3),
                          edge(v2, v5), edge(v5, v2), edge(v3, v6), edge(v7, v8),
                          edge(v8, v7), edge(v5, v8), edge(v8, v5), edge(v5, v6),
                          edge(v6, v5), edge(v6, v9), edge(v9, v6), edge(v9, v4),
                          edge(v4, v9)
                        };
    G graph(N);
    for (std::size_t j = 0; j < sizeof(edge_array) / sizeof(edge); ++j)
        add_edge(edge_array[j].first, edge_array[j].second, graph);

    using dfs_visitor = Dfs_visitor<V, E, G>;

    V root = v1;
    std::vector<E> visited_order;
    std::map<E, boost::default_color_type> edge_color;
    boost::associative_property_map<std::map<E, boost::default_color_type>> colors(boost::make_assoc_property_map(edge_color));
    depth_first_search(graph,
                       visitor(dfs_visitor(root, visited_order, colors, graph))
                       .edge_color_map(&colors)
                       .root_vertex(root));

    return 0;
}