// 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) { set_property_map_role(vertex_distance, distance); } template void tree_edge(Edge e, const Graph& g) { typename property_map::type vidxx = get(vertex_index, g); typename graph_traits::vertex_descriptor src = source(e,g); typename graph_traits::vertex_descriptor des = target(e,g); std::size_t new_distance = get(distance, source(e, g)) + 1; std::cout<<"NowVisiting: ("< ("<, directedS, /*Vertex properties=*/property > Graph; int main(int argc, char* argv[]) { boost::mpi::environment env(argc,argv); // Parse command-line options int n = 7; Graph g(n); if(process_id(g.process_group()) == 0){ std::vector > allEdges; allEdges.push_back(std::pair(0,1)); allEdges.push_back(std::pair(0,2)); allEdges.push_back(std::pair(1,2)); allEdges.push_back(std::pair(1,3)); allEdges.push_back(std::pair(2,3)); allEdges.push_back(std::pair(3,4)); allEdges.push_back(std::pair(4,5)); allEdges.push_back(std::pair(3,6)); std::vector >::iterator git = allEdges.begin(); for( ; git != allEdges.end(); git++) { add_edge(vertex(git->first, g), vertex(git->second, g), g); } // print_graph(g); } synchronize(g.process_group()); typedef boost::graph::parallel::process_group_type::type process_group_type; typedef property_map::type VertexDistanceMap; typedef graph_traits::vertex_descriptor key_type; typedef property_map::type VertexIndexMap; property_map::type distance = get(vertex_distance, g); // Get vertex 0 in the graph graph_traits::vertex_descriptor start = vertex(0, g); // Compute BFS levels from vertex 0 property_map::type vidx = get(vertex_index, g); put(distance, start, 0); distance.set_consistency_model(boost::parallel::cm_forward); breadth_first_search (g, start, visitor(bfs_discovery_visitor(distance))); synchronize(g.process_group()); typedef property_map::const_type VertexIndexMap; typedef property_map::const_type VertexGlobalMap; if(process_id(g.process_group()) == 0){ using boost::graph::parallel::process_group; process_group_type pg = process_group(g); std::cout<<"Finished Parallel BFS "<::vertex_descriptor vtx = vertex(i, g); std::cout<