1 // Copyright (C) 2004-2008 The Trustees of Indiana University.
2
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6
7 // Authors: Douglas Gregor
8 // Andrew Lumsdaine
9
10 // Example usage of breadth_first_search algorithm
11
12 // Enable PBGL interfaces to BGL algorithms
13 #include <boost/graph/use_mpi.hpp>
14
15 // Communicate via MPI
16 #include <boost/graph/distributed/mpi_process_group.hpp>
17
18 // Breadth-first search algorithm
19 #include <boost/graph/breadth_first_search.hpp>
20
21 // Distributed adjacency list
22 #include <boost/graph/distributed/adjacency_list.hpp>
23
24 // METIS Input
25 #include <boost/graph/metis.hpp>
26
27 // Graphviz Output
28 #include <boost/graph/distributed/graphviz.hpp>
29
30 // For choose_min_reducer
31 #include <boost/graph/distributed/distributed_graph_utility.hpp>
32
33 // Standard Library includes
34 #include <fstream>
35 #include <string>
36
37 #ifdef BOOST_NO_EXCEPTIONS
38 void
throw_exception(std::exception const & ex)39 boost::throw_exception(std::exception const& ex)
40 {
41 std::cout << ex.what() << std::endl;
42 abort();
43 }
44 #endif
45
46 using namespace boost;
47 using boost::graph::distributed::mpi_process_group;
48
49 /* An undirected graph with distance values stored on the vertices. */
50 typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, undirectedS,
51 /*Vertex properties=*/property<vertex_distance_t, std::size_t> >
52 Graph;
53
main(int argc,char * argv[])54 int main(int argc, char* argv[])
55 {
56 boost::mpi::environment env(argc,argv);
57
58 // Parse command-line options
59 const char* filename = "weighted_graph.gr";
60 if (argc > 1) filename = argv[1];
61
62 // Open the METIS input file
63 std::ifstream in(filename);
64 graph::metis_reader reader(in);
65
66 // Load the graph using the default distribution
67 Graph g(reader.begin(), reader.end(),
68 reader.num_vertices());
69
70 // Get vertex 0 in the graph
71 graph_traits<Graph>::vertex_descriptor start = vertex(0, g);
72
73 // Compute BFS levels from vertex 0
74 property_map<Graph, vertex_distance_t>::type distance =
75 get(vertex_distance, g);
76
77 // Initialize distances to infinity and set reduction operation to 'min'
78 BGL_FORALL_VERTICES(v, g, Graph) {
79 put(distance, v, (std::numeric_limits<std::size_t>::max)());
80 }
81 distance.set_reduce(boost::graph::distributed::choose_min_reducer<std::size_t>());
82
83 put(distance, start, 0);
84 breadth_first_search
85 (g, start,
86 visitor(make_bfs_visitor(record_distances(distance, on_tree_edge()))));
87
88 // Output a Graphviz DOT file
89 std::string outfile;
90
91 if (argc > 2)
92 outfile = argv[2];
93 else {
94 outfile = filename;
95 size_t i = outfile.rfind('.');
96 if (i != std::string::npos)
97 outfile.erase(outfile.begin() + i, outfile.end());
98 outfile += "-bfs.dot";
99 }
100
101 if (process_id(process_group(g)) == 0) {
102 std::cout << "Writing GraphViz output to " << outfile << "... ";
103 std::cout.flush();
104 }
105 write_graphviz(outfile, g,
106 make_label_writer(distance));
107 if (process_id(process_group(g)) == 0)
108 std::cout << "Done." << std::endl;
109
110 return 0;
111 }
112