123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151 |
- // Copyright 2004 The Trustees of Indiana University.
- // Use, modification and distribution is subject to the Boost Software
- // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- // Authors: Douglas Gregor
- // Andrew Lumsdaine
- #include <boost/graph/use_mpi.hpp>
- #include <boost/config.hpp>
- #include <boost/throw_exception.hpp>
- #include <boost/serialization/vector.hpp>
- #include <boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp>
- #include <boost/graph/distributed/mpi_process_group.hpp>
- #include <boost/graph/distributed/vertex_list_adaptor.hpp>
- #include <boost/graph/parallel/distribution.hpp>
- #include <boost/test/minimal.hpp>
- #include <boost/graph/distributed/adjacency_list.hpp>
- #include <iostream>
- #include <cstdlib>
- #ifdef BOOST_NO_EXCEPTIONS
- void
- boost::throw_exception(std::exception const& ex)
- {
- std::cout << ex.what() << std::endl;
- abort();
- }
- #endif
- using namespace boost;
- using boost::graph::distributed::mpi_process_group;
- template<typename Graph, typename WeightMap, typename InputIterator>
- int
- total_weight(const Graph& g, WeightMap weight_map,
- InputIterator first, InputIterator last)
- {
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- int total_weight = 0;
- while (first != last) {
- total_weight += get(weight_map, *first);
- if (process_id(g.process_group()) == 0) {
- vertex_descriptor u = source(*first, g);
- vertex_descriptor v = target(*first, g);
- std::cout << "(" << g.distribution().global(owner(u), local(u))
- << ", " << g.distribution().global(owner(v), local(v))
- << ")\n";
- }
- ++first;
- }
- return total_weight;
- }
- void
- test_distributed_dense_boruvka()
- {
- typedef adjacency_list<listS,
- distributedS<mpi_process_group, vecS>,
- undirectedS,
- // Vertex properties
- no_property,
- // Edge properties
- property<edge_weight_t, int> > Graph;
- typedef graph_traits<Graph>::edge_descriptor edge_descriptor;
- typedef std::pair<int, int> E;
- const int num_nodes = 5;
- E edge_array[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3),
- E(3, 4), E(4, 0), E(4, 1)
- };
- int weights[] = { 1, 1, 2, 7, 3, 1, 1, 1 };
- std::size_t num_edges = sizeof(edge_array) / sizeof(E);
- Graph g(edge_array, edge_array + num_edges, weights, num_nodes);
- {
- if (process_id(g.process_group()) == 0)
- std::cerr << "--Dense Boruvka--\n";
- typedef property_map<Graph, edge_weight_t>::type WeightMap;
- WeightMap weight_map = get(edge_weight, g);
-
- std::vector<edge_descriptor> mst_edges;
- dense_boruvka_minimum_spanning_tree(make_vertex_list_adaptor(g),
- weight_map,
- std::back_inserter(mst_edges));
- int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
- BOOST_CHECK(w == 4);
- BOOST_CHECK(mst_edges.size() == 4);
- }
- {
- if (process_id(g.process_group()) == 0)
- std::cerr << "--Merge local MSTs--\n";
- typedef property_map<Graph, edge_weight_t>::type WeightMap;
- WeightMap weight_map = get(edge_weight, g);
-
- std::vector<edge_descriptor> mst_edges;
- merge_local_minimum_spanning_trees(make_vertex_list_adaptor(g), weight_map,
- std::back_inserter(mst_edges));
- if (process_id(g.process_group()) == 0) {
- int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
- BOOST_CHECK(w == 4);
- BOOST_CHECK(mst_edges.size() == 4);
- }
- }
- {
- if (process_id(g.process_group()) == 0)
- std::cerr << "--Boruvka then Merge--\n";
- typedef property_map<Graph, edge_weight_t>::type WeightMap;
- WeightMap weight_map = get(edge_weight, g);
-
- std::vector<edge_descriptor> mst_edges;
- boruvka_then_merge(make_vertex_list_adaptor(g), weight_map,
- std::back_inserter(mst_edges));
- if (process_id(g.process_group()) == 0) {
- int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
- BOOST_CHECK(w == 4);
- BOOST_CHECK(mst_edges.size() == 4);
- }
- }
- {
- if (process_id(g.process_group()) == 0)
- std::cerr << "--Boruvka mixed Merge--\n";
- typedef property_map<Graph, edge_weight_t>::type WeightMap;
- WeightMap weight_map = get(edge_weight, g);
-
- std::vector<edge_descriptor> mst_edges;
- boruvka_mixed_merge(make_vertex_list_adaptor(g), weight_map,
- std::back_inserter(mst_edges));
- if (process_id(g.process_group()) == 0) {
- int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
- BOOST_CHECK(w == 4);
- BOOST_CHECK(mst_edges.size() == 4);
- }
- }
- }
- int test_main(int argc, char** argv)
- {
- boost::mpi::environment env(argc, argv);
- test_distributed_dense_boruvka();
- return 0;
- }
|