1 | // |
2 | //======================================================================= |
3 | // Copyright 2012 Fernando Vilas |
4 | // 2010 Daniel Trebbien |
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 | // |
11 | |
12 | // The maximum adjacency search algorithm was originally part of the |
13 | // Stoer-Wagner min cut implementation by Daniel Trebbien. It has been |
14 | // broken out into its own file to be a public search algorithm, with |
15 | // visitor concepts. |
16 | #ifndef BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H |
17 | #define BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H |
18 | |
19 | /** |
20 | * This is an implementation of the maximum adjacency search on an |
21 | * undirected graph. It allows a visitor object to perform some |
22 | * operation on each vertex as that vertex is visited. |
23 | * |
24 | * The algorithm runs as follows: |
25 | * |
26 | * Initialize all nodes to be unvisited (reach count = 0) |
27 | * and call vis.initialize_vertex |
28 | * For i = number of nodes in graph downto 1 |
29 | * Select the unvisited node with the highest reach count |
30 | * The user provides the starting node to break the first tie, |
31 | * but future ties are broken arbitrarily |
32 | * Visit the node by calling vis.start_vertex |
33 | * Increment the reach count for all unvisited neighbors |
34 | * and call vis.examine_edge for each of these edges |
35 | * Mark the node as visited and call vis.finish_vertex |
36 | * |
37 | */ |
38 | |
39 | #include <boost/concept_check.hpp> |
40 | #include <boost/concept/assert.hpp> |
41 | #include <boost/graph/buffer_concepts.hpp> |
42 | #include <boost/graph/exception.hpp> |
43 | #include <boost/graph/graph_concepts.hpp> |
44 | #include <boost/graph/iteration_macros.hpp> |
45 | #include <boost/graph/named_function_params.hpp> |
46 | #include <boost/graph/visitors.hpp> |
47 | #include <boost/tuple/tuple.hpp> |
48 | |
49 | #include <set> |
50 | |
51 | namespace boost { |
52 | template <class Visitor, class Graph> |
53 | struct MASVisitorConcept { |
54 | void constraints() { |
55 | boost::function_requires< boost::CopyConstructibleConcept<Visitor> >(); |
56 | vis.initialize_vertex(u, g); |
57 | vis.start_vertex(u, g); |
58 | vis.examine_edge(e, g); |
59 | vis.finish_vertex(u, g); |
60 | } |
61 | Visitor vis; |
62 | Graph g; |
63 | typename boost::graph_traits<Graph>::vertex_descriptor u; |
64 | typename boost::graph_traits<Graph>::edge_descriptor e; |
65 | }; |
66 | |
67 | template <class Visitors = null_visitor> |
68 | class mas_visitor { |
69 | public: |
70 | mas_visitor() { } |
71 | mas_visitor(Visitors vis) : m_vis(vis) { } |
72 | |
73 | template <class Vertex, class Graph> |
74 | void |
75 | initialize_vertex(Vertex u, Graph& g) |
76 | { |
77 | invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex()); |
78 | } |
79 | |
80 | template <class Vertex, class Graph> |
81 | void |
82 | start_vertex(Vertex u, Graph& g) |
83 | { |
84 | invoke_visitors(m_vis, u, g, ::boost::on_start_vertex()); |
85 | } |
86 | |
87 | template <class Edge, class Graph> |
88 | void |
89 | examine_edge(Edge e, Graph& g) |
90 | { |
91 | invoke_visitors(m_vis, e, g, ::boost::on_examine_edge()); |
92 | } |
93 | |
94 | template <class Vertex, class Graph> |
95 | void |
96 | finish_vertex(Vertex u, Graph& g) |
97 | { |
98 | invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex()); |
99 | } |
100 | |
101 | BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,mas) |
102 | BOOST_GRAPH_EVENT_STUB(on_start_vertex,mas) |
103 | BOOST_GRAPH_EVENT_STUB(on_examine_edge,mas) |
104 | BOOST_GRAPH_EVENT_STUB(on_finish_vertex,mas) |
105 | |
106 | protected: |
107 | Visitors m_vis; |
108 | }; |
109 | template <class Visitors> |
110 | mas_visitor<Visitors> |
111 | make_mas_visitor(Visitors vis) { |
112 | return mas_visitor<Visitors>(vis); |
113 | } |
114 | typedef mas_visitor<> default_mas_visitor; |
115 | |
116 | namespace detail { |
117 | template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue> |
118 | void |
119 | maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, const typename boost::graph_traits<Graph>::vertex_descriptor start, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq) { |
120 | typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor; |
121 | typedef typename boost::property_traits<WeightMap>::value_type weight_type; |
122 | |
123 | std::set<vertex_descriptor> assignedVertices; |
124 | |
125 | // initialize `assignments` (all vertices are initially |
126 | // assigned to themselves) |
127 | BGL_FORALL_VERTICES_T(v, g, Graph) { |
128 | put(assignments, v, v); |
129 | } |
130 | |
131 | typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys(); |
132 | |
133 | // set number of visited neighbors for all vertices to 0 |
134 | BGL_FORALL_VERTICES_T(v, g, Graph) { |
135 | if (v == get(assignments, v)) { // foreach u \in V do |
136 | put(keys, v, weight_type(0)); vis.initialize_vertex(v, g); |
137 | |
138 | pq.push(v); |
139 | } |
140 | } |
141 | BOOST_ASSERT(pq.size() >= 2); |
142 | |
143 | // Give the starting vertex high priority |
144 | put(keys, start, get(keys, start) + num_vertices(g) + 1); |
145 | pq.update(start); |
146 | |
147 | // start traversing the graph |
148 | //vertex_descriptor s, t; |
149 | weight_type w; |
150 | while (!pq.empty()) { // while PQ \neq {} do |
151 | const vertex_descriptor u = pq.top(); // u = extractmax(PQ) |
152 | w = get(keys, u); vis.start_vertex(u, g); |
153 | pq.pop(); // vis.start_vertex(u, g); |
154 | |
155 | BGL_FORALL_OUTEDGES_T(u, e, g, Graph) { // foreach (u, v) \in E do |
156 | vis.examine_edge(e, g); |
157 | |
158 | const vertex_descriptor v = get(assignments, target(e, g)); |
159 | |
160 | if (pq.contains(v)) { // if v \in PQ then |
161 | put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v)) |
162 | pq.update(v); |
163 | } |
164 | } |
165 | |
166 | typename std::set<vertex_descriptor>::const_iterator assignedVertexIt, assignedVertexEnd = assignedVertices.end(); |
167 | for (assignedVertexIt = assignedVertices.begin(); assignedVertexIt != assignedVertexEnd; ++assignedVertexIt) { |
168 | const vertex_descriptor uPrime = *assignedVertexIt; |
169 | |
170 | if (get(assignments, uPrime) == u) { |
171 | BGL_FORALL_OUTEDGES_T(uPrime, e, g, Graph) { // foreach (u, v) \in E do |
172 | vis.examine_edge(e, g); |
173 | |
174 | const vertex_descriptor v = get(assignments, target(e, g)); |
175 | |
176 | if (pq.contains(v)) { // if v \in PQ then |
177 | put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v)) |
178 | pq.update(v); |
179 | } |
180 | } |
181 | } |
182 | } |
183 | vis.finish_vertex(u, g); |
184 | } |
185 | } |
186 | } // end namespace detail |
187 | |
188 | template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue> |
189 | void |
190 | maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, const typename boost::graph_traits<Graph>::vertex_descriptor start, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq) { |
191 | BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<Graph>)); |
192 | BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<Graph>)); |
193 | typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor; |
194 | typedef typename boost::graph_traits<Graph>::vertices_size_type vertices_size_type; |
195 | typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor; |
196 | BOOST_CONCEPT_ASSERT((boost::Convertible<typename boost::graph_traits<Graph>::directed_category, boost::undirected_tag>)); |
197 | BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<WeightMap, edge_descriptor>)); |
198 | // typedef typename boost::property_traits<WeightMap>::value_type weight_type; |
199 | boost::function_requires< MASVisitorConcept<MASVisitor, Graph> >(); |
200 | BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<VertexAssignmentMap, vertex_descriptor>)); |
201 | BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<VertexAssignmentMap>::value_type>)); |
202 | BOOST_CONCEPT_ASSERT((boost::KeyedUpdatableQueueConcept<KeyedUpdatablePriorityQueue>)); |
203 | |
204 | vertices_size_type n = num_vertices(g); |
205 | if (n < 2) |
206 | throw boost::bad_graph("the input graph must have at least two vertices." ); |
207 | else if (!pq.empty()) |
208 | throw std::invalid_argument("the max-priority queue must be empty initially." ); |
209 | |
210 | detail::maximum_adjacency_search(g, weights, |
211 | vis, start, |
212 | assignments, pq); |
213 | } |
214 | |
215 | namespace graph { |
216 | namespace detail { |
217 | template <typename WeightMap> |
218 | struct mas_dispatch { |
219 | typedef void result_type; |
220 | template <typename Graph, typename ArgPack> |
221 | static result_type apply(const Graph& g, |
222 | //const bgl_named_params<P,T,R>& params, |
223 | const ArgPack& params, |
224 | WeightMap w) { |
225 | |
226 | using namespace boost::graph::keywords; |
227 | typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor; |
228 | typedef typename WeightMap::value_type weight_type; |
229 | |
230 | typedef boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > default_pq_gen_type; |
231 | |
232 | default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0))); |
233 | |
234 | typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params); |
235 | |
236 | boost::maximum_adjacency_search |
237 | (g, |
238 | w, |
239 | params [ _visitor | make_mas_visitor(vis: null_visitor())], |
240 | params [ _root_vertex | *vertices(g).first], |
241 | params [ _vertex_assignment_map | boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, params)], |
242 | pq |
243 | ); |
244 | } |
245 | }; |
246 | |
247 | template <> |
248 | struct mas_dispatch<boost::param_not_found> { |
249 | typedef void result_type; |
250 | |
251 | template <typename Graph, typename ArgPack> |
252 | static result_type apply(const Graph& g, |
253 | const ArgPack& params, |
254 | param_not_found) { |
255 | |
256 | using namespace boost::graph::keywords; |
257 | typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor; |
258 | |
259 | // get edge_weight_t as the weight type |
260 | typedef typename boost::property_map<Graph, edge_weight_t> WeightMap; |
261 | typedef typename WeightMap::value_type weight_type; |
262 | |
263 | typedef boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > default_pq_gen_type; |
264 | |
265 | default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0))); |
266 | |
267 | typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params); |
268 | |
269 | boost::maximum_adjacency_search |
270 | (g, |
271 | get(edge_weight, g), |
272 | params [ _visitor | make_mas_visitor(vis: null_visitor())], |
273 | params [ _root_vertex | *vertices(g).first], |
274 | params [ _vertex_assignment_map | boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, params)], |
275 | pq |
276 | ); |
277 | } |
278 | }; |
279 | } // end namespace detail |
280 | } // end namespace graph |
281 | |
282 | // Named parameter interface |
283 | //BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(maximum_adjacency_search, 1) |
284 | template <typename Graph, typename P, typename T, typename R> |
285 | void |
286 | maximum_adjacency_search (const Graph& g, |
287 | const bgl_named_params<P,T,R>& params) { |
288 | |
289 | typedef bgl_named_params<P, T, R> params_type; |
290 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) |
291 | |
292 | // do the dispatch based on WeightMap |
293 | typedef typename get_param_type<edge_weight_t, bgl_named_params<P,T,R> >::type W; |
294 | graph::detail::mas_dispatch<W>::apply(g, arg_pack, get_param(params, edge_weight)); |
295 | } |
296 | |
297 | namespace graph { |
298 | namespace detail { |
299 | template <typename Graph> |
300 | struct maximum_adjacency_search_impl { |
301 | typedef void result_type; |
302 | |
303 | template <typename ArgPack> |
304 | void |
305 | operator() (const Graph& g, const ArgPack& arg_pack) const { |
306 | // call the function that does the dispatching |
307 | typedef typename get_param_type<edge_weight_t, ArgPack >::type W; |
308 | graph::detail::mas_dispatch<W>::apply(g, arg_pack, get_param(arg_pack, edge_weight)); |
309 | } |
310 | }; |
311 | } // end namespace detail |
312 | BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(maximum_adjacency_search,1,5) |
313 | } // end namespace graph |
314 | |
315 | } // end namespace boost |
316 | |
317 | #include <boost/graph/iteration_macros_undef.hpp> |
318 | |
319 | #endif // BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H |
320 | |