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

   1 // Copyright 2004 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Douglas Gregor
   8 //           Andrew Lumsdaine
   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/distributed/dehne_gotz_min_spanning_tree.hpp>
  15 #include <boost/graph/distributed/mpi_process_group.hpp>
  16 #include <boost/graph/distributed/vertex_list_adaptor.hpp>
  17 #include <boost/graph/parallel/distribution.hpp>
  18 #include <boost/test/minimal.hpp>
  19 #include <boost/graph/distributed/adjacency_list.hpp>
  20 #include <iostream>
  21 #include <cstdlib>
  22
  23 #ifdef BOOST_NO_EXCEPTIONS
  24 void
  25 boost::throw_exception(std::exception const& ex)
  26 {
  27     std::cout << ex.what() << std::endl;
  28     abort();
  29 }
  30 #endif
  31
  32 using namespace boost;
  33 using boost::graph::distributed::mpi_process_group;
  34
  35 template<typename Graph, typename WeightMap, typename InputIterator>
  36 int
  37 total_weight(const Graph& g, WeightMap weight_map,
  38              InputIterator first, InputIterator last)
  39 {
  40   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
  41
  42   int total_weight = 0;
  43   while (first != last) {
  44     total_weight += get(weight_map, *first);
  45     if (process_id(g.process_group()) == 0) {
  46       vertex_descriptor u = source(*first, g);
  47       vertex_descriptor v = target(*first, g);
  48       std::cout << "(" << g.distribution().global(owner(u), local(u))
  49                 << ", " << g.distribution().global(owner(v), local(v))
  50                 << ")\n";
  51     }
  52     ++first;
  53   }
  54
  55   return total_weight;
  56 }
  57
  58 void
  59 test_distributed_dense_boruvka()
  60 {
  61   typedef adjacency_list<listS,
  62                          distributedS<mpi_process_group, vecS>,
  63                          undirectedS,
  64                          // Vertex properties
  65                          no_property,
  66                          // Edge properties
  67                          property<edge_weight_t, int> > Graph;
  68
  69   typedef graph_traits<Graph>::edge_descriptor edge_descriptor;
  70
  71   typedef std::pair<int, int> E;
  72
  73   const int num_nodes = 5;
  74   E edge_array[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3),
  75     E(3, 4), E(4, 0), E(4, 1)
  76   };
  77   int weights[] = { 1, 1, 2, 7, 3, 1, 1, 1 };
  78   std::size_t num_edges = sizeof(edge_array) / sizeof(E);
  79
  80   Graph g(edge_array, edge_array + num_edges, weights, num_nodes);
  81
  82   {
  83     if (process_id(g.process_group()) == 0)
  84       std::cerr << "--Dense Boruvka--\n";
  85     typedef property_map<Graph, edge_weight_t>::type WeightMap;
  86     WeightMap weight_map = get(edge_weight, g);
  87
  88     std::vector<edge_descriptor> mst_edges;
  89     dense_boruvka_minimum_spanning_tree(make_vertex_list_adaptor(g),
  90                                         weight_map,
  91                                         std::back_inserter(mst_edges));
  92     int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
  93     BOOST_CHECK(w == 4);
  94     BOOST_CHECK(mst_edges.size() == 4);
  95   }
  96
  97   {
  98     if (process_id(g.process_group()) == 0)
  99       std::cerr << "--Merge local MSTs--\n";
 100     typedef property_map<Graph, edge_weight_t>::type WeightMap;
 101     WeightMap weight_map = get(edge_weight, g);
 102
 103     std::vector<edge_descriptor> mst_edges;
 104     merge_local_minimum_spanning_trees(make_vertex_list_adaptor(g), weight_map,
 105                                        std::back_inserter(mst_edges));
 106     if (process_id(g.process_group()) == 0) {
 107       int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
 108       BOOST_CHECK(w == 4);
 109       BOOST_CHECK(mst_edges.size() == 4);
 110     }
 111   }
 112
 113   {
 114     if (process_id(g.process_group()) == 0)
 115       std::cerr << "--Boruvka then Merge--\n";
 116     typedef property_map<Graph, edge_weight_t>::type WeightMap;
 117     WeightMap weight_map = get(edge_weight, g);
 118
 119     std::vector<edge_descriptor> mst_edges;
 120     boruvka_then_merge(make_vertex_list_adaptor(g), weight_map,
 121                         std::back_inserter(mst_edges));
 122     if (process_id(g.process_group()) == 0) {
 123       int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
 124       BOOST_CHECK(w == 4);
 125       BOOST_CHECK(mst_edges.size() == 4);
 126     }
 127   }
 128
 129   {
 130     if (process_id(g.process_group()) == 0)
 131       std::cerr << "--Boruvka mixed Merge--\n";
 132     typedef property_map<Graph, edge_weight_t>::type WeightMap;
 133     WeightMap weight_map = get(edge_weight, g);
 134
 135     std::vector<edge_descriptor> mst_edges;
 136     boruvka_mixed_merge(make_vertex_list_adaptor(g), weight_map,
 137                         std::back_inserter(mst_edges));
 138     if (process_id(g.process_group()) == 0) {
 139       int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
 140       BOOST_CHECK(w == 4);
 141       BOOST_CHECK(mst_edges.size() == 4);
 142     }
 143   }
 144 }
 145
 146 int test_main(int argc, char** argv)
 147 {
 148   boost::mpi::environment env(argc, argv);
 149   test_distributed_dense_boruvka();
 150   return 0;
 151 }