1 // Copyright (C) 2007-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 #include <boost/graph/use_mpi.hpp>
8 #include <boost/config.hpp>
9 #include <boost/throw_exception.hpp>
10 #include <boost/mpl/print.hpp>
11 #include <boost/graph/distributed/adjacency_list.hpp>
12 #include <boost/graph/distributed/mpi_process_group.hpp>
13 #include <boost/graph/iteration_macros.hpp>
14 #include <boost/test/minimal.hpp>
15 #include <string>
16 #include <iostream>
17
18 #ifdef BOOST_NO_EXCEPTIONS
19 void
throw_exception(std::exception const & ex)20 boost::throw_exception(std::exception const& ex)
21 {
22 std::cout << ex.what() << std::endl;
23 abort();
24 }
25 #endif
26
27 using namespace boost;
28 using boost::graph::distributed::mpi_process_group;
29
30 /// City structure to be attached to each vertex
31 struct City {
CityCity32 City() {}
33
CityCity34 City(const std::string& name, int population = -1)
35 : name(name), population(population) { }
36
37 template<typename Archiver>
serializeCity38 void serialize(Archiver& ar, const unsigned int /*version*/)
39 {
40 ar & name & population;
41 }
42
43 std::string name;
44 int population;
45 };
46
47 /// Our distribution function
48 template<typename T>
49 struct named_vertices_hashed_distribution
50 {
51 template<typename ProcessGroup>
named_vertices_hashed_distributionnamed_vertices_hashed_distribution52 named_vertices_hashed_distribution(const ProcessGroup& pg,
53 std::size_t /*num_vertices*/ = 0)
54 : n(num_processes(pg)) { }
55
operator ()named_vertices_hashed_distribution56 int operator()(const T& value) const
57 {
58 return hasher(value) % n;
59 }
60
61 std::size_t n;
62 boost::hash<T> hasher;
63 };
64
65 typedef named_vertices_hashed_distribution<std::string> hasher_type;
66
67 namespace boost { namespace graph {
68
69 /// Use the City name as a key for indexing cities in a graph
70 template<>
71 struct internal_vertex_name<City>
72 {
73 typedef multi_index::member<City, std::string, &City::name> type;
74 };
75
76 /// Allow the graph to build cities given only their names (filling in
77 /// the defaults for fields).
78 template<>
79 struct internal_vertex_constructor<City>
80 {
81 typedef vertex_from_name<City> type;
82 };
83
84 // namespace distributed
85 // {
86 // /// Use the City name as the source for the distribution hasher
87 // ///
88 // /// This is currently needed in addition to the specification of this
89 // /// hasher functor as the 3rd template parameter to the distributedS
90 // /// template.
91 // template<>
92 // struct internal_vertex_name_distribution<City>
93 // {
94 // typedef named_vertices_hashed_distribution<std::string> type;
95 // };
96 // }
97
98 } } // end namespace boost::graph
99
100 /// Our road map, where each of the vertices are cities
101 typedef boost::adjacency_list<vecS,
102 distributedS<mpi_process_group, vecS, hasher_type>,
103 bidirectionalS, City> RoadMap;
104 typedef graph_traits<RoadMap>::vertex_descriptor Vertex;
105
test_main(int argc,char ** argv)106 int test_main(int argc, char** argv)
107 {
108 boost::mpi::environment env(argc, argv);
109
110 mpi_process_group pg;
111 RoadMap map; // (pg, hasher_type(pg));
112
113 int rank = process_id(pg);
114 bool i_am_root = rank == 0;
115
116 /// Create vertices for Bloomington, Indianapolis, Chicago. Everyone will
117 /// try to do this, but only one of each vertex will be added.
118 Vertex bloomington = add_vertex(City("Bloomington", 69291), map);
119 Vertex chicago = add_vertex(City("Chicago", 9500000), map);
120 Vertex indianapolis = add_vertex(City("Indianapolis", 791926), map);
121
122 BGL_FORALL_VERTICES(city, map, RoadMap)
123 std::cout << rank << ": " << map[city].name << ", population "
124 << map[city].population << std::endl;
125
126 BOOST_CHECK(*find_vertex("Bloomington", map) == bloomington);
127 BOOST_CHECK(*find_vertex("Indianapolis", map) == indianapolis);
128 BOOST_CHECK(*find_vertex("Chicago", map) == chicago);
129
130 if (i_am_root) {
131 add_edge(bloomington, "Indianapolis", map);
132 add_edge("Indianapolis", chicago, map);
133 add_edge("Indianapolis", "Cincinnati", map);
134 }
135
136 synchronize(map);
137
138 {
139 property_map<RoadMap, std::string City::*>::type
140 city_name = get(&City::name, map);
141
142 BGL_FORALL_EDGES(road, map, RoadMap)
143 std::cout << rank << ": " << get(city_name, source(road, map)) << " -> "
144 << get(city_name, target(road, map)) << std::endl;
145
146 synchronize(map);
147 }
148
149 // Make sure the vertex for "Cincinnati" was created implicitly
150 Vertex cincinnati = *find_vertex("Cincinnati", map);
151 if (get(get(vertex_owner, map), cincinnati)
152 == process_id(map.process_group()))
153 BOOST_CHECK(map[cincinnati].population == -1);
154
155 synchronize(map);
156
157 return 0;
158 }
159