3 * Copyright (c) 2010 Matthias Walter (xammy@xammy.homelinux.net)
5 * Authors: Matthias Walter
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)
13 #ifndef BOOST_GRAPH_BIPARTITE_HPP
14 #define BOOST_GRAPH_BIPARTITE_HPP
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>
30 * The bipartite_visitor_error is thrown if an edge cannot be colored.
31 * The witnesses are the edges incident vertices.
34 template <typename Vertex>
35 struct bipartite_visitor_error: std::exception
37 std::pair <Vertex, Vertex> witnesses;
39 bipartite_visitor_error (Vertex a, Vertex b) :
45 const char* what () const throw ()
47 return "Graph is not bipartite.";
52 * Functor which colors edges to be non-monochromatic.
55 template <typename PartitionMap>
56 struct bipartition_colorize
58 typedef on_tree_edge event_filter;
60 bipartition_colorize (PartitionMap partition_map) :
61 partition_map_ (partition_map)
66 template <typename Edge, typename Graph>
67 void operator() (Edge e, const Graph& g)
69 typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t;
70 typedef color_traits <typename property_traits <PartitionMap>::value_type> color_traits;
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 ());
77 put (partition_map_, target_vertex, color_traits::white ());
81 PartitionMap partition_map_;
85 * Creates a bipartition_colorize functor which colors edges
86 * to be non-monochromatic.
88 * @param partition_map Color map for the bipartition
89 * @return The functor.
92 template <typename PartitionMap>
93 inline bipartition_colorize <PartitionMap> colorize_bipartition (PartitionMap partition_map)
95 return bipartition_colorize <PartitionMap> (partition_map);
99 * Functor which tests an edge to be monochromatic.
102 template <typename PartitionMap>
103 struct bipartition_check
105 typedef on_back_edge event_filter;
107 bipartition_check (PartitionMap partition_map) :
108 partition_map_ (partition_map)
113 template <typename Edge, typename Graph>
114 void operator() (Edge e, const Graph& g)
116 typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t;
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);
125 PartitionMap partition_map_;
129 * Creates a bipartition_check functor which raises an error if a
130 * monochromatic edge is found.
132 * @param partition_map The map for a bipartition.
133 * @return The functor.
136 template <typename PartitionMap>
137 inline bipartition_check <PartitionMap> check_bipartition (PartitionMap partition_map)
139 return bipartition_check <PartitionMap> (partition_map);
143 * Find the beginning of a common suffix of two sequences
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.
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)
155 if (sequence1.first == sequence1.second || sequence2.first == sequence2.second)
156 return std::make_pair (sequence1.first, sequence2.first);
158 BiDirectionalIterator1 iter1 = sequence1.second;
159 BiDirectionalIterator2 iter2 = sequence2.second;
165 if (*iter1 != *iter2)
171 if (iter1 == sequence1.first)
173 if (iter2 == sequence2.first)
177 return std::make_pair (iter1, iter2);
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
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.
195 template <typename Graph, typename IndexMap, typename PartitionMap>
196 bool is_bipartite (const Graph& graph, const IndexMap index_map, PartitionMap partition_map)
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;
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);
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 ()))))));
215 catch (detail::bipartite_visitor_error <vertex_descriptor_t> error)
224 * Checks a given graph for bipartiteness.
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.
231 template <typename Graph, typename IndexMap>
232 bool is_bipartite (const Graph& graph, const IndexMap index_map)
234 typedef one_bit_color_map <IndexMap> partition_map_t;
235 partition_map_t partition_map (num_vertices (graph), index_map);
237 return is_bipartite (graph, index_map, partition_map);
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.
245 * @param graph The given graph.
246 * @return true if and only if the given graph is bipartite.
249 template <typename Graph>
250 bool is_bipartite (const Graph& graph)
252 return is_bipartite (graph, get (vertex_index, graph));
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
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.
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)
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;
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;
285 predecessors_t predecessors (num_vertices (graph), graph_traits <Graph>::null_vertex ());
286 predecessor_map_t predecessor_map (predecessors.begin (), index_map);
288 /// Initialize predecessor map
289 for (boost::tie (vertex_iter, vertex_end) = vertices (graph); vertex_iter != vertex_end; ++vertex_iter)
291 put (predecessor_map, *vertex_iter, *vertex_iter);
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 ())))))));
302 catch (detail::bipartite_visitor_error <vertex_descriptor_t> error)
304 typedef std::vector <vertex_descriptor_t> path_t;
307 vertex_descriptor_t next, current;
310 next = error.witnesses.first;
314 path1.push_back (current);
315 next = predecessor_map[current];
317 while (current != next);
320 next = error.witnesses.second;
324 path2.push_back (current);
325 next = predecessor_map[current];
327 while (current != next);
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 ()));
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);
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.
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.
353 template <typename Graph, typename IndexMap, typename OutputIterator>
354 OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, OutputIterator result)
356 typedef one_bit_color_map <IndexMap> partition_map_t;
357 partition_map_t partition_map (num_vertices (graph), index_map);
359 return find_odd_cycle (graph, index_map, partition_map, result);
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.
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.
374 template <typename Graph, typename OutputIterator>
375 OutputIterator find_odd_cycle (const Graph& graph, OutputIterator result)
377 return find_odd_cycle (graph, get (vertex_index, graph), result);
381 #endif /// BOOST_GRAPH_BIPARTITE_HPP