9
3

bipartite.hpp 13 KB

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