1 //=======================================================================
2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
3 // Copyright 2004 Douglas Gregor
4 // Copyright (C) 2006-2008
5
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
10 #include <boost/graph/use_mpi.hpp>
11 #include <boost/config.hpp>
12 #include <boost/throw_exception.hpp>
13 #include <boost/serialization/vector.hpp>
14 #include <boost/graph/depth_first_search.hpp>
15 #include <boost/graph/distributed/mpi_process_group.hpp>
16 #include <boost/graph/distributed/adjacency_list.hpp>
17 #include <boost/test/minimal.hpp>
18 #include <iostream>
19
20 #ifdef BOOST_NO_EXCEPTIONS
21 void
throw_exception(std::exception const & ex)22 boost::throw_exception(std::exception const& ex)
23 {
24 std::cout << ex.what() << std::endl;
25 abort();
26 }
27 #endif
28
29 using namespace boost;
30 using boost::graph::distributed::mpi_process_group;
31
32 // Set up the vertex names
33 enum vertex_id_t { u, v, w, x, y, z, N };
34 char vertex_names[] = { 'u', 'v', 'w', 'x', 'y', 'z' };
35
36 template<typename Vertex, typename Graph>
get_vertex_name(Vertex v,const Graph & g)37 char get_vertex_name(Vertex v, const Graph& g)
38 {
39 return vertex_names[g.distribution().global(owner(v), local(v))];
40 }
41
42 struct printing_dfs_visitor
43 {
44 template<typename Vertex, typename Graph>
initialize_vertexprinting_dfs_visitor45 void initialize_vertex(Vertex v, const Graph& g)
46 {
47 vertex_event("initialize_vertex", v, g);
48 }
49
50 template<typename Vertex, typename Graph>
start_vertexprinting_dfs_visitor51 void start_vertex(Vertex v, const Graph& g)
52 {
53 vertex_event("start_vertex", v, g);
54 }
55
56 template<typename Vertex, typename Graph>
discover_vertexprinting_dfs_visitor57 void discover_vertex(Vertex v, const Graph& g)
58 {
59 vertex_event("discover_vertex", v, g);
60 }
61
62 template<typename Edge, typename Graph>
examine_edgeprinting_dfs_visitor63 void examine_edge(Edge e, const Graph& g)
64 {
65 edge_event("examine_edge", e, g);
66 }
67
68 template<typename Edge, typename Graph>
tree_edgeprinting_dfs_visitor69 void tree_edge(Edge e, const Graph& g)
70 {
71 edge_event("tree_edge", e, g);
72 }
73
74 template<typename Edge, typename Graph>
back_edgeprinting_dfs_visitor75 void back_edge(Edge e, const Graph& g)
76 {
77 edge_event("back_edge", e, g);
78 }
79
80 template<typename Edge, typename Graph>
forward_or_cross_edgeprinting_dfs_visitor81 void forward_or_cross_edge(Edge e, const Graph& g)
82 {
83 edge_event("forward_or_cross_edge", e, g);
84 }
85
86 template<typename Vertex, typename Graph>
finish_vertexprinting_dfs_visitor87 void finish_vertex(Vertex v, const Graph& g)
88 {
89 vertex_event("finish_vertex", v, g);
90 }
91
92 private:
93 template<typename Vertex, typename Graph>
vertex_eventprinting_dfs_visitor94 void vertex_event(const char* name, Vertex v, const Graph& g)
95 {
96 std::cerr << "#" << process_id(g.process_group()) << ": " << name << "("
97 << get_vertex_name(v, g) << ": " << local(v) << "@" << owner(v)
98 << ")\n";
99 }
100
101 template<typename Edge, typename Graph>
edge_eventprinting_dfs_visitor102 void edge_event(const char* name, Edge e, const Graph& g)
103 {
104 std::cerr << "#" << process_id(g.process_group()) << ": " << name << "("
105 << get_vertex_name(source(e, g), g) << ": "
106 << local(source(e, g)) << "@" << owner(source(e, g)) << ", "
107 << get_vertex_name(target(e, g), g) << ": "
108 << local(target(e, g)) << "@" << owner(target(e, g)) << ")\n";
109 }
110
111 };
112
113 void
test_distributed_dfs()114 test_distributed_dfs()
115 {
116 typedef adjacency_list<listS,
117 distributedS<mpi_process_group, vecS>,
118 undirectedS,
119 // Vertex properties
120 property<vertex_color_t, default_color_type> >
121 Graph;
122 typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
123
124 // Specify the edges in the graph
125 typedef std::pair<int, int> E;
126 E edge_array[] = { E(u, v), E(u, w), E(u, x), E(x, v), E(y, x),
127 E(v, y), E(w, y), E(w, z), E(z, z) };
128 Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(E), N);
129
130 std::vector<vertex_descriptor> parent(num_vertices(g));
131 std::vector<vertex_descriptor> explore(num_vertices(g));
132
133 boost::graph::tsin_depth_first_visit
134 (g,
135 vertex(u, g),
136 printing_dfs_visitor(),
137 get(vertex_color, g),
138 make_iterator_property_map(parent.begin(), get(vertex_index, g)),
139 make_iterator_property_map(explore.begin(), get(vertex_index, g)),
140 get(vertex_index, g));
141
142 #if 0
143 std::size_t correct_parents1[N] = {u, u, y, y, v, w};
144 std::size_t correct_parents2[N] = {u, u, y, v, x, w};
145 #endif
146
147 for (std::size_t i = 0; i < N; ++i) {
148 vertex_descriptor v = vertex(i, g);
149 if (owner(v) == process_id(g.process_group())) {
150 std::cout << "parent(" << get_vertex_name(v, g) << ") = "
151 << get_vertex_name(parent[v.local], g) << std::endl;
152
153 }
154 }
155
156 if (false) {
157 depth_first_visit(g, vertex(u, g), printing_dfs_visitor());
158 }
159 }
160
161 int
test_main(int argc,char * argv[])162 test_main(int argc, char* argv[])
163 {
164 mpi::environment env(argc, argv);
165 test_distributed_dfs();
166 return 0;
167 }
168