123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216 |
- // Copyright (C) 2005, 2006 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/lexical_cast.hpp>
- #include <boost/serialization/vector.hpp>
- #include <boost/graph/distributed/adjacency_list.hpp>
- #include <boost/graph/distributed/mpi_process_group.hpp>
- #include <boost/random/linear_congruential.hpp>
- #include <iostream>
- #include <boost/property_map/property_map_iterator.hpp>
- #include <boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp>
- #include <boost/graph/distributed/vertex_list_adaptor.hpp>
- #include <boost/graph/erdos_renyi_generator.hpp>
- #include <boost/graph/distributed/graphviz.hpp>
- #include <sstream>
- #include <string>
- #include <boost/graph/iteration_macros.hpp>
- #include <boost/test/minimal.hpp>
- #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;
- /****************************************************************************
- * Edge weight generator iterator *
- ****************************************************************************/
- template<typename F>
- class generator_iterator
- {
- public:
- typedef std::input_iterator_tag iterator_category;
- typedef typename F::result_type value_type;
- typedef const value_type& reference;
- typedef const value_type* pointer;
- typedef void difference_type;
- explicit generator_iterator(const F& f = F()) : f(f) { value = this->f(); }
- reference operator*() const { return value; }
- pointer operator->() const { return &value; }
- generator_iterator& operator++()
- {
- value = f();
- return *this;
- }
- generator_iterator operator++(int)
- {
- generator_iterator temp(*this);
- ++(*this);
- return temp;
- }
- bool operator==(const generator_iterator& other) const
- { return f == other.f; }
- bool operator!=(const generator_iterator& other) const
- { return !(*this == other); }
- private:
- F f;
- value_type value;
- };
- template<typename F>
- inline generator_iterator<F> make_generator_iterator(const F& f)
- { return generator_iterator<F>(f); }
- typedef minstd_rand RandomGenerator;
- template<typename Graph>
- double get_mst_weight (const Graph& g)
- {
- typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
- typename property_map<Graph, edge_weight_t>::const_type weight
- = get(edge_weight, g);
- // Boruvka then merge test
- std::vector<edge_descriptor> results;
- graph::boruvka_then_merge(make_vertex_list_adaptor(g), weight,
- std::back_inserter(results));
- if (process_id(g.process_group()) == 0)
- return accumulate(make_property_map_iterator(weight, results.begin()),
- make_property_map_iterator(weight, results.end()),
- 0.0);
- else
- return 0.0;
- }
- template<typename Graph>
- void test_redistribution(int n, double p, int iterations, bool debug_output)
- {
- RandomGenerator gen;
- Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, n, p),
- erdos_renyi_iterator<RandomGenerator, Graph>(),
- make_generator_iterator(uniform_01<RandomGenerator>(gen)),
- n);
- int iter = 0;
- mpi_process_group pg = g.process_group();
- // Set the names of the vertices to be the global index in the
- // initial distribution. Then when we are debugging we'll be able to
- // see how vertices have moved.
- {
- typedef typename property_map<Graph, vertex_index_t>::type VertexIndexMap;
- typedef typename property_map<Graph, vertex_global_t>::type VertexGlobalMap;
- typename property_map<Graph, vertex_name_t>::type name_map
- = get(vertex_name, g);
- parallel::global_index_map<VertexIndexMap, VertexGlobalMap>
- global_index(g.process_group(), num_vertices(g),
- get(vertex_index, g), get(vertex_global, g));
- BGL_FORALL_VERTICES_T(v, g, Graph)
- put(name_map, v, get(global_index, v));
- }
- if (debug_output)
- write_graphviz("redist-0.dot", g,
- make_label_writer(get(vertex_name, g)),
- make_label_writer(get(edge_weight, g)));
- double mst_weight = get_mst_weight(g);
- if (process_id(pg) == 0)
- std::cout << "MST weight = " << mst_weight << std::endl;
- RandomGenerator nonsync_gen(process_id(pg) + gen());
- while (++iter <= iterations) {
- typename property_map<Graph, vertex_rank_t>::type to_processor_map =
- get(vertex_rank, g);
- // Randomly assign a new distribution
- typename graph_traits<Graph>::vertex_iterator vi, vi_end;
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
- put(to_processor_map, *vi, gen() % num_processes(pg));
- if (process_id(pg) == 0)
- std::cout << "Redistributing...";
- // Perform the actual redistribution
- g.redistribute(to_processor_map);
- if (process_id(pg) == 0)
- std::cout << " done." << std::endl;
- if (debug_output) {
- std::ostringstream out;
- out << "redist-" << iter << ".dot";
- write_graphviz(out.str().c_str(), g,
- make_label_writer(get(vertex_name, g)),
- make_label_writer(get(edge_weight, g)));
- }
- // Check that the MST weight is unchanged
- double new_mst_weight = get_mst_weight(g);
- if (process_id(pg) == 0) {
- std::cout << "MST weight = " << new_mst_weight << std::endl;
- if (std::fabs(new_mst_weight - mst_weight) > 0.0001)
- communicator(pg).abort(-1); }
- }
- }
- int test_main(int argc, char** argv)
- {
- int n = 1000;
- double p = 3e-3;
- int iterations = 5;
- bool debug_output = false;
- boost::mpi::environment env(argc, argv);
- if (argc > 1) n = lexical_cast<int>(argv[1]);
- if (argc > 2) p = lexical_cast<double>(argv[2]);
- if (argc > 3) iterations = lexical_cast<int>(argv[3]);
- if (argc > 4) debug_output = true;
- typedef adjacency_list<listS,
- distributedS<mpi_process_group, vecS>,
- undirectedS,
- // Vertex properties
- property<vertex_name_t, std::size_t,
- property<vertex_rank_t, int> >,
- // Edge properties
- property<edge_weight_t, double> > UnstableUDGraph;
- typedef adjacency_list<listS,
- distributedS<mpi_process_group, listS>,
- undirectedS,
- // Vertex properties
- property<vertex_name_t, std::size_t,
- property<vertex_rank_t, int,
- property<vertex_index_t, std::size_t> > >,
- // Edge properties
- property<edge_weight_t, double> > StableUDGraph;
- test_redistribution<UnstableUDGraph>(n, p, iterations, debug_output);
- test_redistribution<StableUDGraph>(n, p, iterations, debug_output);
- return 0;
- }
|