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