libs/graph_parallel/test/adjlist_remove_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/graph/distributed/adjacency_list.hpp>
  14 #include <boost/graph/distributed/mpi_process_group.hpp>
  15 #include <boost/graph/parallel/distribution.hpp>
  16 #include <iostream>
  17 #include <cassert>
  18 #include <boost/test/minimal.hpp>
  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 void test_bidirectional_graph()
  33 {
  34   typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>,
  35                          bidirectionalS> Graph;
  36   typedef graph_traits<Graph>::vertex_descriptor Vertex;
  37
  38   typedef std::pair<std::size_t, std::size_t> E;
  39   E edges[3] = { E(0,3), E(1,4), E(2,5) };
  40
  41   Graph g(&edges[0], &edges[0] + 3, 6);
  42   assert(num_processes(g.process_group()) == 2);
  43
  44   if (process_id(g.process_group()) == 0)
  45     std::cerr << "Testing bidirectional graph edge removal...";
  46   synchronize(g.process_group());
  47
  48   graph_traits<Graph>::vertex_iterator vi = vertices(g).first;
  49   Vertex u = *vi++;
  50   Vertex v = *vi++;
  51   Vertex w = *vi++;
  52   BOOST_CHECK(vi == vertices(g).second);
  53
  54   BOOST_CHECK((process_id(g.process_group()) == 0 && out_degree(u, g) == 1)
  55              || (process_id(g.process_group()) == 1 && in_degree(u, g) == 1));
  56
  57   BOOST_CHECK((process_id(g.process_group()) == 0 && out_degree(v, g) == 1)
  58              || (process_id(g.process_group()) == 1 && in_degree(v, g) == 1));
  59
  60   BOOST_CHECK((process_id(g.process_group()) == 0 && out_degree(w, g) == 1)
  61              || (process_id(g.process_group()) == 1 && in_degree(w, g) == 1));
  62
  63   // Remove edges
  64   if (process_id(g.process_group()) == 0) {
  65     remove_edge(*out_edges(u, g).first, g);
  66     remove_edge(*out_edges(w, g).first, g);
  67   } else {
  68     remove_edge(*in_edges(v, g).first, g);
  69     remove_edge(*in_edges(w, g).first, g);
  70   }
  71
  72   synchronize(g);
  73
  74   BOOST_CHECK(num_edges(g) == 0);
  75   BOOST_CHECK(out_degree(u, g) == 0);
  76   BOOST_CHECK(out_degree(v, g) == 0);
  77   BOOST_CHECK(out_degree(w, g) == 0);
  78   BOOST_CHECK(in_degree(u, g) == 0);
  79   BOOST_CHECK(in_degree(v, g) == 0);
  80   BOOST_CHECK(in_degree(w, g) == 0);
  81
  82   if (process_id(g.process_group()) == 0) std::cerr << "OK.\n";
  83 }
  84
  85 void test_undirected_graph()
  86 {
  87   typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>,
  88                          undirectedS> Graph;
  89   typedef graph_traits<Graph>::vertex_descriptor Vertex;
  90   typedef graph_traits<Graph>::edge_descriptor Edge;
  91
  92   typedef std::pair<std::size_t, std::size_t> E;
  93   E the_edges[3] = { E(0,3), E(1,4), E(2,5) };
  94
  95   Graph g(&the_edges[0], &the_edges[0] + 3, 6);
  96   assert(num_processes(g.process_group()) == 2);
  97
  98   if (process_id(g.process_group()) == 0)
  99     std::cerr << "Testing undirected graph edge removal...";
 100   synchronize(g.process_group());
 101
 102   graph_traits<Graph>::vertex_iterator vi = vertices(g).first;
 103   Vertex u = *vi++;
 104   Vertex v = *vi++;
 105   Vertex w = *vi++;
 106   BOOST_CHECK(vi == vertices(g).second);
 107   BOOST_CHECK(degree(u, g) == 1);
 108   BOOST_CHECK(degree(v, g) == 1);
 109   BOOST_CHECK(degree(w, g) == 1);
 110
 111   // Remove edges
 112   if (process_id(g.process_group()) == 0) {
 113     BOOST_CHECK(num_edges(g) == 3);
 114     remove_edge(*out_edges(u, g).first, g);
 115     remove_edge(*out_edges(w, g).first, g);
 116   } else {
 117     BOOST_CHECK(num_edges(g) == 0);
 118     remove_edge(*in_edges(v, g).first, g);
 119     remove_edge(*in_edges(w, g).first, g);
 120   }
 121
 122   synchronize(g);
 123
 124   if (num_edges(g) > 0) {
 125     Edge e = *edges(g).first;
 126     std::cerr << "#" << process_id(g.process_group()) << ": extra edge! ("
 127               << local(source(e, g)) << "@" << owner(source(e, g))
 128               << ", "
 129               << local(target(e, g)) << "@" << owner(target(e, g))
 130               << ")\n";
 131   }
 132
 133   BOOST_CHECK(num_edges(g) == 0);
 134   BOOST_CHECK(degree(u, g) == 0);
 135   BOOST_CHECK(degree(v, g) == 0);
 136   BOOST_CHECK(degree(w, g) == 0);
 137   if (process_id(g.process_group()) == 0) std::cerr << "OK.\n";
 138 }
 139
 140 int test_main(int argc, char** argv)
 141 {
 142   boost::mpi::environment env(argc, argv);
 143   test_bidirectional_graph();
 144   test_undirected_graph();
 145   return 0;
 146 }