Modified form of "example/dfs-example.cpp" code (https://github.com/boostorg/graph/blob/master/example/dfs-example.cpp) showing DFS with visitors

Boost_Reference_Manual_Page_173_code.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 TimeMap > class dfs_time_visitor:public boost::default_dfs_visitor {
  typedef typename boost::property_traits < TimeMap >::value_type T;
public:
  // I think the following 3 lines are referring to this "  :  m_dtimemap(dmap), m_ftimemap(fmap), m_time(t) "
  TimeMap m_dtimemap;
  TimeMap m_ftimemap;
  T & m_time;

  // Constructor of our custom visitor
  dfs_time_visitor(TimeMap dmap, TimeMap fmap, T & t)  :  m_dtimemap(dmap), m_ftimemap(fmap), m_time(t) {
  }

  // discover_vertex template
  template < typename Vertex, typename Graph >
    void discover_vertex(Vertex u, const Graph & g) const
  {
    put(m_dtimemap, u, m_time++);
  }

  // finish_vertex template
  template < typename Vertex, typename Graph >
    void finish_vertex(Vertex u, const Graph & g) const
  {
    put(m_ftimemap, u, m_time++);
  }
};


int
main()
{
  // Select the graph type we wish to use
  typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS > DirectedGraph;
  // This type is a representation of the number of vertices in the graph
  typedef boost::graph_traits < DirectedGraph >::vertices_size_type size_type;
  // Set up the vertex names
  enum
  { u, v, w, x, y, z, N };
  char name[] = { 'u', 'v', 'w', 'x', 'y', 'z' };
  // Specify the edges in the graph
  typedef std::pair < int, int >E;
  E edge_array[] = { E(u, v), E(u, x), E(x, v), E(y, x),
    E(v, y), E(w, y), E(w, z), E(z, z)
  };

  DirectedGraph digraph(N);
  // Populating the edges in the graph
  for (std::size_t j = 0; j < sizeof(edge_array) / sizeof(E); ++j)
    add_edge(edge_array[j].first, edge_array[j].second, digraph);

  // discover time and finish time properties
  std::vector < size_type > discovertime(num_vertices(digraph));
  std::vector < size_type > finishtime(num_vertices(digraph));
  
  // Imp Point: distance_map, predecessor_map, vertex_index_map, all type of maps is defined like " get(____, g) "

  // The following 4 lines are difficult to understand but the idea is to create discover and finish property map obj.
  // iterator_property_map is a default of color_map, so basically we are making a color map here.
  typedef boost::iterator_property_map<std::vector<size_type>::iterator,
		  boost::property_map<DirectedGraph, boost::vertex_index_t>::const_type> time_propertymap_type;
  time_propertymap_type discovertime_propertymap(discovertime.begin(), get(boost::vertex_index, digraph));
  time_propertymap_type finishtime_propertymap(finishtime.begin(), get(boost::vertex_index, digraph));

  size_type t = 0;

  // Creating the obj for our custom dfs visitor
  dfs_time_visitor < time_propertymap_type > vis(discovertime_propertymap, finishtime_propertymap, t);

  // Running DFS function
  boost::depth_first_search(digraph, boost::visitor(vis));

  // ------------------ The following codes are just to represent the results -----------------------------

  // use std::sort to order the vertices by their discover time
  std::vector < size_type > discover_order(N);
  boost::integer_range < size_type > r(0, N);
  std::copy(r.begin(), r.end(), discover_order.begin());
  std::sort(discover_order.begin(), discover_order.end(),
		  boost::indirect_cmp < time_propertymap_type, std::less < size_type > >(discovertime_propertymap));
  std::cout << "order of discovery: ";
  int i;
  for (i = 0; i < N; ++i)
    std::cout << name[discover_order[i]] << " ";

  std::vector < size_type > finish_order(N);
  std::copy(r.begin(), r.end(), finish_order.begin());
  std::sort(finish_order.begin(), finish_order.end(),
		  boost::indirect_cmp < time_propertymap_type, std::less < size_type > >(finishtime_propertymap));
  std::cout << std::endl << "order of finish: ";
  for (i = 0; i < N; ++i)
    std::cout << name[finish_order[i]] << " ";
  std::cout << std::endl;

  return EXIT_SUCCESS;
}