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
throw_exception(std::exception const & ex)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
test_bidirectional_graph()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
test_undirected_graph()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
test_main(int argc,char ** argv)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 }
147