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 bipartite_visitor_errorboost::detail::bipartite_visitor_error39 bipartite_visitor_error (Vertex a, Vertex b) : 40 witnesses (a, b) 41 { 42 43 } 44 whatboost::detail::bipartite_visitor_error45 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 bipartition_colorizeboost::detail::bipartition_colorize60 bipartition_colorize (PartitionMap partition_map) : 61 partition_map_ (partition_map) 62 { 63 64 } 65 66 template <typename Edge, typename Graph> operator ()boost::detail::bipartition_colorize67 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> colorize_bipartition(PartitionMap partition_map)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 bipartition_checkboost::detail::bipartition_check107 bipartition_check (PartitionMap partition_map) : 108 partition_map_ (partition_map) 109 { 110 111 } 112 113 template <typename Edge, typename Graph> operator ()boost::detail::bipartition_check114 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> check_bipartition(PartitionMap partition_map)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> reverse_mismatch(std::pair<BiDirectionalIterator1,BiDirectionalIterator1> sequence1,std::pair<BiDirectionalIterator2,BiDirectionalIterator2> sequence2)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> is_bipartite(const Graph & graph,const IndexMap index_map,PartitionMap partition_map)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> is_bipartite(const Graph & graph,const IndexMap index_map)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> is_bipartite(const Graph & 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> find_odd_cycle(const Graph & graph,const IndexMap index_map,PartitionMap partition_map,OutputIterator result)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> find_odd_cycle(const Graph & graph,const IndexMap index_map,OutputIterator result)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> find_odd_cycle(const Graph & graph,OutputIterator result)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