ceph/src/boost/libs/graph/example/dfs_parenthesis.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 //  DFS parenthesis:
  12 //  (0(2(3(4(11)4)3)2)0)
  13
  14 #include <boost/config.hpp>
  15 #include <assert.h>
  16 #include <iostream>
  17
  18 #include <vector>
  19 #include <algorithm>
  20 #include <utility>
  21
  22 #include "boost/graph/visitors.hpp"
  23 #include "boost/graph/adjacency_list.hpp"
  24 #include "boost/graph/breadth_first_search.hpp"
  25 #include "boost/graph/depth_first_search.hpp"
  26
  27 using namespace boost;
  28 using namespace std;
  29
  30 struct open_paren : public base_visitor<open_paren> {
  31   typedef on_discover_vertex event_filter;
  32   template <class Vertex, class Graph>
  33   void operator()(Vertex v, Graph&) {
  34     std::cout << "(" << v;
  35   }
  36 };
  37 struct close_paren : public base_visitor<close_paren> {
  38   typedef on_finish_vertex event_filter;
  39   template <class Vertex, class Graph>
  40   void operator()(Vertex v, Graph&) {
  41     std::cout << v << ")";
  42   }
  43 };
  44
  45
  46 int
  47 main(int, char*[])
  48 {
  49
  50   using namespace boost;
  51
  52   typedef adjacency_list<> Graph;
  53   typedef std::pair<int,int> E;
  54   E edge_array[] = { E(0, 2),
  55                 E(1, 1), E(1, 3),
  56                 E(2, 1), E(2, 3),
  57                 E(3, 1), E(3, 4),
  58                 E(4, 0), E(4, 1) };
  59 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
  60   Graph G(5);
  61   for (std::size_t j = 0; j < sizeof(edge_array) / sizeof(E); ++j)
  62     add_edge(edge_array[j].first, edge_array[j].second, G);
  63 #else
  64   Graph G(edge_array, edge_array + sizeof(edge_array)/sizeof(E), 5);
  65 #endif
  66
  67   std::cout << "DFS parenthesis:" << std::endl;
  68   depth_first_search(G, visitor(make_dfs_visitor(std::make_pair(open_paren(),
  69                                                         close_paren()))));
  70   std::cout << std::endl;
  71   return 0;
  72 }
  73