1 | /** |
2 | * |
3 | * Copyright (c) 2010 Matthias Walter (xammy@xammy.homelinux.net) |
4 | * |
5 | * Authors: Matthias Walter |
6 | * |
7 | * Distributed under the Boost Software License, Version 1.0. (See |
8 | * accompanying file LICENSE_1_0.txt or copy at |
9 | * http://www.boost.org/LICENSE_1_0.txt) |
10 | * |
11 | */ |
12 | |
13 | #ifndef BOOST_GRAPH_BIPARTITE_HPP |
14 | #define BOOST_GRAPH_BIPARTITE_HPP |
15 | |
16 | #include <utility> |
17 | #include <vector> |
18 | #include <exception> |
19 | #include <boost/graph/properties.hpp> |
20 | #include <boost/graph/adjacency_list.hpp> |
21 | #include <boost/graph/depth_first_search.hpp> |
22 | #include <boost/graph/one_bit_color_map.hpp> |
23 | #include <boost/bind.hpp> |
24 | |
25 | namespace boost { |
26 | |
27 | namespace detail { |
28 | |
29 | /** |
30 | * The bipartite_visitor_error is thrown if an edge cannot be colored. |
31 | * The witnesses are the edges incident vertices. |
32 | */ |
33 | |
34 | template <typename Vertex> |
35 | struct bipartite_visitor_error: std::exception |
36 | { |
37 | std::pair <Vertex, Vertex> witnesses; |
38 | |
39 | bipartite_visitor_error (Vertex a, Vertex b) : |
40 | witnesses (a, b) |
41 | { |
42 | |
43 | } |
44 | |
45 | const char* what () const throw () |
46 | { |
47 | return "Graph is not bipartite." ; |
48 | } |
49 | }; |
50 | |
51 | /** |
52 | * Functor which colors edges to be non-monochromatic. |
53 | */ |
54 | |
55 | template <typename PartitionMap> |
56 | struct bipartition_colorize |
57 | { |
58 | typedef on_tree_edge event_filter; |
59 | |
60 | bipartition_colorize (PartitionMap partition_map) : |
61 | partition_map_ (partition_map) |
62 | { |
63 | |
64 | } |
65 | |
66 | template <typename Edge, typename Graph> |
67 | void operator() (Edge e, const Graph& g) |
68 | { |
69 | typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t; |
70 | typedef color_traits <typename property_traits <PartitionMap>::value_type> color_traits; |
71 | |
72 | vertex_descriptor_t source_vertex = source (e, g); |
73 | vertex_descriptor_t target_vertex = target (e, g); |
74 | if (get (partition_map_, source_vertex) == color_traits::white ()) |
75 | put (partition_map_, target_vertex, color_traits::black ()); |
76 | else |
77 | put (partition_map_, target_vertex, color_traits::white ()); |
78 | } |
79 | |
80 | private: |
81 | PartitionMap partition_map_; |
82 | }; |
83 | |
84 | /** |
85 | * Creates a bipartition_colorize functor which colors edges |
86 | * to be non-monochromatic. |
87 | * |
88 | * @param partition_map Color map for the bipartition |
89 | * @return The functor. |
90 | */ |
91 | |
92 | template <typename PartitionMap> |
93 | inline bipartition_colorize <PartitionMap> colorize_bipartition (PartitionMap partition_map) |
94 | { |
95 | return bipartition_colorize <PartitionMap> (partition_map); |
96 | } |
97 | |
98 | /** |
99 | * Functor which tests an edge to be monochromatic. |
100 | */ |
101 | |
102 | template <typename PartitionMap> |
103 | struct bipartition_check |
104 | { |
105 | typedef on_back_edge event_filter; |
106 | |
107 | bipartition_check (PartitionMap partition_map) : |
108 | partition_map_ (partition_map) |
109 | { |
110 | |
111 | } |
112 | |
113 | template <typename Edge, typename Graph> |
114 | void operator() (Edge e, const Graph& g) |
115 | { |
116 | typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t; |
117 | |
118 | vertex_descriptor_t source_vertex = source (e, g); |
119 | vertex_descriptor_t target_vertex = target (e, g); |
120 | if (get (partition_map_, source_vertex) == get (partition_map_, target_vertex)) |
121 | throw bipartite_visitor_error <vertex_descriptor_t> (source_vertex, target_vertex); |
122 | } |
123 | |
124 | private: |
125 | PartitionMap partition_map_; |
126 | }; |
127 | |
128 | /** |
129 | * Creates a bipartition_check functor which raises an error if a |
130 | * monochromatic edge is found. |
131 | * |
132 | * @param partition_map The map for a bipartition. |
133 | * @return The functor. |
134 | */ |
135 | |
136 | template <typename PartitionMap> |
137 | inline bipartition_check <PartitionMap> check_bipartition (PartitionMap partition_map) |
138 | { |
139 | return bipartition_check <PartitionMap> (partition_map); |
140 | } |
141 | |
142 | /** |
143 | * Find the beginning of a common suffix of two sequences |
144 | * |
145 | * @param sequence1 Pair of bidirectional iterators defining the first sequence. |
146 | * @param sequence2 Pair of bidirectional iterators defining the second sequence. |
147 | * @return Pair of iterators pointing to the beginning of the common suffix. |
148 | */ |
149 | |
150 | template <typename BiDirectionalIterator1, typename BiDirectionalIterator2> |
151 | inline std::pair <BiDirectionalIterator1, BiDirectionalIterator2> reverse_mismatch (std::pair < |
152 | BiDirectionalIterator1, BiDirectionalIterator1> sequence1, std::pair <BiDirectionalIterator2, |
153 | BiDirectionalIterator2> sequence2) |
154 | { |
155 | if (sequence1.first == sequence1.second || sequence2.first == sequence2.second) |
156 | return std::make_pair (sequence1.first, sequence2.first); |
157 | |
158 | BiDirectionalIterator1 iter1 = sequence1.second; |
159 | BiDirectionalIterator2 iter2 = sequence2.second; |
160 | |
161 | while (true) |
162 | { |
163 | --iter1; |
164 | --iter2; |
165 | if (*iter1 != *iter2) |
166 | { |
167 | ++iter1; |
168 | ++iter2; |
169 | break; |
170 | } |
171 | if (iter1 == sequence1.first) |
172 | break; |
173 | if (iter2 == sequence2.first) |
174 | break; |
175 | } |
176 | |
177 | return std::make_pair (iter1, iter2); |
178 | } |
179 | |
180 | } |
181 | |
182 | /** |
183 | * Checks a given graph for bipartiteness and fills the given color map with |
184 | * white and black according to the bipartition. If the graph is not |
185 | * bipartite, the contents of the color map are undefined. Runs in linear |
186 | * time in the size of the graph, if access to the property maps is in |
187 | * constant time. |
188 | * |
189 | * @param graph The given graph. |
190 | * @param index_map An index map associating vertices with an index. |
191 | * @param partition_map A color map to fill with the bipartition. |
192 | * @return true if and only if the given graph is bipartite. |
193 | */ |
194 | |
195 | template <typename Graph, typename IndexMap, typename PartitionMap> |
196 | bool is_bipartite (const Graph& graph, const IndexMap index_map, PartitionMap partition_map) |
197 | { |
198 | /// General types and variables |
199 | typedef typename property_traits <PartitionMap>::value_type partition_color_t; |
200 | typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t; |
201 | |
202 | /// Declare dfs visitor |
203 | // detail::empty_recorder recorder; |
204 | // typedef detail::bipartite_visitor <PartitionMap, detail::empty_recorder> dfs_visitor_t; |
205 | // dfs_visitor_t dfs_visitor (partition_map, recorder); |
206 | |
207 | |
208 | /// Call dfs |
209 | try |
210 | { |
211 | depth_first_search (graph, vertex_index_map (index_map).visitor (make_dfs_visitor (std::make_pair ( |
212 | detail::colorize_bipartition (partition_map), std::make_pair (detail::check_bipartition (partition_map), |
213 | put_property (partition_map, color_traits <partition_color_t>::white (), on_start_vertex ())))))); |
214 | } |
215 | catch (detail::bipartite_visitor_error <vertex_descriptor_t> error) |
216 | { |
217 | return false; |
218 | } |
219 | |
220 | return true; |
221 | } |
222 | |
223 | /** |
224 | * Checks a given graph for bipartiteness. |
225 | * |
226 | * @param graph The given graph. |
227 | * @param index_map An index map associating vertices with an index. |
228 | * @return true if and only if the given graph is bipartite. |
229 | */ |
230 | |
231 | template <typename Graph, typename IndexMap> |
232 | bool is_bipartite (const Graph& graph, const IndexMap index_map) |
233 | { |
234 | typedef one_bit_color_map <IndexMap> partition_map_t; |
235 | partition_map_t partition_map (num_vertices (graph), index_map); |
236 | |
237 | return is_bipartite (graph, index_map, partition_map); |
238 | } |
239 | |
240 | /** |
241 | * Checks a given graph for bipartiteness. The graph must |
242 | * have an internal vertex_index property. Runs in linear time in the |
243 | * size of the graph, if access to the property maps is in constant time. |
244 | * |
245 | * @param graph The given graph. |
246 | * @return true if and only if the given graph is bipartite. |
247 | */ |
248 | |
249 | template <typename Graph> |
250 | bool is_bipartite (const Graph& graph) |
251 | { |
252 | return is_bipartite (graph, get (vertex_index, graph)); |
253 | } |
254 | |
255 | /** |
256 | * Checks a given graph for bipartiteness and fills a given color map with |
257 | * white and black according to the bipartition. If the graph is not |
258 | * bipartite, a sequence of vertices, producing an odd-cycle, is written to |
259 | * the output iterator. The final iterator value is returned. Runs in linear |
260 | * time in the size of the graph, if access to the property maps is in |
261 | * constant time. |
262 | * |
263 | * @param graph The given graph. |
264 | * @param index_map An index map associating vertices with an index. |
265 | * @param partition_map A color map to fill with the bipartition. |
266 | * @param result An iterator to write the odd-cycle vertices to. |
267 | * @return The final iterator value after writing. |
268 | */ |
269 | |
270 | template <typename Graph, typename IndexMap, typename PartitionMap, typename OutputIterator> |
271 | OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, PartitionMap partition_map, |
272 | OutputIterator result) |
273 | { |
274 | /// General types and variables |
275 | typedef typename property_traits <PartitionMap>::value_type partition_color_t; |
276 | typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t; |
277 | typedef typename graph_traits <Graph>::vertex_iterator vertex_iterator_t; |
278 | vertex_iterator_t vertex_iter, vertex_end; |
279 | |
280 | /// Declare predecessor map |
281 | typedef std::vector <vertex_descriptor_t> predecessors_t; |
282 | typedef iterator_property_map <typename predecessors_t::iterator, IndexMap, vertex_descriptor_t, |
283 | vertex_descriptor_t&> predecessor_map_t; |
284 | |
285 | predecessors_t predecessors (num_vertices (graph), graph_traits <Graph>::null_vertex ()); |
286 | predecessor_map_t predecessor_map (predecessors.begin (), index_map); |
287 | |
288 | /// Initialize predecessor map |
289 | for (boost::tie (vertex_iter, vertex_end) = vertices (graph); vertex_iter != vertex_end; ++vertex_iter) |
290 | { |
291 | put (predecessor_map, *vertex_iter, *vertex_iter); |
292 | } |
293 | |
294 | /// Call dfs |
295 | try |
296 | { |
297 | depth_first_search (graph, vertex_index_map (index_map).visitor (make_dfs_visitor (std::make_pair ( |
298 | detail::colorize_bipartition (partition_map), std::make_pair (detail::check_bipartition (partition_map), |
299 | std::make_pair (put_property (partition_map, color_traits <partition_color_t>::white (), |
300 | on_start_vertex ()), record_predecessors (predecessor_map, on_tree_edge ()))))))); |
301 | } |
302 | catch (detail::bipartite_visitor_error <vertex_descriptor_t> error) |
303 | { |
304 | typedef std::vector <vertex_descriptor_t> path_t; |
305 | |
306 | path_t path1, path2; |
307 | vertex_descriptor_t next, current; |
308 | |
309 | /// First path |
310 | next = error.witnesses.first; |
311 | do |
312 | { |
313 | current = next; |
314 | path1.push_back (current); |
315 | next = predecessor_map[current]; |
316 | } |
317 | while (current != next); |
318 | |
319 | /// Second path |
320 | next = error.witnesses.second; |
321 | do |
322 | { |
323 | current = next; |
324 | path2.push_back (current); |
325 | next = predecessor_map[current]; |
326 | } |
327 | while (current != next); |
328 | |
329 | /// Find beginning of common suffix |
330 | std::pair <typename path_t::iterator, typename path_t::iterator> mismatch = detail::reverse_mismatch ( |
331 | std::make_pair (path1.begin (), path1.end ()), std::make_pair (path2.begin (), path2.end ())); |
332 | |
333 | /// Copy the odd-length cycle |
334 | result = std::copy (path1.begin (), mismatch.first + 1, result); |
335 | return std::reverse_copy (path2.begin (), mismatch.second, result); |
336 | } |
337 | |
338 | return result; |
339 | } |
340 | |
341 | /** |
342 | * Checks a given graph for bipartiteness. If the graph is not bipartite, a |
343 | * sequence of vertices, producing an odd-cycle, is written to the output |
344 | * iterator. The final iterator value is returned. Runs in linear time in the |
345 | * size of the graph, if access to the property maps is in constant time. |
346 | * |
347 | * @param graph The given graph. |
348 | * @param index_map An index map associating vertices with an index. |
349 | * @param result An iterator to write the odd-cycle vertices to. |
350 | * @return The final iterator value after writing. |
351 | */ |
352 | |
353 | template <typename Graph, typename IndexMap, typename OutputIterator> |
354 | OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, OutputIterator result) |
355 | { |
356 | typedef one_bit_color_map <IndexMap> partition_map_t; |
357 | partition_map_t partition_map (num_vertices (graph), index_map); |
358 | |
359 | return find_odd_cycle (graph, index_map, partition_map, result); |
360 | } |
361 | |
362 | /** |
363 | * Checks a given graph for bipartiteness. If the graph is not bipartite, a |
364 | * sequence of vertices, producing an odd-cycle, is written to the output |
365 | * iterator. The final iterator value is returned. The graph must have an |
366 | * internal vertex_index property. Runs in linear time in the size of the |
367 | * graph, if access to the property maps is in constant time. |
368 | * |
369 | * @param graph The given graph. |
370 | * @param result An iterator to write the odd-cycle vertices to. |
371 | * @return The final iterator value after writing. |
372 | */ |
373 | |
374 | template <typename Graph, typename OutputIterator> |
375 | OutputIterator find_odd_cycle (const Graph& graph, OutputIterator result) |
376 | { |
377 | return find_odd_cycle (graph, get (vertex_index, graph), result); |
378 | } |
379 | } |
380 | |
381 | #endif /// BOOST_GRAPH_BIPARTITE_HPP |
382 | |