EventVisitorList Concept

An EventVisitorList is either an EventVisitor, or a list of EventVisitors combined using std::pair. Each graph algorithm defines visitor adaptors that convert an EventVisitorList into the particular kind of visitor needed by the algorithm. In the following example we will show how to combine event visitors into a list using std::pair and how to use an algorithm's visitor adaptor class.

Suppose we would like to print out the parenthesis structure of the discover/finish times of vertices in a depth-first search. We can use the BGL algorithm depth_first_search() and two event visitors to accomplish this. The complete source code for the following example is in examples/dfs_parenthesis.cpp. First we define the two event visitors. We use on_discover_vertex and on_finish_vertex as the event points, selected from the list of event points specified in DFSVisitor.

struct open_paren : public base_visitor<open_paren> {
  typedef on_discover_vertex event_filter;
  template <class Vertex, class Graph>
  void operator()(Vertex v, Graph& G) {
    std::cout << "(" << v;
  }
};
struct close_paren : public base_visitor<close_paren> {
  typedef on_finish_vertex event_filter;
  template <class Vertex, class Graph>
  void operator()(Vertex v, Graph& G) {
    std::cout << v << ")";
  }
};

Next we create two event visitor objects and make an EventVisitorList out of them using a std::pair which created by std::make_pair.

std::make_pair(open_paren(), close_paren())

Next we want to pass this list into depth_first_search(), but depth_first_search() is expecting a DFSVisitor, not a EventVisitorList. We therefore use the dfs_visitor adaptor which turns an EventVisitor list into a DFSVisitor. Like all of the visitor adaptors, dfs_visitor has a creation function called make_dfs_visitor().

make_dfs_visitor(std::make_pair(open_paren(), close_paren()))

Now we can pass the resulting visitor object into depth_first_search() as follows.

  // graph object G is created ...

  std::vector<default_color_type> color(num_vertices(G));

  depth_first_search(G, make_dfs_visitor(std::make_pair(open_paren(), close_paren())),
                     color.begin());

For creating a list of more than two event visitors, you can nest calls to std::make_pair in the following way:

std::make_pair(visitor1,
  std::make_pair(visitor2,
    ...
    std::make_pair(visitorN-1, visitorN)...));

EventVisitorList Concept

See Also