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/test/unit_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
init_unit_test_suite(int argc,char * argv[])40 boost::unit_test::test_suite* init_unit_test_suite(int argc, char* argv[])
41 {
42 if (argc != 2)
43 {
44 std::cerr << "Usage: " << argv[0] << " path-to-libs-graph-test"
45 << std::endl;
46 throw boost::unit_test::framework::setup_error(
47 "Invalid command line arguments");
48 }
49 test_dir = argv[1];
50 return 0;
51 }
52
53 struct edge_t
54 {
55 unsigned long first;
56 unsigned long second;
57 };
58
59 template < typename Graph, typename KeyedUpdatablePriorityQueue >
60 class mas_edge_connectivity_visitor : public boost::default_mas_visitor
61 {
62 public:
63 typedef typename boost::graph_traits< Graph >::vertex_descriptor
64 vertex_descriptor;
65 typedef typename KeyedUpdatablePriorityQueue::key_type weight_type;
66 #if 0
67 mas_edge_connectivity_visitor(const mas_edge_connectivity_visitor<Graph, KeyedUpdatablePriorityQueue>& r)
68 : m_pq(r.m_pq), m_curr(r.m_curr), m_prev(r.m_prev),
69 m_reach_weight(r.m_reach_weight) {
70 BOOST_TEST_MESSAGE( "COPY CTOR" );
71 }
72 #endif
mas_edge_connectivity_visitor(KeyedUpdatablePriorityQueue & pq)73 explicit mas_edge_connectivity_visitor(KeyedUpdatablePriorityQueue& pq)
74 : m_pq(pq)
75 , m_curr(new vertex_descriptor(0))
76 , m_prev(new vertex_descriptor(0))
77 , m_reach_weight(new weight_type(0))
78 {
79 // BOOST_TEST_MESSAGE( "CTOR" );
80 }
81
clear()82 void clear()
83 {
84 *m_curr = 0;
85 *m_prev = 0;
86 *m_reach_weight = 0;
87 }
88
89 // template <typename Vertex> //, typename Graph>
90 // void start_vertex(Vertex u, const Graph& g) {
start_vertex(vertex_descriptor u,const Graph & g)91 void start_vertex(vertex_descriptor u, const Graph& g)
92 {
93 *m_prev = *m_curr;
94 *m_curr = u;
95 // BOOST_TEST_MESSAGE( "Initializing Vertex(weight): " << u << "(" <<
96 // *m_reach_weight << ")" );
97 *m_reach_weight = get(m_pq.keys(), u);
98 }
99
curr() const100 vertex_descriptor curr() const { return *m_curr; }
prev() const101 vertex_descriptor prev() const { return *m_prev; }
reach_weight() const102 weight_type reach_weight() const { return *m_reach_weight; }
103
104 private:
105 const KeyedUpdatablePriorityQueue& m_pq;
106 boost::shared_ptr< vertex_descriptor > m_curr, m_prev;
107 boost::shared_ptr< weight_type > m_reach_weight;
108 };
109
110 // the example from Stoer & Wagner (1997)
111 // Check various implementations of the ArgPack where
112 // the weights are provided in it, and one case where
113 // they are not.
BOOST_AUTO_TEST_CASE(test0)114 BOOST_AUTO_TEST_CASE(test0)
115 {
116 typedef boost::graph_traits< undirected_graph >::vertex_descriptor
117 vertex_descriptor;
118 typedef boost::graph_traits< undirected_graph >::edge_descriptor
119 edge_descriptor;
120
121 edge_t edges[] = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 0, 4 }, { 1, 4 },
122 { 1, 5 }, { 2, 6 }, { 3, 6 }, { 3, 7 }, { 4, 5 }, { 5, 6 }, { 6, 7 } };
123 weight_type ws[] = { 2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3 };
124 undirected_graph g(edges, edges + 12, ws, 8, 12);
125
126 weight_map_type weights = get(boost::edge_weight, g);
127
128 std::map< vertex_descriptor, vertex_descriptor > assignment;
129 boost::associative_property_map<
130 std::map< vertex_descriptor, vertex_descriptor > >
131 assignments(assignment);
132
133 typedef boost::shared_array_property_map< weight_type,
134 boost::property_map< undirected_graph,
135 boost::vertex_index_t >::const_type >
136 distances_type;
137 distances_type distances = boost::make_shared_array_property_map(
138 num_vertices(g), weight_type(0), get(boost::vertex_index, g));
139 typedef std::vector< vertex_descriptor >::size_type index_in_heap_type;
140 typedef boost::shared_array_property_map< index_in_heap_type,
141 boost::property_map< undirected_graph,
142 boost::vertex_index_t >::const_type >
143 indicesInHeap_type;
144 indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map(
145 num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g));
146 boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type,
147 distances_type, std::greater< weight_type > >
148 pq(distances, indicesInHeap);
149
150 mas_edge_connectivity_visitor< undirected_graph,
151 boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type,
152 distances_type, std::greater< weight_type > > >
153 test_vis(pq);
154
155 boost::maximum_adjacency_search(g,
156 boost::weight_map(weights)
157 .visitor(test_vis)
158 .root_vertex(*vertices(g).first)
159 .vertex_assignment_map(assignments)
160 .max_priority_queue(pq));
161
162 BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
163 BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
164 BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
165
166 test_vis.clear();
167 boost::maximum_adjacency_search(g,
168 boost::weight_map(weights)
169 .visitor(test_vis)
170 .root_vertex(*vertices(g).first)
171 .max_priority_queue(pq));
172
173 BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
174 BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
175 BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
176
177 test_vis.clear();
178 boost::maximum_adjacency_search(
179 g, boost::weight_map(weights).visitor(test_vis).max_priority_queue(pq));
180
181 BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
182 BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
183 BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
184
185 boost::maximum_adjacency_search(g,
186 boost::weight_map(weights).visitor(
187 boost::make_mas_visitor(boost::null_visitor())));
188
189 boost::maximum_adjacency_search(g, boost::weight_map(weights));
190
191 boost::maximum_adjacency_search(g, boost::root_vertex(*vertices(g).first));
192
193 test_vis.clear();
194 boost::maximum_adjacency_search(g,
195 boost::weight_map(
196 boost::make_constant_property< edge_descriptor >(weight_type(1)))
197 .visitor(test_vis)
198 .max_priority_queue(pq));
199 BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
200 BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(3));
201 BOOST_CHECK_EQUAL(test_vis.reach_weight(), 2);
202 }
203
204 // Check the unweighted case
205 // with and without providing a weight_map
BOOST_AUTO_TEST_CASE(test1)206 BOOST_AUTO_TEST_CASE(test1)
207 {
208 typedef boost::graph_traits<
209 undirected_unweighted_graph >::vertex_descriptor vertex_descriptor;
210 typedef boost::graph_traits< undirected_unweighted_graph >::edge_descriptor
211 edge_descriptor;
212
213 edge_t edge_list[] = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 0, 4 }, { 1, 4 },
214 { 1, 5 }, { 2, 6 }, { 3, 6 }, { 3, 7 }, { 4, 5 }, { 5, 6 }, { 6, 7 } };
215 undirected_unweighted_graph g(edge_list, edge_list + 12, 8);
216
217 std::map< vertex_descriptor, vertex_descriptor > assignment;
218 boost::associative_property_map<
219 std::map< vertex_descriptor, vertex_descriptor > >
220 assignments(assignment);
221
222 typedef unsigned weight_type;
223 typedef boost::shared_array_property_map< weight_type,
224 boost::property_map< undirected_graph,
225 boost::vertex_index_t >::const_type >
226 distances_type;
227 distances_type distances = boost::make_shared_array_property_map(
228 num_vertices(g), weight_type(0), get(boost::vertex_index, g));
229 typedef std::vector< vertex_descriptor >::size_type index_in_heap_type;
230 typedef boost::shared_array_property_map< index_in_heap_type,
231 boost::property_map< undirected_graph,
232 boost::vertex_index_t >::const_type >
233 indicesInHeap_type;
234 indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map(
235 num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g));
236 boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type,
237 distances_type, std::greater< weight_type > >
238 pq(distances, indicesInHeap);
239
240 mas_edge_connectivity_visitor< undirected_unweighted_graph,
241 boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type,
242 distances_type, std::greater< weight_type > > >
243 test_vis(pq);
244
245 boost::maximum_adjacency_search(g,
246 boost::weight_map(
247 boost::make_constant_property< edge_descriptor >(weight_type(1)))
248 .visitor(test_vis)
249 .max_priority_queue(pq));
250
251 BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
252 BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(3));
253 BOOST_CHECK_EQUAL(test_vis.reach_weight(), weight_type(2));
254
255 weight_type ws[] = { 2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3 };
256 std::map< edge_descriptor, weight_type > wm;
257
258 weight_type i = 0;
259 BGL_FORALL_EDGES(e, g, undirected_unweighted_graph)
260 {
261 wm[e] = ws[i];
262 ++i;
263 }
264 boost::associative_property_map< std::map< edge_descriptor, weight_type > >
265 ws_map(wm);
266
267 boost::maximum_adjacency_search(
268 g, boost::weight_map(ws_map).visitor(test_vis).max_priority_queue(pq));
269 BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
270 BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
271 BOOST_CHECK_EQUAL(test_vis.reach_weight(), weight_type(5));
272 }
273
274 #include <boost/graph/iteration_macros_undef.hpp>
275