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
25namespace 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

source code of boost/boost/graph/bipartite.hpp