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
28typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS,
29 boost::no_property, boost::property< boost::edge_weight_t, int > >
30 undirected_graph;
31typedef boost::property_map< undirected_graph, boost::edge_weight_t >::type
32 weight_map_type;
33typedef boost::property_traits< weight_map_type >::value_type weight_type;
34
35typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS >
36 undirected_unweighted_graph;
37
38std::string test_dir;
39
40struct edge_t
41{
42 unsigned long first;
43 unsigned long second;
44};
45
46template < typename Graph, typename KeyedUpdatablePriorityQueue >
47class mas_edge_connectivity_visitor : public boost::default_mas_visitor
48{
49public:
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
91private:
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.
101void 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
193void 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
263int 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

source code of boost/libs/graph/test/mas_test.cpp