1 // Copyright 2004 The Trustees of Indiana University.
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)
7 // Authors: Douglas Gregor
10 #include <boost/graph/use_mpi.hpp>
11 #include <boost/throw_exception.hpp>
12 #include <boost/serialization/vector.hpp>
13 #include <boost/graph/distributed/page_rank.hpp>
14 #include <boost/core/lightweight_test.hpp>
15 #include <boost/graph/distributed/adjacency_list.hpp>
16 #include <boost/graph/distributed/mpi_process_group.hpp>
17 #include <boost/core/lightweight_test.hpp>
22 #ifdef BOOST_NO_EXCEPTIONS
24 boost::throw_exception(std::exception
const& ex
)
26 std::cout
<< ex
.what() << std::endl
;
31 using namespace boost
;
32 using boost::graph::distributed::mpi_process_group
;
34 bool close_to(double x
, double y
)
37 if (diff
< 0) diff
= -diff
;
38 double base
= (y
== 0? x
: y
);
39 if (base
!= 0) return diff
/ base
< 0.01;
43 // Make convenient labels for the vertices
44 enum vertex_id_t
{ A
, B
, C
, D
, N
};
46 void test_distributed_page_rank(int iterations
)
48 using namespace boost::graph
;
50 // create a typedef for the Graph type
51 typedef adjacency_list
<vecS
,
52 distributedS
<mpi_process_group
, vecS
>,
55 typedef graph_traits
<Graph
>::vertex_descriptor vertex_descriptor
;
57 // writing out the edges in the graph
58 typedef std::pair
<int, int> Edge
;
60 { Edge(A
,B
), Edge(A
,C
), Edge(B
,C
), Edge(C
,A
), Edge(D
,C
) };
61 const int num_edges
= sizeof(edge_array
)/sizeof(edge_array
[0]);
63 // declare a graph object
64 Graph
g(edge_array
, edge_array
+ num_edges
, N
);
66 std::vector
<double> ranks(num_vertices(g
));
69 make_iterator_property_map(ranks
.begin(),
70 get(boost::vertex_index
, g
)),
71 n_iterations(iterations
), 0.85, N
);
73 double local_sum
= 0.0;
74 for(unsigned int i
= 0; i
< num_vertices(g
); ++i
) {
75 std::cout
<< (char)('A' + g
.distribution().global(i
)) << " = "
76 << ranks
[i
] << std::endl
;
77 local_sum
+= ranks
[i
];
80 boost::mpi::reduce(communicator(g
.process_group()),
81 local_sum
, sum
, std::plus
<double>(), 0);
82 if (process_id(g
.process_group()) == 0) {
83 std::cout
<< "Sum = " << sum
<< "\n\n";
84 BOOST_TEST(close_to(sum
, 4)); // 1 when alpha=0
87 // double expected_ranks0[N] = {0.400009, 0.199993, 0.399998, 0.0};
88 double expected_ranks
[N
] = {1.49011, 0.783296, 1.5766, 0.15};
89 for (int i
= 0; i
< N
; ++i
) {
90 vertex_descriptor v
= vertex(i
, g
);
91 if (v
!= Graph::null_vertex()
92 && owner(v
) == process_id(g
.process_group())) {
93 BOOST_TEST(close_to(ranks
[local(v
)], expected_ranks
[i
]));
98 int main(int argc
, char* argv
[])
100 mpi::environment
env(argc
, argv
);
104 iterations
= atoi(argv
[1]);
107 test_distributed_page_rank(iterations
);
109 return boost::report_errors();