ceph/src/boost/libs/graph/example/visitor.cpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9 //
  10 //  Sample output
  11 //
  12 // DFS categorized directed graph
  13 // tree: 0 --> 2
  14 // tree: 2 --> 1
  15 // back: 1 --> 1
  16 // tree: 1 --> 3
  17 // back: 3 --> 1
  18 // tree: 3 --> 4
  19 // back: 4 --> 0
  20 // back: 4 --> 1
  21 // forward or cross: 2 --> 3
  22
  23 // BFS categorized directed graph
  24 // tree: 0 --> 2
  25 // tree: 2 --> 1
  26 // tree: 2 --> 3
  27 // cycle: 1 --> 1
  28 // cycle: 1 --> 3
  29 // cycle: 3 --> 1
  30 // tree: 3 --> 4
  31 // cycle: 4 --> 0
  32 // cycle: 4 --> 1
  33
  34 #include <boost/config.hpp>
  35 #include <iostream>
  36 #include <vector>
  37 #include <algorithm>
  38 #include <utility>
  39 #include <string>
  40
  41 #include <boost/graph/visitors.hpp>
  42 #include <boost/graph/graph_utility.hpp>
  43 #include <boost/graph/adjacency_list.hpp>
  44 #include <boost/graph/breadth_first_search.hpp>
  45 #include <boost/graph/depth_first_search.hpp>
  46
  47 using namespace boost;
  48 using namespace std;
  49
  50 template < class Tag >
  51 struct edge_printer : public base_visitor< edge_printer< Tag > >
  52 {
  53     typedef Tag event_filter;
  54     edge_printer(std::string edge_t) : m_edge_type(edge_t) {}
  55     template < class Edge, class Graph > void operator()(Edge e, Graph& G)
  56     {
  57         std::cout << m_edge_type << ": " << source(e, G) << " --> "
  58                   << target(e, G) << std::endl;
  59     }
  60     std::string m_edge_type;
  61 };
  62 template < class Tag > edge_printer< Tag > print_edge(std::string type, Tag)
  63 {
  64     return edge_printer< Tag >(type);
  65 }
  66
  67 int main(int, char*[])
  68 {
  69
  70     using namespace boost;
  71
  72     typedef adjacency_list<> Graph;
  73     typedef std::pair< int, int > E;
  74     E edges[] = { E(0, 2), E(1, 1), E(1, 3), E(2, 1), E(2, 3), E(3, 1), E(3, 4),
  75         E(4, 0), E(4, 1) };
  76 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
  77     Graph G(5);
  78     for (std::size_t j = 0; j < sizeof(edges) / sizeof(E); ++j)
  79         add_edge(edges[j].first, edges[j].second, G);
  80 #else
  81     Graph G(edges, edges + sizeof(edges) / sizeof(E), 5);
  82 #endif
  83
  84     typedef boost::graph_traits< Graph >::vertices_size_type size_type;
  85
  86     std::vector< size_type > d(num_vertices(G));
  87     std::vector< size_type > f(num_vertices(G));
  88
  89     cout << "DFS categorized directed graph" << endl;
  90     depth_first_search(G,
  91         visitor(make_dfs_visitor(make_list(print_edge("tree", on_tree_edge()),
  92             print_edge("back", on_back_edge()),
  93             print_edge("forward or cross", on_forward_or_cross_edge())))));
  94
  95     cout << endl << "BFS categorized directed graph" << endl;
  96     boost::breadth_first_search(G, vertex(0, G),
  97         visitor(
  98             make_bfs_visitor(std::make_pair(print_edge("tree", on_tree_edge()),
  99                 print_edge("cycle", on_non_tree_edge())))));
 100
 101     return 0;
 102 }