ceph/src/boost/libs/graph_parallel/test/distributed_dfs_test.cpp

   1 //=======================================================================
   2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
   3 // Copyright 2004 Douglas Gregor
   4 // Copyright (C) 2006-2008
   5
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //=======================================================================
  10 #include <boost/graph/use_mpi.hpp>
  11 #include <boost/config.hpp>
  12 #include <boost/throw_exception.hpp>
  13 #include <boost/serialization/vector.hpp>
  14 #include <boost/graph/depth_first_search.hpp>
  15 #include <boost/graph/distributed/mpi_process_group.hpp>
  16 #include <boost/graph/distributed/adjacency_list.hpp>
  17 #include <boost/test/minimal.hpp>
  18 #include <iostream>
  19
  20 #ifdef BOOST_NO_EXCEPTIONS
  21 void
  22 boost::throw_exception(std::exception const& ex)
  23 {
  24     std::cout << ex.what() << std::endl;
  25     abort();
  26 }
  27 #endif
  28
  29 using namespace boost;
  30 using boost::graph::distributed::mpi_process_group;
  31
  32 // Set up the vertex names
  33 enum vertex_id_t { u, v, w, x, y, z, N };
  34 char vertex_names[] = { 'u', 'v', 'w', 'x', 'y', 'z' };
  35
  36 template<typename Vertex, typename Graph>
  37 char get_vertex_name(Vertex v,  const Graph& g)
  38 {
  39   return vertex_names[g.distribution().global(owner(v), local(v))];
  40 }
  41
  42 struct printing_dfs_visitor
  43 {
  44   template<typename Vertex, typename Graph>
  45   void initialize_vertex(Vertex v, const Graph& g)
  46   {
  47     vertex_event("initialize_vertex", v, g);
  48   }
  49
  50   template<typename Vertex, typename Graph>
  51   void start_vertex(Vertex v, const Graph& g)
  52   {
  53     vertex_event("start_vertex", v, g);
  54   }
  55
  56   template<typename Vertex, typename Graph>
  57   void discover_vertex(Vertex v, const Graph& g)
  58   {
  59     vertex_event("discover_vertex", v, g);
  60   }
  61
  62   template<typename Edge, typename Graph>
  63   void examine_edge(Edge e, const Graph& g)
  64   {
  65     edge_event("examine_edge", e, g);
  66   }
  67
  68   template<typename Edge, typename Graph>
  69   void tree_edge(Edge e, const Graph& g)
  70   {
  71     edge_event("tree_edge", e, g);
  72   }
  73
  74   template<typename Edge, typename Graph>
  75   void back_edge(Edge e, const Graph& g)
  76   {
  77     edge_event("back_edge", e, g);
  78   }
  79
  80   template<typename Edge, typename Graph>
  81   void forward_or_cross_edge(Edge e, const Graph& g)
  82   {
  83     edge_event("forward_or_cross_edge", e, g);
  84   }
  85
  86   template<typename Vertex, typename Graph>
  87   void finish_vertex(Vertex v, const Graph& g)
  88   {
  89     vertex_event("finish_vertex", v, g);
  90   }
  91
  92 private:
  93   template<typename Vertex, typename Graph>
  94   void vertex_event(const char* name, Vertex v, const Graph& g)
  95   {
  96     std::cerr << "#" << process_id(g.process_group()) << ": " << name << "("
  97               << get_vertex_name(v, g) << ": " << local(v) << "@" << owner(v)
  98               << ")\n";
  99   }
 100
 101   template<typename Edge, typename Graph>
 102   void edge_event(const char* name, Edge e, const Graph& g)
 103   {
 104     std::cerr << "#" << process_id(g.process_group()) << ": " << name << "("
 105               << get_vertex_name(source(e, g), g) << ": "
 106               << local(source(e, g)) << "@" << owner(source(e, g)) << ", "
 107               << get_vertex_name(target(e, g), g) << ": "
 108               << local(target(e, g)) << "@" << owner(target(e, g)) << ")\n";
 109   }
 110
 111 };
 112
 113 void
 114 test_distributed_dfs()
 115 {
 116   typedef adjacency_list<listS,
 117                          distributedS<mpi_process_group, vecS>,
 118                          undirectedS,
 119                          // Vertex properties
 120                          property<vertex_color_t, default_color_type> >
 121     Graph;
 122   typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 123
 124   // Specify the edges in the graph
 125   typedef std::pair<int, int> E;
 126   E edge_array[] = { E(u, v), E(u, w), E(u, x), E(x, v), E(y, x),
 127                      E(v, y), E(w, y), E(w, z), E(z, z) };
 128   Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(E), N);
 129
 130   std::vector<vertex_descriptor> parent(num_vertices(g));
 131   std::vector<vertex_descriptor> explore(num_vertices(g));
 132
 133   boost::graph::tsin_depth_first_visit
 134     (g,
 135      vertex(u, g),
 136      printing_dfs_visitor(),
 137      get(vertex_color, g),
 138      make_iterator_property_map(parent.begin(), get(vertex_index, g)),
 139      make_iterator_property_map(explore.begin(), get(vertex_index, g)),
 140      get(vertex_index, g));
 141
 142 #if 0
 143   std::size_t correct_parents1[N] = {u, u, y, y, v, w};
 144   std::size_t correct_parents2[N] = {u, u, y, v, x, w};
 145 #endif
 146
 147   for (std::size_t i = 0; i < N; ++i) {
 148     vertex_descriptor v = vertex(i, g);
 149     if (owner(v) == process_id(g.process_group())) {
 150       std::cout  << "parent(" << get_vertex_name(v, g) << ") = "
 151                  << get_vertex_name(parent[v.local], g) << std::endl;
 152
 153     }
 154   }
 155
 156   if (false) {
 157     depth_first_visit(g, vertex(u, g), printing_dfs_visitor());
 158   }
 159 }
 160
 161 int
 162 test_main(int argc, char* argv[])
 163 {
 164   mpi::environment env(argc, argv);
 165   test_distributed_dfs();
 166   return 0;
 167 }