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

   1 // Copyright (C) 2004-2008 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/graph/distributed/adjacency_list.hpp>
  14 #include <boost/graph/distributed/mpi_process_group.hpp>
  15 #include <boost/graph/distributed/local_subgraph.hpp>
  16 #include <boost/graph/parallel/distribution.hpp>
  17 #include <iostream>
  18 #include <cassert>
  19 #include <boost/test/minimal.hpp>
  20
  21 #ifdef BOOST_NO_EXCEPTIONS
  22 void
  23 boost::throw_exception(std::exception const& ex)
  24 {
  25     std::cout << ex.what() << std::endl;
  26     abort();
  27 }
  28 #endif
  29
  30 using namespace boost;
  31 using boost::graph::distributed::mpi_process_group;
  32
  33 template<typename Graph>
  34 struct never
  35 {
  36   typedef typename graph_traits<Graph>::edge_descriptor argument_type;
  37   typedef bool result_type;
  38
  39   result_type operator()(argument_type) { return false; }
  40 };
  41
  42 int test_main(int argc, char** argv)
  43 {
  44   boost::mpi::environment env(argc, argv);
  45
  46   mpi_process_group pg;
  47   parallel::block dist(pg, 20);
  48
  49   typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>,
  50                          bidirectionalS> Graph1;
  51   typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>,
  52                          directedS> Graph2;
  53   typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>,
  54                          undirectedS> Graph3;
  55
  56   if (num_processes(pg) > 20) return -1;
  57
  58   if (process_id(pg) == 0) std::cout << "Graph 1------------------\n";
  59
  60   std::cout << "Processor #" << process_id(pg) << ": "
  61             << dist.block_size(20) << " vertices." << std::endl;
  62   {
  63     Graph1 g1(20);
  64
  65     //    if (process_id(pg) == num_processes(pg)() - 1)
  66     //      add_vertex(g1);
  67
  68     graph_traits<Graph1>::vertex_iterator v, v_end;
  69     int counter = 0;
  70     for (boost::tie(v, v_end) = vertices(g1); v != v_end; ++v) {
  71       std::cout << "Processor #" << process_id(pg) << ": vertex " << ++counter
  72                 << std::endl;
  73
  74       out_edges(*v, g1);
  75       out_degree(*v, g1);
  76       in_edges(*v, g1);
  77       in_degree(*v, g1);
  78
  79       graph_traits<Graph1>::vertex_descriptor other = *v;
  80       other.owner = (other.owner + 1) % num_processes(pg);
  81       other.local = 0;
  82       add_edge(*v, other, g1);
  83
  84       std::cout << "Adding edge from processor " << process_id(pg)
  85                 << " to processor " << other.owner << std::endl;
  86     }
  87
  88     synchronize(g1);
  89     assert((std::size_t)std::distance(edges(g1).first, edges(g1).second) == num_vertices(g1));
  90
  91     if (num_vertices(g1) >= 2) {
  92       graph_traits<Graph1>::vertex_iterator vi = vertices(g1).first;
  93       graph_traits<Graph1>::vertex_descriptor u = *vi++;
  94       graph_traits<Graph1>::vertex_descriptor v = *vi++;
  95       add_edge(u, v, g1);
  96       assert(out_degree(u, g1) == 2);
  97       assert(in_degree(v, g1) == 1);
  98     }
  99
 100     int prior_processor = (process_id(pg) + num_processes(pg) - 1)
 101       % num_processes(pg);
 102     const int n = 20;
 103     std::size_t vertices_in_prior = (n / num_processes(pg))
 104       + (n % num_processes(pg) > prior_processor? 1 : 0);
 105
 106     graph_traits<Graph1>::vertex_descriptor u = *vertices(g1).first;
 107     if (in_degree(u, g1) != vertices_in_prior) {
 108       std::cout << "Processor #" << process_id(pg) << ": " << in_degree(u, g1)
 109                 << " vs. " << vertices_in_prior << std::endl;
 110     }
 111     assert(in_degree(u, g1) == vertices_in_prior);
 112     std::cout << "Processor #" << process_id(pg) << ": " << num_edges(g1)
 113               << " edges.\n";
 114
 115     local_subgraph<Graph1> local_g1(g1);
 116     edges(local_g1);
 117     vertices(local_g1);
 118     if (num_vertices(local_g1) > 0) {
 119       out_edges(*vertices(local_g1).first, local_g1);
 120       in_edges(*vertices(local_g1).first, local_g1);
 121       adjacent_vertices(*vertices(local_g1).first, local_g1);
 122       if (false) {
 123         remove_out_edge_if(*vertices(g1).first, never<Graph1>(), g1);
 124         remove_in_edge_if(*vertices(g1).first, never<Graph1>(), g1);
 125         clear_out_edges(*vertices(g1).first, g1);
 126         clear_in_edges(*vertices(g1).first, g1);
 127         clear_vertex(*vertices(g1).first, g1);
 128         remove_vertex(*vertices(g1).first, g1);
 129       }
 130     }
 131     remove_edge_if(never<Graph1>(), g1);
 132   }
 133
 134
 135   if (process_id(pg) == 0) std::cout << "Graph 2------------------\n";
 136
 137   {
 138     Graph2 g2(20);
 139
 140     if (process_id(pg) == num_processes(pg) - 1)
 141       add_vertex(g2);
 142
 143     graph_traits<Graph2>::vertex_iterator v, v_end;
 144     int counter = 0;
 145     for (boost::tie(v, v_end) = vertices(g2); v != v_end; ++v) {
 146       std::cout << "Processor #" << process_id(pg) << ": vertex " << ++counter
 147                 << std::endl;
 148
 149       out_edges(*v, g2);
 150     }
 151
 152     synchronize(g2);
 153
 154     if (num_vertices(g2) >= 2) {
 155       graph_traits<Graph2>::vertex_iterator vi = vertices(g2).first;
 156       graph_traits<Graph2>::vertex_descriptor u = *vi++;
 157       graph_traits<Graph2>::vertex_descriptor v = *vi++;
 158       add_edge(u, v, g2);
 159       assert(out_degree(u, g2) == 1);
 160       assert(*adjacent_vertices(u, g2).first == v);
 161       std::cout << "Processor #" << process_id(pg) << ": " << num_edges(g2)
 162                 << " edges.\n";
 163       assert(std::distance(edges(g2).first, edges(g2).second) == 1);
 164
 165     }
 166     synchronize(g2);
 167
 168     local_subgraph<Graph2> local_g2(g2);
 169     edges(local_g2);
 170     vertices(local_g2);
 171     if (num_vertices(local_g2) > 0) {
 172       out_edges(*vertices(local_g2).first, local_g2);
 173       adjacent_vertices(*vertices(local_g2).first, local_g2);
 174       remove_out_edge_if(*vertices(g2).first, never<Graph2>(), g2);
 175       clear_out_edges(*vertices(g2).first, g2);
 176       remove_vertex(*vertices(g2).first, g2);
 177     }
 178     remove_edge_if(never<Graph2>(), g2);
 179   }
 180
 181   if (process_id(pg) == 0) std::cout << "Graph 3------------------\n";
 182
 183   {
 184     Graph3 g3(20);
 185
 186     //    if (process_id(pg) == num_processes(pg) - 1)
 187     //      add_vertex(g3);
 188
 189     graph_traits<Graph3>::vertex_iterator v, v_end;
 190     int counter = 0;
 191     for (boost::tie(v, v_end) = vertices(g3); v != v_end; ++v) {
 192       std::cout << "Processor #" << process_id(pg) << ": vertex " << ++counter
 193                 << std::endl;
 194
 195       out_edges(*v, g3);
 196       out_degree(*v, g3);
 197       in_edges(*v, g3);
 198       in_degree(*v, g3);
 199     }
 200
 201     graph_traits<Graph3>::vertices_size_type added_edges = 0;
 202     if (num_vertices(g3) >= 2) {
 203       graph_traits<Graph3>::vertex_iterator vi = vertices(g3).first;
 204       graph_traits<Graph3>::vertex_descriptor u = *vi++;
 205       graph_traits<Graph3>::vertex_descriptor v = *vi++;
 206       add_edge(u, v, g3); ++added_edges;
 207       assert(out_degree(u, g3) == 1);
 208       assert(in_degree(u, g3) == 1);
 209       graph_traits<Graph3>::edge_descriptor e = *out_edges(u, g3).first;
 210       assert(source(e, g3) == u);
 211       assert(target(e, g3) == v);
 212       e = *in_edges(u, g3).first;
 213       assert(source(e, g3) == v);
 214       assert(target(e, g3) == u);
 215       assert(out_degree(v, g3) == 1);
 216       assert(in_degree(v, g3) == 1);
 217       e = *out_edges(v, g3).first;
 218       assert(source(e, g3) == v);
 219       assert(target(e, g3) == u);
 220       e = *in_edges(v, g3).first;
 221       assert(source(e, g3) == u);
 222       assert(target(e, g3) == v);
 223
 224       assert(*adjacent_vertices(u, g3).first == v);
 225       assert(*adjacent_vertices(v, g3).first == u);
 226       std::cout << "Processor #" << process_id(pg) << ": " << num_edges(g3)
 227                 << " edges.\n";
 228     }
 229
 230     // Add some remote edges
 231     for (boost::tie(v, v_end) = vertices(g3); v != v_end; ++v) {
 232       graph_traits<Graph1>::vertex_descriptor other = *v;
 233       other.owner = (other.owner + 1) % num_processes(pg);
 234       other.local = 0;
 235       add_edge(*v, other, g3); ++added_edges;
 236
 237       std::cout << "Adding edge from processor " << process_id(pg)
 238                 << " to processor " << other.owner << std::endl;
 239     }
 240
 241     synchronize(g3);
 242     assert(std::distance(edges(g3).first, edges(g3).second) == (ptrdiff_t)added_edges);
 243     assert(num_edges(g3) == added_edges);
 244
 245     // Verify the remote edges
 246     if (num_vertices(g3) >= 2) {
 247       graph_traits<Graph3>::vertex_iterator vi = vertices(g3).first;
 248       graph_traits<Graph3>::vertex_descriptor u = *vi++;
 249
 250       int prior_processor = (process_id(pg) + num_processes(pg) - 1)
 251         % num_processes(pg);
 252       const int n = 20;
 253       graph_traits<Graph3>::vertices_size_type vertices_in_prior = (n / num_processes(pg))
 254         + (n % num_processes(pg) > prior_processor? 1 : 0);
 255       if (in_degree(u, g3) != vertices_in_prior + 2) {
 256         std::cerr << "#" << process_id(pg) << ": " << in_degree(u, g3)
 257                   << " != " << vertices_in_prior + 2 << std::endl;
 258       }
 259
 260       assert(in_degree(u, g3) == vertices_in_prior + 2);
 261       assert(out_degree(u, g3) == vertices_in_prior + 2);
 262     }
 263
 264     local_subgraph<Graph3> local_g3(g3);
 265     edges(local_g3);
 266     vertices(local_g3);
 267     if (num_vertices(local_g3) > 0) {
 268       out_edges(*vertices(local_g3).first, local_g3);
 269       in_edges(*vertices(local_g3).first, local_g3);
 270       adjacent_vertices(*vertices(local_g3).first, local_g3);
 271       remove_out_edge_if(*vertices(g3).first, never<Graph3>(), g3);
 272       remove_in_edge_if(*vertices(g3).first, never<Graph3>(), g3);
 273       if (false) {
 274         // Removing an edge from two processes concurrently is not yet
 275         // supported.
 276         clear_vertex(*vertices(g3).first, g3);
 277         remove_vertex(*vertices(g3).first, g3);
 278       }
 279     }
 280     remove_edge_if(never<Graph3>(), g3);
 281   }
 282
 283   return 0;
 284 }