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, boost::no_property, boost::property<boost::edge_weight_t, int> > undirected_graph;
29 typedef boost::property_map<undirected_graph, boost::edge_weight_t>::type weight_map_type;
30 typedef boost::property_traits<weight_map_type>::value_type weight_type;
31
32 typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> undirected_unweighted_graph;
33
34 std::string test_dir;
35
init_unit_test_suite(int argc,char * argv[])36 boost::unit_test::test_suite* init_unit_test_suite( int argc, char* argv[] ) {
37 if (argc != 2) {
38 std::cerr << "Usage: " << argv[0] << " path-to-libs-graph-test" << std::endl;
39 throw boost::unit_test::framework::setup_error("Invalid command line arguments");
40 }
41 test_dir = argv[1];
42 return 0;
43 }
44
45 struct edge_t
46 {
47 unsigned long first;
48 unsigned long second;
49 };
50
51 template <typename Graph, typename KeyedUpdatablePriorityQueue>
52 class mas_edge_connectivity_visitor : public boost::default_mas_visitor {
53 public:
54 typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
55 typedef typename KeyedUpdatablePriorityQueue::key_type weight_type;
56 #if 0
57 mas_edge_connectivity_visitor(const mas_edge_connectivity_visitor<Graph, KeyedUpdatablePriorityQueue>& r)
58 : m_pq(r.m_pq), m_curr(r.m_curr), m_prev(r.m_prev),
59 m_reach_weight(r.m_reach_weight) {
60 BOOST_TEST_MESSAGE( "COPY CTOR" );
61 }
62 #endif
mas_edge_connectivity_visitor(KeyedUpdatablePriorityQueue & pq)63 explicit mas_edge_connectivity_visitor(KeyedUpdatablePriorityQueue& pq)
64 : m_pq(pq),
65 m_curr(new vertex_descriptor(0)), m_prev(new vertex_descriptor(0)),
66 m_reach_weight(new weight_type(0)) {
67 // BOOST_TEST_MESSAGE( "CTOR" );
68 }
69
clear()70 void clear() {
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) {
start_vertex(vertex_descriptor u,const Graph & g)78 void start_vertex(vertex_descriptor u, const Graph& g) {
79 *m_prev = *m_curr;
80 *m_curr = u;
81 //BOOST_TEST_MESSAGE( "Initializing Vertex(weight): " << u << "(" << *m_reach_weight << ")" );
82 *m_reach_weight = get(m_pq.keys(), u);
83 }
84
curr() const85 vertex_descriptor curr() const { return *m_curr; }
prev() const86 vertex_descriptor prev() const { return *m_prev; }
reach_weight() const87 weight_type reach_weight() const { return *m_reach_weight; }
88
89 private:
90
91 const KeyedUpdatablePriorityQueue& m_pq;
92 boost::shared_ptr<vertex_descriptor> m_curr, m_prev;
93 boost::shared_ptr<weight_type> m_reach_weight;
94 };
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.
BOOST_AUTO_TEST_CASE(test0)101 BOOST_AUTO_TEST_CASE(test0)
102 {
103 typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
104 typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
105
106 edge_t edges[] = {{0, 1}, {1, 2}, {2, 3},
107 {0, 4}, {1, 4}, {1, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 5}, {5, 6}, {6, 7}};
108 weight_type ws[] = {2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3};
109 undirected_graph g(edges, edges + 12, ws, 8, 12);
110
111 weight_map_type weights = get(boost::edge_weight, g);
112
113 std::map<vertex_descriptor, vertex_descriptor> assignment;
114 boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
115
116 typedef boost::shared_array_property_map<weight_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> distances_type;
117 distances_type distances = boost::make_shared_array_property_map(num_vertices(g), weight_type(0), get(boost::vertex_index, g));
118 typedef std::vector<vertex_descriptor>::size_type index_in_heap_type;
119 typedef boost::shared_array_property_map<index_in_heap_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> indicesInHeap_type;
120 indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map(num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g));
121 boost::d_ary_heap_indirect<vertex_descriptor, 22, indicesInHeap_type, distances_type, std::greater<weight_type> > pq(distances, indicesInHeap);
122
123 mas_edge_connectivity_visitor<undirected_graph,boost::d_ary_heap_indirect<vertex_descriptor, 22, indicesInHeap_type, distances_type, std::greater<weight_type> > > test_vis(pq);
124
125 boost::maximum_adjacency_search(g,
126 boost::weight_map(weights).
127 visitor(test_vis).
128 root_vertex(*vertices(g).first).
129 vertex_assignment_map(assignments).
130 max_priority_queue(pq));
131
132 BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
133 BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
134 BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
135
136 test_vis.clear();
137 boost::maximum_adjacency_search(g,
138 boost::weight_map(weights).
139 visitor(test_vis).
140 root_vertex(*vertices(g).first).
141 max_priority_queue(pq));
142
143 BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
144 BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
145 BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
146
147 test_vis.clear();
148 boost::maximum_adjacency_search(g,
149 boost::weight_map(weights).
150 visitor(test_vis).
151 max_priority_queue(pq));
152
153 BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
154 BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
155 BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
156
157 boost::maximum_adjacency_search(g,
158 boost::weight_map(weights).
159 visitor(boost::make_mas_visitor(boost::null_visitor())));
160
161 boost::maximum_adjacency_search(g,
162 boost::weight_map(weights));
163
164 boost::maximum_adjacency_search(g,
165 boost::root_vertex(*vertices(g).first));
166
167 test_vis.clear();
168 boost::maximum_adjacency_search(g,
169 boost::weight_map(boost::make_constant_property<edge_descriptor>(weight_type(1))).
170 visitor(test_vis).
171 max_priority_queue(pq));
172 BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
173 BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(3));
174 BOOST_CHECK_EQUAL(test_vis.reach_weight(), 2);
175
176 }
177
178 // Check the unweighted case
179 // with and without providing a weight_map
BOOST_AUTO_TEST_CASE(test1)180 BOOST_AUTO_TEST_CASE(test1)
181 {
182 typedef boost::graph_traits<undirected_unweighted_graph>::vertex_descriptor vertex_descriptor;
183 typedef boost::graph_traits<undirected_unweighted_graph>::edge_descriptor edge_descriptor;
184
185 edge_t edge_list[] = {{0, 1}, {1, 2}, {2, 3},
186 {0, 4}, {1, 4}, {1, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 5}, {5, 6}, {6, 7}};
187 undirected_unweighted_graph g(edge_list, edge_list + 12, 8);
188
189 std::map<vertex_descriptor, vertex_descriptor> assignment;
190 boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
191
192 typedef unsigned weight_type;
193 typedef boost::shared_array_property_map<weight_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> distances_type;
194 distances_type distances = boost::make_shared_array_property_map(num_vertices(g), weight_type(0), get(boost::vertex_index, g));
195 typedef std::vector<vertex_descriptor>::size_type index_in_heap_type;
196 typedef boost::shared_array_property_map<index_in_heap_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> indicesInHeap_type;
197 indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map(num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g));
198 boost::d_ary_heap_indirect<vertex_descriptor, 22, indicesInHeap_type, distances_type, std::greater<weight_type> > pq(distances, indicesInHeap);
199
200 mas_edge_connectivity_visitor<undirected_unweighted_graph,boost::d_ary_heap_indirect<vertex_descriptor, 22, indicesInHeap_type, distances_type, std::greater<weight_type> > > test_vis(pq);
201
202 boost::maximum_adjacency_search(g,
203 boost::weight_map(boost::make_constant_property<edge_descriptor>(weight_type(1))).visitor(test_vis).max_priority_queue(pq));
204
205 BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
206 BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(3));
207 BOOST_CHECK_EQUAL(test_vis.reach_weight(), weight_type(2));
208
209 weight_type ws[] = {2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3};
210 std::map<edge_descriptor, weight_type> wm;
211
212 weight_type i = 0;
213 BGL_FORALL_EDGES(e, g, undirected_unweighted_graph) {
214 wm[e] = ws[i];
215 ++i;
216 }
217 boost::associative_property_map<std::map<edge_descriptor, weight_type> > ws_map(wm);
218
219 boost::maximum_adjacency_search(g, boost::weight_map(ws_map).visitor(test_vis).max_priority_queue(pq));
220 BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
221 BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
222 BOOST_CHECK_EQUAL(test_vis.reach_weight(), weight_type(5));
223
224 }
225
226 #include <boost/graph/iteration_macros_undef.hpp>
227
228