| // Copyright (C) 2004-2008 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/graph/distributed/adjacency_list.hpp> |
| #include <boost/graph/distributed/mpi_process_group.hpp> |
| #include <boost/graph/distributed/local_subgraph.hpp> |
| #include <boost/graph/parallel/distribution.hpp> |
| #include <iostream> |
| #include <cassert> |
| #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; |
| |
| template<typename Graph> |
| struct never |
| { |
| typedef typename graph_traits<Graph>::edge_descriptor argument_type; |
| typedef bool result_type; |
| |
| result_type operator()(argument_type) { return false; } |
| }; |
| |
| int test_main(int argc, char** argv) |
| { |
| boost::mpi::environment env(argc, argv); |
| |
| mpi_process_group pg; |
| parallel::block dist(pg, 20); |
| |
| typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>, |
| bidirectionalS> Graph1; |
| typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>, |
| directedS> Graph2; |
| typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>, |
| undirectedS> Graph3; |
| |
| if (num_processes(pg) > 20) return -1; |
| |
| if (process_id(pg) == 0) std::cout << "Graph 1------------------\n"; |
| |
| std::cout << "Processor #" << process_id(pg) << ": " |
| << dist.block_size(20) << " vertices." << std::endl; |
| { |
| Graph1 g1(20); |
| |
| // if (process_id(pg) == num_processes(pg)() - 1) |
| // add_vertex(g1); |
| |
| graph_traits<Graph1>::vertex_iterator v, v_end; |
| int counter = 0; |
| for (boost::tie(v, v_end) = vertices(g1); v != v_end; ++v) { |
| std::cout << "Processor #" << process_id(pg) << ": vertex " << ++counter |
| << std::endl; |
| |
| out_edges(*v, g1); |
| out_degree(*v, g1); |
| in_edges(*v, g1); |
| in_degree(*v, g1); |
| |
| graph_traits<Graph1>::vertex_descriptor other = *v; |
| other.owner = (other.owner + 1) % num_processes(pg); |
| other.local = 0; |
| add_edge(*v, other, g1); |
| |
| std::cout << "Adding edge from processor " << process_id(pg) |
| << " to processor " << other.owner << std::endl; |
| } |
| |
| synchronize(g1); |
| assert((std::size_t)std::distance(edges(g1).first, edges(g1).second) == num_vertices(g1)); |
| |
| if (num_vertices(g1) >= 2) { |
| graph_traits<Graph1>::vertex_iterator vi = vertices(g1).first; |
| graph_traits<Graph1>::vertex_descriptor u = *vi++; |
| graph_traits<Graph1>::vertex_descriptor v = *vi++; |
| add_edge(u, v, g1); |
| assert(out_degree(u, g1) == 2); |
| assert(in_degree(v, g1) == 1); |
| } |
| |
| int prior_processor = (process_id(pg) + num_processes(pg) - 1) |
| % num_processes(pg); |
| const int n = 20; |
| std::size_t vertices_in_prior = (n / num_processes(pg)) |
| + (n % num_processes(pg) > prior_processor? 1 : 0); |
| |
| graph_traits<Graph1>::vertex_descriptor u = *vertices(g1).first; |
| if (in_degree(u, g1) != vertices_in_prior) { |
| std::cout << "Processor #" << process_id(pg) << ": " << in_degree(u, g1) |
| << " vs. " << vertices_in_prior << std::endl; |
| } |
| assert(in_degree(u, g1) == vertices_in_prior); |
| std::cout << "Processor #" << process_id(pg) << ": " << num_edges(g1) |
| << " edges.\n"; |
| |
| local_subgraph<Graph1> local_g1(g1); |
| edges(local_g1); |
| vertices(local_g1); |
| if (num_vertices(local_g1) > 0) { |
| out_edges(*vertices(local_g1).first, local_g1); |
| in_edges(*vertices(local_g1).first, local_g1); |
| adjacent_vertices(*vertices(local_g1).first, local_g1); |
| if (false) { |
| remove_out_edge_if(*vertices(g1).first, never<Graph1>(), g1); |
| remove_in_edge_if(*vertices(g1).first, never<Graph1>(), g1); |
| clear_out_edges(*vertices(g1).first, g1); |
| clear_in_edges(*vertices(g1).first, g1); |
| clear_vertex(*vertices(g1).first, g1); |
| remove_vertex(*vertices(g1).first, g1); |
| } |
| } |
| remove_edge_if(never<Graph1>(), g1); |
| } |
| |
| |
| if (process_id(pg) == 0) std::cout << "Graph 2------------------\n"; |
| |
| { |
| Graph2 g2(20); |
| |
| if (process_id(pg) == num_processes(pg) - 1) |
| add_vertex(g2); |
| |
| graph_traits<Graph2>::vertex_iterator v, v_end; |
| int counter = 0; |
| for (boost::tie(v, v_end) = vertices(g2); v != v_end; ++v) { |
| std::cout << "Processor #" << process_id(pg) << ": vertex " << ++counter |
| << std::endl; |
| |
| out_edges(*v, g2); |
| } |
| |
| synchronize(g2); |
| |
| if (num_vertices(g2) >= 2) { |
| graph_traits<Graph2>::vertex_iterator vi = vertices(g2).first; |
| graph_traits<Graph2>::vertex_descriptor u = *vi++; |
| graph_traits<Graph2>::vertex_descriptor v = *vi++; |
| add_edge(u, v, g2); |
| assert(out_degree(u, g2) == 1); |
| assert(*adjacent_vertices(u, g2).first == v); |
| std::cout << "Processor #" << process_id(pg) << ": " << num_edges(g2) |
| << " edges.\n"; |
| assert(std::distance(edges(g2).first, edges(g2).second) == 1); |
| |
| } |
| synchronize(g2); |
| |
| local_subgraph<Graph2> local_g2(g2); |
| edges(local_g2); |
| vertices(local_g2); |
| if (num_vertices(local_g2) > 0) { |
| out_edges(*vertices(local_g2).first, local_g2); |
| adjacent_vertices(*vertices(local_g2).first, local_g2); |
| remove_out_edge_if(*vertices(g2).first, never<Graph2>(), g2); |
| clear_out_edges(*vertices(g2).first, g2); |
| remove_vertex(*vertices(g2).first, g2); |
| } |
| remove_edge_if(never<Graph2>(), g2); |
| } |
| |
| if (process_id(pg) == 0) std::cout << "Graph 3------------------\n"; |
| |
| { |
| Graph3 g3(20); |
| |
| // if (process_id(pg) == num_processes(pg) - 1) |
| // add_vertex(g3); |
| |
| graph_traits<Graph3>::vertex_iterator v, v_end; |
| int counter = 0; |
| for (boost::tie(v, v_end) = vertices(g3); v != v_end; ++v) { |
| std::cout << "Processor #" << process_id(pg) << ": vertex " << ++counter |
| << std::endl; |
| |
| out_edges(*v, g3); |
| out_degree(*v, g3); |
| in_edges(*v, g3); |
| in_degree(*v, g3); |
| } |
| |
| graph_traits<Graph3>::vertices_size_type added_edges = 0; |
| if (num_vertices(g3) >= 2) { |
| graph_traits<Graph3>::vertex_iterator vi = vertices(g3).first; |
| graph_traits<Graph3>::vertex_descriptor u = *vi++; |
| graph_traits<Graph3>::vertex_descriptor v = *vi++; |
| add_edge(u, v, g3); ++added_edges; |
| assert(out_degree(u, g3) == 1); |
| assert(in_degree(u, g3) == 1); |
| graph_traits<Graph3>::edge_descriptor e = *out_edges(u, g3).first; |
| assert(source(e, g3) == u); |
| assert(target(e, g3) == v); |
| e = *in_edges(u, g3).first; |
| assert(source(e, g3) == v); |
| assert(target(e, g3) == u); |
| assert(out_degree(v, g3) == 1); |
| assert(in_degree(v, g3) == 1); |
| e = *out_edges(v, g3).first; |
| assert(source(e, g3) == v); |
| assert(target(e, g3) == u); |
| e = *in_edges(v, g3).first; |
| assert(source(e, g3) == u); |
| assert(target(e, g3) == v); |
| |
| assert(*adjacent_vertices(u, g3).first == v); |
| assert(*adjacent_vertices(v, g3).first == u); |
| std::cout << "Processor #" << process_id(pg) << ": " << num_edges(g3) |
| << " edges.\n"; |
| } |
| |
| // Add some remote edges |
| for (boost::tie(v, v_end) = vertices(g3); v != v_end; ++v) { |
| graph_traits<Graph1>::vertex_descriptor other = *v; |
| other.owner = (other.owner + 1) % num_processes(pg); |
| other.local = 0; |
| add_edge(*v, other, g3); ++added_edges; |
| |
| std::cout << "Adding edge from processor " << process_id(pg) |
| << " to processor " << other.owner << std::endl; |
| } |
| |
| synchronize(g3); |
| assert(std::distance(edges(g3).first, edges(g3).second) == (ptrdiff_t)added_edges); |
| assert(num_edges(g3) == added_edges); |
| |
| // Verify the remote edges |
| if (num_vertices(g3) >= 2) { |
| graph_traits<Graph3>::vertex_iterator vi = vertices(g3).first; |
| graph_traits<Graph3>::vertex_descriptor u = *vi++; |
| |
| int prior_processor = (process_id(pg) + num_processes(pg) - 1) |
| % num_processes(pg); |
| const int n = 20; |
| graph_traits<Graph3>::vertices_size_type vertices_in_prior = (n / num_processes(pg)) |
| + (n % num_processes(pg) > prior_processor? 1 : 0); |
| if (in_degree(u, g3) != vertices_in_prior + 2) { |
| std::cerr << "#" << process_id(pg) << ": " << in_degree(u, g3) |
| << " != " << vertices_in_prior + 2 << std::endl; |
| } |
| |
| assert(in_degree(u, g3) == vertices_in_prior + 2); |
| assert(out_degree(u, g3) == vertices_in_prior + 2); |
| } |
| |
| local_subgraph<Graph3> local_g3(g3); |
| edges(local_g3); |
| vertices(local_g3); |
| if (num_vertices(local_g3) > 0) { |
| out_edges(*vertices(local_g3).first, local_g3); |
| in_edges(*vertices(local_g3).first, local_g3); |
| adjacent_vertices(*vertices(local_g3).first, local_g3); |
| remove_out_edge_if(*vertices(g3).first, never<Graph3>(), g3); |
| remove_in_edge_if(*vertices(g3).first, never<Graph3>(), g3); |
| if (false) { |
| // Removing an edge from two processes concurrently is not yet |
| // supported. |
| clear_vertex(*vertices(g3).first, g3); |
| remove_vertex(*vertices(g3).first, g3); |
| } |
| } |
| remove_edge_if(never<Graph3>(), g3); |
| } |
| |
| return 0; |
| } |
