// 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 <boost/graph/use_mpi.hpp> // Communicate via MPI #include <boost/graph/distributed/mpi_process_group.hpp> // Breadth-first search algorithm #include <boost/graph/breadth_first_search.hpp> // Distributed adjacency list #include <boost/graph/distributed/adjacency_list.hpp> // METIS Input #include <boost/graph/metis.hpp> // Graphviz Output #include <boost/graph/distributed/graphviz.hpp> // Standard Library includes #include <fstream> #include <string> #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; /* An undirected graph with distance values stored on the vertices. */ typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, undirectedS, /*Vertex properties=*/property<vertex_distance_t, std::size_t> > Graph; int main(int argc, char* argv[]) { boost::mpi::environment env(argc,argv); // Parse command-line options const char* filename = "weighted_graph.gr"; if (argc > 1) filename = argv[1]; // Open the METIS input file std::ifstream in(filename); graph::metis_reader reader(in); // Load the graph using the default distribution Graph g(reader.begin(), reader.end(), reader.num_vertices()); // Get vertex 0 in the graph graph_traits<Graph>::vertex_descriptor start = vertex(0, g); // Compute BFS levels from vertex 0 property_map<Graph, vertex_distance_t>::type distance = get(vertex_distance, g); put(distance, start, 0); breadth_first_search (g, start, visitor(make_bfs_visitor(record_distances(distance, on_tree_edge())))); // Output a Graphviz DOT file std::string outfile; if (argc > 2) outfile = argv[2]; else { outfile = filename; size_t i = outfile.rfind('.'); if (i != std::string::npos) outfile.erase(outfile.begin() + i, outfile.end()); outfile += "-bfs.dot"; } if (process_id(process_group(g)) == 0) { std::cout << "Writing GraphViz output to " << outfile << "... "; std::cout.flush(); } write_graphviz(outfile, g, make_label_writer(distance)); if (process_id(process_group(g)) == 0) std::cout << "Done." << std::endl; return 0; }