1 // Copyright (C) 2004-2006 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 dijkstra_shortest_paths algorithm
11
12 // Enable PBGL interfaces to BGL algorithms
13 #include <boost/graph/use_mpi.hpp>
14
15 // Communication via MPI
16 #include <boost/graph/distributed/mpi_process_group.hpp>
17
18 // Dijkstra's single-source shortest paths algorithm
19 #include <boost/graph/dijkstra_shortest_paths.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 // Standard Library includes
31 #include <fstream>
32 #include <string>
33
34 #ifdef BOOST_NO_EXCEPTIONS
35 void
throw_exception(std::exception const & ex)36 boost::throw_exception(std::exception const& ex)
37 {
38 std::cout << ex.what() << std::endl;
39 abort();
40 }
41 #endif
42
43 using namespace boost;
44 using boost::graph::distributed::mpi_process_group;
45
46 /* An undirected, weighted graph with distance values stored on the
47 vertices. */
48 typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, undirectedS,
49 /*Vertex properties=*/property<vertex_distance_t, float>,
50 /*Edge properties=*/property<edge_weight_t, float> >
51 Graph;
52
main(int argc,char * argv[])53 int main(int argc, char* argv[])
54 {
55 boost::mpi::environment env(argc,argv);
56
57 // Parse command-line options
58 const char* filename = "weighted_graph.gr";
59 if (argc > 1) filename = argv[1];
60
61 // Open the METIS input file
62 std::ifstream in(filename);
63 graph::metis_reader reader(in);
64
65 // Load the graph using the default distribution
66 Graph g(reader.begin(), reader.end(), reader.weight_begin(),
67 reader.num_vertices());
68
69 // Get vertex 0 in the graph
70 graph_traits<Graph>::vertex_descriptor start = vertex(0, g);
71
72 // Compute shortest paths from vertex 0
73 dijkstra_shortest_paths(g, start,
74 distance_map(get(vertex_distance, g)));
75
76 // Output a Graphviz DOT file
77 std::string outfile = filename;
78 if (argc > 2)
79 outfile = argv[2];
80 else {
81 size_t i = outfile.rfind('.');
82 if (i != std::string::npos)
83 outfile.erase(outfile.begin() + i, outfile.end());
84 outfile += "-dijkstra.dot";
85 }
86
87 if (process_id(process_group(g)) == 0) {
88 std::cout << "Writing GraphViz output to " << outfile << "... ";
89 std::cout.flush();
90 }
91 write_graphviz(outfile, g,
92 make_label_writer(get(vertex_distance, g)),
93 make_label_writer(get(edge_weight, g)));
94 if (process_id(process_group(g)) == 0)
95 std::cout << "Done." << std::endl;
96
97 return 0;
98 }
99