]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(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(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 |