// 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 // Example usage of breadth_first_search algorithm // Enable PBGL interfaces to BGL algorithms #include // Communicate via MPI #include // Breadth-first search algorithm #include // Distributed adjacency list #include // METIS Input #include // Graphviz Output #include // Standard Library includes #include #include #include #include #include #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 struct bfs_discovery_visitor : bfs_visitor<> { bfs_discovery_visitor(DistanceMap distance) : distance(distance) { } template void tree_edge(Edge e, const Graph& g) { put(distance, target(e,g), get(distance, source(e,g)) + 1); } private: DistanceMap distance; }; int main(int argc, char* argv[]) { boost::mpi::environment env(argc,argv); typedef adjacency_list, directedS, no_property, no_property> Graph; typedef graph_traits::vertex_descriptor vertex_descriptor; // Construct graph int n = 6; typedef std::pair E; E edge_array[] = { E(0, 1), E(0, 4), E(1, 2), E(2, 3), E(4, 3) }; std::size_t num_edges = sizeof(edge_array) / sizeof(E); Graph g(edge_array, edge_array + num_edges, n); synchronize(g.process_group()); // Define a distance map typedef property_map::const_type VertexIndexMap; typedef iterator_property_map::iterator, VertexIndexMap> DistanceMap; std::vector distance_S(num_vertices(g), std::numeric_limits::max()); DistanceMap distance(distance_S.begin(), get(vertex_index, g)); put(distance, vertex(0, g), 0); breadth_first_search(g, vertex(0, g), visitor(bfs_discovery_visitor(distance))); // Fetch final distances of targets of all local edges BGL_FORALL_EDGES(e, g, Graph) { request(distance, target(e,g)); } synchronize(distance); BGL_FORALL_EDGES(e, g, Graph) { if (get(distance, target(e,g)) > get(distance, source(e,g)) + 1) std::cerr << process_id(process_group(g)) << ": distance of " << get(get(vertex_local, g), target(e, g)) << "@" << get(get(vertex_owner, g), target(e, g)) << " = " << get(distance, target(e, g)) << " (should be <= " << get(distance, source(e, g)) + 1 << ")\n"; // assert(get(distance, target(e,g)) <= get(distance, source(e,g)) + 1); } if (process_id(process_group(g)) == 0) for (int i = 0; i < n; ++i) request(distance, vertex(i, g)); synchronize(distance); if(process_id(process_group(g)) == 0) { std::cout << "Finished Parallel BFS " << std::endl; std::cout << "Node ID : Level " << std::endl; for (int i = 0; i < n; ++i) std::cout << i << " : " << get(distance, vertex(i, g)) << " " <