1 | // Copyright Fernando Vilas 2012. |
2 | // Based on stoer_wagner_test.cpp by Daniel Trebbien. |
3 | // Distributed under the Boost Software License, Version 1.0. |
4 | // (See accompanying file LICENSE_1_0.txt or the copy at |
5 | // http://www.boost.org/LICENSE_1_0.txt) |
6 | |
7 | #include <fstream> |
8 | #include <iostream> |
9 | #include <map> |
10 | #include <vector> |
11 | #include <string> |
12 | #include <boost/graph/adjacency_list.hpp> |
13 | #include <boost/graph/connected_components.hpp> |
14 | #include <boost/graph/exception.hpp> |
15 | #include <boost/graph/graph_traits.hpp> |
16 | #include <boost/graph/read_dimacs.hpp> |
17 | #include <boost/graph/maximum_adjacency_search.hpp> |
18 | #include <boost/graph/visitors.hpp> |
19 | #include <boost/graph/property_maps/constant_property_map.hpp> |
20 | #include <boost/property_map/property_map.hpp> |
21 | #include <boost/core/lightweight_test.hpp> |
22 | #include <boost/tuple/tuple.hpp> |
23 | #include <boost/tuple/tuple_comparison.hpp> |
24 | #include <boost/tuple/tuple_io.hpp> |
25 | |
26 | #include <boost/graph/iteration_macros.hpp> |
27 | |
28 | typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, |
29 | boost::no_property, boost::property< boost::edge_weight_t, int > > |
30 | undirected_graph; |
31 | typedef boost::property_map< undirected_graph, boost::edge_weight_t >::type |
32 | weight_map_type; |
33 | typedef boost::property_traits< weight_map_type >::value_type weight_type; |
34 | |
35 | typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS > |
36 | undirected_unweighted_graph; |
37 | |
38 | std::string test_dir; |
39 | |
40 | struct edge_t |
41 | { |
42 | unsigned long first; |
43 | unsigned long second; |
44 | }; |
45 | |
46 | template < typename Graph, typename KeyedUpdatablePriorityQueue > |
47 | class mas_edge_connectivity_visitor : public boost::default_mas_visitor |
48 | { |
49 | public: |
50 | typedef typename boost::graph_traits< Graph >::vertex_descriptor |
51 | vertex_descriptor; |
52 | typedef typename KeyedUpdatablePriorityQueue::key_type weight_type; |
53 | #if 0 |
54 | mas_edge_connectivity_visitor(const mas_edge_connectivity_visitor<Graph, KeyedUpdatablePriorityQueue>& r) |
55 | : m_pq(r.m_pq), m_curr(r.m_curr), m_prev(r.m_prev), |
56 | m_reach_weight(r.m_reach_weight) { |
57 | BOOST_TEST_MESSAGE( "COPY CTOR" ); |
58 | } |
59 | #endif |
60 | explicit mas_edge_connectivity_visitor(KeyedUpdatablePriorityQueue& pq) |
61 | : m_pq(pq) |
62 | , m_curr(new vertex_descriptor(0)) |
63 | , m_prev(new vertex_descriptor(0)) |
64 | , m_reach_weight(new weight_type(0)) |
65 | { |
66 | // BOOST_TEST_MESSAGE( "CTOR" ); |
67 | } |
68 | |
69 | void clear() |
70 | { |
71 | *m_curr = 0; |
72 | *m_prev = 0; |
73 | *m_reach_weight = 0; |
74 | } |
75 | |
76 | // template <typename Vertex> //, typename Graph> |
77 | // void start_vertex(Vertex u, const Graph& g) { |
78 | void start_vertex(vertex_descriptor u, const Graph& g) |
79 | { |
80 | *m_prev = *m_curr; |
81 | *m_curr = u; |
82 | // BOOST_TEST_MESSAGE( "Initializing Vertex(weight): " << u << "(" << |
83 | // *m_reach_weight << ")" ); |
84 | *m_reach_weight = get(m_pq.keys(), u); |
85 | } |
86 | |
87 | vertex_descriptor curr() const { return *m_curr; } |
88 | vertex_descriptor prev() const { return *m_prev; } |
89 | weight_type reach_weight() const { return *m_reach_weight; } |
90 | |
91 | private: |
92 | const KeyedUpdatablePriorityQueue& m_pq; |
93 | boost::shared_ptr< vertex_descriptor > m_curr, m_prev; |
94 | boost::shared_ptr< weight_type > m_reach_weight; |
95 | }; |
96 | |
97 | // the example from Stoer & Wagner (1997) |
98 | // Check various implementations of the ArgPack where |
99 | // the weights are provided in it, and one case where |
100 | // they are not. |
101 | void test0() |
102 | { |
103 | typedef boost::graph_traits< undirected_graph >::vertex_descriptor |
104 | vertex_descriptor; |
105 | typedef boost::graph_traits< undirected_graph >::edge_descriptor |
106 | edge_descriptor; |
107 | |
108 | edge_t edges[] = { { .first: 0, .second: 1 }, { .first: 1, .second: 2 }, { .first: 2, .second: 3 }, { .first: 0, .second: 4 }, { .first: 1, .second: 4 }, |
109 | { .first: 1, .second: 5 }, { .first: 2, .second: 6 }, { .first: 3, .second: 6 }, { .first: 3, .second: 7 }, { .first: 4, .second: 5 }, { .first: 5, .second: 6 }, { .first: 6, .second: 7 } }; |
110 | weight_type ws[] = { 2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3 }; |
111 | undirected_graph g(edges, edges + 12, ws, 8, 12); |
112 | |
113 | weight_map_type weights = get(p: boost::edge_weight, g); |
114 | |
115 | std::map< vertex_descriptor, vertex_descriptor > assignment; |
116 | boost::associative_property_map< |
117 | std::map< vertex_descriptor, vertex_descriptor > > |
118 | assignments(assignment); |
119 | |
120 | typedef boost::shared_array_property_map< weight_type, |
121 | boost::property_map< undirected_graph, |
122 | boost::vertex_index_t >::const_type > |
123 | distances_type; |
124 | distances_type distances = boost::make_shared_array_property_map( |
125 | n: num_vertices(g_: g), weight_type(0), index: get(p: boost::vertex_index, g)); |
126 | typedef std::vector< vertex_descriptor >::size_type index_in_heap_type; |
127 | typedef boost::shared_array_property_map< index_in_heap_type, |
128 | boost::property_map< undirected_graph, |
129 | boost::vertex_index_t >::const_type > |
130 | indicesInHeap_type; |
131 | indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map( |
132 | n: num_vertices(g_: g), index_in_heap_type(-1), index: get(p: boost::vertex_index, g)); |
133 | boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type, |
134 | distances_type, std::greater< weight_type > > |
135 | pq(distances, indicesInHeap); |
136 | |
137 | mas_edge_connectivity_visitor< undirected_graph, |
138 | boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type, |
139 | distances_type, std::greater< weight_type > > > |
140 | test_vis(pq); |
141 | |
142 | boost::maximum_adjacency_search(g, |
143 | params: boost::weight_map(p: weights) |
144 | .visitor(p: test_vis) |
145 | .root_vertex(p: *vertices(g_: g).first) |
146 | .vertex_assignment_map(p: assignments) |
147 | .max_priority_queue(p&: pq)); |
148 | |
149 | BOOST_TEST_EQ(test_vis.curr(), vertex_descriptor(7)); |
150 | BOOST_TEST_EQ(test_vis.prev(), vertex_descriptor(6)); |
151 | BOOST_TEST_EQ(test_vis.reach_weight(), 5); |
152 | |
153 | test_vis.clear(); |
154 | boost::maximum_adjacency_search(g, |
155 | params: boost::weight_map(p: weights) |
156 | .visitor(p: test_vis) |
157 | .root_vertex(p: *vertices(g_: g).first) |
158 | .max_priority_queue(p&: pq)); |
159 | |
160 | BOOST_TEST_EQ(test_vis.curr(), vertex_descriptor(7)); |
161 | BOOST_TEST_EQ(test_vis.prev(), vertex_descriptor(6)); |
162 | BOOST_TEST_EQ(test_vis.reach_weight(), 5); |
163 | |
164 | test_vis.clear(); |
165 | boost::maximum_adjacency_search( |
166 | g, params: boost::weight_map(p: weights).visitor(p: test_vis).max_priority_queue(p&: pq)); |
167 | |
168 | BOOST_TEST_EQ(test_vis.curr(), vertex_descriptor(7)); |
169 | BOOST_TEST_EQ(test_vis.prev(), vertex_descriptor(6)); |
170 | BOOST_TEST_EQ(test_vis.reach_weight(), 5); |
171 | |
172 | boost::maximum_adjacency_search(g, |
173 | params: boost::weight_map(p: weights).visitor( |
174 | p: boost::make_mas_visitor(vis: boost::null_visitor()))); |
175 | |
176 | boost::maximum_adjacency_search(g, params: boost::weight_map(p: weights)); |
177 | |
178 | boost::maximum_adjacency_search(g, params: boost::root_vertex(p: *vertices(g_: g).first)); |
179 | |
180 | test_vis.clear(); |
181 | boost::maximum_adjacency_search(g, |
182 | params: boost::weight_map( |
183 | p: boost::make_constant_property< edge_descriptor >(value: weight_type(1))) |
184 | .visitor(p: test_vis) |
185 | .max_priority_queue(p&: pq)); |
186 | BOOST_TEST_EQ(test_vis.curr(), vertex_descriptor(7)); |
187 | BOOST_TEST_EQ(test_vis.prev(), vertex_descriptor(3)); |
188 | BOOST_TEST_EQ(test_vis.reach_weight(), 2); |
189 | } |
190 | |
191 | // Check the unweighted case |
192 | // with and without providing a weight_map |
193 | void test1() |
194 | { |
195 | typedef boost::graph_traits< |
196 | undirected_unweighted_graph >::vertex_descriptor vertex_descriptor; |
197 | typedef boost::graph_traits< undirected_unweighted_graph >::edge_descriptor |
198 | edge_descriptor; |
199 | |
200 | edge_t edge_list[] = { { .first: 0, .second: 1 }, { .first: 1, .second: 2 }, { .first: 2, .second: 3 }, { .first: 0, .second: 4 }, { .first: 1, .second: 4 }, |
201 | { .first: 1, .second: 5 }, { .first: 2, .second: 6 }, { .first: 3, .second: 6 }, { .first: 3, .second: 7 }, { .first: 4, .second: 5 }, { .first: 5, .second: 6 }, { .first: 6, .second: 7 } }; |
202 | undirected_unweighted_graph g(edge_list, edge_list + 12, 8); |
203 | |
204 | std::map< vertex_descriptor, vertex_descriptor > assignment; |
205 | boost::associative_property_map< |
206 | std::map< vertex_descriptor, vertex_descriptor > > |
207 | assignments(assignment); |
208 | |
209 | typedef unsigned weight_type; |
210 | typedef boost::shared_array_property_map< weight_type, |
211 | boost::property_map< undirected_graph, |
212 | boost::vertex_index_t >::const_type > |
213 | distances_type; |
214 | distances_type distances = boost::make_shared_array_property_map( |
215 | n: num_vertices(g_: g), weight_type(0), index: get(p: boost::vertex_index, g)); |
216 | typedef std::vector< vertex_descriptor >::size_type index_in_heap_type; |
217 | typedef boost::shared_array_property_map< index_in_heap_type, |
218 | boost::property_map< undirected_graph, |
219 | boost::vertex_index_t >::const_type > |
220 | indicesInHeap_type; |
221 | indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map( |
222 | n: num_vertices(g_: g), index_in_heap_type(-1), index: get(p: boost::vertex_index, g)); |
223 | boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type, |
224 | distances_type, std::greater< weight_type > > |
225 | pq(distances, indicesInHeap); |
226 | |
227 | mas_edge_connectivity_visitor< undirected_unweighted_graph, |
228 | boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type, |
229 | distances_type, std::greater< weight_type > > > |
230 | test_vis(pq); |
231 | |
232 | boost::maximum_adjacency_search(g, |
233 | params: boost::weight_map( |
234 | p: boost::make_constant_property< edge_descriptor >(value: weight_type(1))) |
235 | .visitor(p: test_vis) |
236 | .max_priority_queue(p&: pq)); |
237 | |
238 | BOOST_TEST_EQ(test_vis.curr(), vertex_descriptor(7)); |
239 | BOOST_TEST_EQ(test_vis.prev(), vertex_descriptor(3)); |
240 | BOOST_TEST_EQ(test_vis.reach_weight(), weight_type(2)); |
241 | |
242 | weight_type ws[] = { 2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3 }; |
243 | std::map< edge_descriptor, weight_type > wm; |
244 | |
245 | weight_type i = 0; |
246 | BGL_FORALL_EDGES(e, g, undirected_unweighted_graph) |
247 | { |
248 | wm[e] = ws[i]; |
249 | ++i; |
250 | } |
251 | boost::associative_property_map< std::map< edge_descriptor, weight_type > > |
252 | ws_map(wm); |
253 | |
254 | boost::maximum_adjacency_search( |
255 | g, params: boost::weight_map(p: ws_map).visitor(p: test_vis).max_priority_queue(p&: pq)); |
256 | BOOST_TEST_EQ(test_vis.curr(), vertex_descriptor(7)); |
257 | BOOST_TEST_EQ(test_vis.prev(), vertex_descriptor(6)); |
258 | BOOST_TEST_EQ(test_vis.reach_weight(), weight_type(5)); |
259 | } |
260 | |
261 | #include <boost/graph/iteration_macros_undef.hpp> |
262 | |
263 | int main(int argc, char* argv[]) |
264 | { |
265 | if (BOOST_TEST(argc == 2)) { |
266 | test_dir = argv[1]; |
267 | test0(); |
268 | test1(); |
269 | } |
270 | return boost::report_errors(); |
271 | } |
272 | |