| /** |
| * |
| * Copyright (c) 2010 Matthias Walter (xammy@xammy.homelinux.net) |
| * |
| * Authors: Matthias Walter |
| * |
| * Distributed under the Boost Software License, Version 1.0. (See |
| * accompanying file LICENSE_1_0.txt or copy at |
| * http://www.boost.org/LICENSE_1_0.txt) |
| * |
| */ |
| |
| #ifndef BOOST_GRAPH_BIPARTITE_HPP |
| #define BOOST_GRAPH_BIPARTITE_HPP |
| |
| #include <utility> |
| #include <vector> |
| #include <exception> |
| #include <boost/graph/properties.hpp> |
| #include <boost/graph/adjacency_list.hpp> |
| #include <boost/graph/depth_first_search.hpp> |
| #include <boost/graph/one_bit_color_map.hpp> |
| #include <boost/bind.hpp> |
| |
| namespace boost { |
| |
| namespace detail { |
| |
| /** |
| * The bipartite_visitor_error is thrown if an edge cannot be colored. |
| * The witnesses are the edges incident vertices. |
| */ |
| |
| template <typename Vertex> |
| struct bipartite_visitor_error: std::exception |
| { |
| std::pair <Vertex, Vertex> witnesses; |
| |
| bipartite_visitor_error (Vertex a, Vertex b) : |
| witnesses (a, b) |
| { |
| |
| } |
| |
| const char* what () const throw () |
| { |
| return "Graph is not bipartite."; |
| } |
| }; |
| |
| /** |
| * Functor which colors edges to be non-monochromatic. |
| */ |
| |
| template <typename PartitionMap> |
| struct bipartition_colorize |
| { |
| typedef on_tree_edge event_filter; |
| |
| bipartition_colorize (PartitionMap partition_map) : |
| partition_map_ (partition_map) |
| { |
| |
| } |
| |
| template <typename Edge, typename Graph> |
| void operator() (Edge e, const Graph& g) |
| { |
| typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t; |
| typedef color_traits <typename property_traits <PartitionMap>::value_type> color_traits; |
| |
| vertex_descriptor_t source_vertex = source (e, g); |
| vertex_descriptor_t target_vertex = target (e, g); |
| if (get (partition_map_, source_vertex) == color_traits::white ()) |
| put (partition_map_, target_vertex, color_traits::black ()); |
| else |
| put (partition_map_, target_vertex, color_traits::white ()); |
| } |
| |
| private: |
| PartitionMap partition_map_; |
| }; |
| |
| /** |
| * Creates a bipartition_colorize functor which colors edges |
| * to be non-monochromatic. |
| * |
| * @param partition_map Color map for the bipartition |
| * @return The functor. |
| */ |
| |
| template <typename PartitionMap> |
| inline bipartition_colorize <PartitionMap> colorize_bipartition (PartitionMap partition_map) |
| { |
| return bipartition_colorize <PartitionMap> (partition_map); |
| } |
| |
| /** |
| * Functor which tests an edge to be monochromatic. |
| */ |
| |
| template <typename PartitionMap> |
| struct bipartition_check |
| { |
| typedef on_back_edge event_filter; |
| |
| bipartition_check (PartitionMap partition_map) : |
| partition_map_ (partition_map) |
| { |
| |
| } |
| |
| template <typename Edge, typename Graph> |
| void operator() (Edge e, const Graph& g) |
| { |
| typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t; |
| |
| vertex_descriptor_t source_vertex = source (e, g); |
| vertex_descriptor_t target_vertex = target (e, g); |
| if (get (partition_map_, source_vertex) == get (partition_map_, target_vertex)) |
| throw bipartite_visitor_error <vertex_descriptor_t> (source_vertex, target_vertex); |
| } |
| |
| private: |
| PartitionMap partition_map_; |
| }; |
| |
| /** |
| * Creates a bipartition_check functor which raises an error if a |
| * monochromatic edge is found. |
| * |
| * @param partition_map The map for a bipartition. |
| * @return The functor. |
| */ |
| |
| template <typename PartitionMap> |
| inline bipartition_check <PartitionMap> check_bipartition (PartitionMap partition_map) |
| { |
| return bipartition_check <PartitionMap> (partition_map); |
| } |
| |
| /** |
| * Find the beginning of a common suffix of two sequences |
| * |
| * @param sequence1 Pair of bidirectional iterators defining the first sequence. |
| * @param sequence2 Pair of bidirectional iterators defining the second sequence. |
| * @return Pair of iterators pointing to the beginning of the common suffix. |
| */ |
| |
| template <typename BiDirectionalIterator1, typename BiDirectionalIterator2> |
| inline std::pair <BiDirectionalIterator1, BiDirectionalIterator2> reverse_mismatch (std::pair < |
| BiDirectionalIterator1, BiDirectionalIterator1> sequence1, std::pair <BiDirectionalIterator2, |
| BiDirectionalIterator2> sequence2) |
| { |
| if (sequence1.first == sequence1.second || sequence2.first == sequence2.second) |
| return std::make_pair (sequence1.first, sequence2.first); |
| |
| BiDirectionalIterator1 iter1 = sequence1.second; |
| BiDirectionalIterator2 iter2 = sequence2.second; |
| |
| while (true) |
| { |
| --iter1; |
| --iter2; |
| if (*iter1 != *iter2) |
| { |
| ++iter1; |
| ++iter2; |
| break; |
| } |
| if (iter1 == sequence1.first) |
| break; |
| if (iter2 == sequence2.first) |
| break; |
| } |
| |
| return std::make_pair (iter1, iter2); |
| } |
| |
| } |
| |
| /** |
| * Checks a given graph for bipartiteness and fills the given color map with |
| * white and black according to the bipartition. If the graph is not |
| * bipartite, the contents of the color map are undefined. Runs in linear |
| * time in the size of the graph, if access to the property maps is in |
| * constant time. |
| * |
| * @param graph The given graph. |
| * @param index_map An index map associating vertices with an index. |
| * @param partition_map A color map to fill with the bipartition. |
| * @return true if and only if the given graph is bipartite. |
| */ |
| |
| template <typename Graph, typename IndexMap, typename PartitionMap> |
| bool is_bipartite (const Graph& graph, const IndexMap index_map, PartitionMap partition_map) |
| { |
| /// General types and variables |
| typedef typename property_traits <PartitionMap>::value_type partition_color_t; |
| typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t; |
| typedef typename graph_traits <Graph>::vertex_iterator vertex_iterator_t; |
| |
| /// Declare dfs visitor |
| // detail::empty_recorder recorder; |
| // typedef detail::bipartite_visitor <PartitionMap, detail::empty_recorder> dfs_visitor_t; |
| // dfs_visitor_t dfs_visitor (partition_map, recorder); |
| |
| |
| /// Call dfs |
| try |
| { |
| depth_first_search (graph, vertex_index_map (index_map).visitor (make_dfs_visitor (std::make_pair ( |
| detail::colorize_bipartition (partition_map), std::make_pair (detail::check_bipartition (partition_map), |
| put_property (partition_map, color_traits <partition_color_t>::white (), on_start_vertex ())))))); |
| |
| // depth_first_search (graph, vertex_index_map (index_map).visitor (dfs_visitor)); |
| } |
| catch (detail::bipartite_visitor_error <vertex_descriptor_t> error) |
| { |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /** |
| * Checks a given graph for bipartiteness. |
| * |
| * @param graph The given graph. |
| * @param index_map An index map associating vertices with an index. |
| * @return true if and only if the given graph is bipartite. |
| */ |
| |
| template <typename Graph, typename IndexMap> |
| bool is_bipartite (const Graph& graph, const IndexMap index_map) |
| { |
| typedef one_bit_color_map <IndexMap> partition_map_t; |
| partition_map_t partition_map (num_vertices (graph), index_map); |
| |
| return is_bipartite (graph, index_map, partition_map); |
| } |
| |
| /** |
| * Checks a given graph for bipartiteness. The graph must |
| * have an internal vertex_index property. Runs in linear time in the |
| * size of the graph, if access to the property maps is in constant time. |
| * |
| * @param graph The given graph. |
| * @return true if and only if the given graph is bipartite. |
| */ |
| |
| template <typename Graph> |
| bool is_bipartite (const Graph& graph) |
| { |
| return is_bipartite (graph, get (vertex_index, graph)); |
| } |
| |
| /** |
| * Checks a given graph for bipartiteness and fills a given color map with |
| * white and black according to the bipartition. If the graph is not |
| * bipartite, a sequence of vertices, producing an odd-cycle, is written to |
| * the output iterator. The final iterator value is returned. Runs in linear |
| * time in the size of the graph, if access to the property maps is in |
| * constant time. |
| * |
| * @param graph The given graph. |
| * @param index_map An index map associating vertices with an index. |
| * @param partition_map A color map to fill with the bipartition. |
| * @param result An iterator to write the odd-cycle vertices to. |
| * @return The final iterator value after writing. |
| */ |
| |
| template <typename Graph, typename IndexMap, typename PartitionMap, typename OutputIterator> |
| OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, PartitionMap partition_map, |
| OutputIterator result) |
| { |
| /// General types and variables |
| typedef typename property_traits <PartitionMap>::value_type partition_color_t; |
| typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t; |
| typedef typename graph_traits <Graph>::vertex_iterator vertex_iterator_t; |
| vertex_iterator_t vertex_iter, vertex_end; |
| |
| /// Declare predecessor map |
| typedef std::vector <vertex_descriptor_t> predecessors_t; |
| typedef iterator_property_map <typename predecessors_t::iterator, IndexMap, vertex_descriptor_t, |
| vertex_descriptor_t&> predecessor_map_t; |
| typedef predecessor_recorder <predecessor_map_t, IndexMap> predecessor_recorder_t; |
| |
| predecessors_t predecessors (num_vertices (graph), graph_traits <Graph>::null_vertex ()); |
| predecessor_map_t predecessor_map (predecessors.begin (), index_map); |
| predecessor_recorder_t predecessor_recorder (predecessor_map); |
| |
| /// Initialize predecessor map |
| for (boost::tie (vertex_iter, vertex_end) = vertices (graph); vertex_iter != vertex_end; ++vertex_iter) |
| { |
| put (predecessor_map, *vertex_iter, *vertex_iter); |
| } |
| |
| /// Call dfs |
| try |
| { |
| depth_first_search (graph, vertex_index_map (index_map).visitor (make_dfs_visitor (std::make_pair ( |
| detail::colorize_bipartition (partition_map), std::make_pair (detail::check_bipartition (partition_map), |
| std::make_pair (put_property (partition_map, color_traits <partition_color_t>::white (), |
| on_start_vertex ()), record_predecessors (predecessor_map, on_tree_edge ()))))))); |
| } |
| catch (detail::bipartite_visitor_error <vertex_descriptor_t> error) |
| { |
| typedef std::vector <vertex_descriptor_t> path_t; |
| |
| path_t path1, path2; |
| vertex_descriptor_t next, current; |
| |
| /// First path |
| next = error.witnesses.first; |
| do |
| { |
| current = next; |
| path1.push_back (current); |
| next = predecessor_map[current]; |
| } |
| while (current != next); |
| |
| /// Second path |
| next = error.witnesses.second; |
| do |
| { |
| current = next; |
| path2.push_back (current); |
| next = predecessor_map[current]; |
| } |
| while (current != next); |
| |
| /// Find beginning of common suffix |
| std::pair <typename path_t::iterator, typename path_t::iterator> mismatch = detail::reverse_mismatch ( |
| std::make_pair (path1.begin (), path1.end ()), std::make_pair (path2.begin (), path2.end ())); |
| |
| /// Copy the odd-length cycle |
| result = std::copy (path1.begin (), mismatch.first + 1, result); |
| return std::reverse_copy (path2.begin (), mismatch.second, result); |
| } |
| |
| return result; |
| } |
| |
| /** |
| * Checks a given graph for bipartiteness. If the graph is not bipartite, a |
| * sequence of vertices, producing an odd-cycle, is written to the output |
| * iterator. The final iterator value is returned. Runs in linear time in the |
| * size of the graph, if access to the property maps is in constant time. |
| * |
| * @param graph The given graph. |
| * @param index_map An index map associating vertices with an index. |
| * @param result An iterator to write the odd-cycle vertices to. |
| * @return The final iterator value after writing. |
| */ |
| |
| template <typename Graph, typename IndexMap, typename OutputIterator> |
| OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, OutputIterator result) |
| { |
| typedef one_bit_color_map <IndexMap> partition_map_t; |
| partition_map_t partition_map (num_vertices (graph), index_map); |
| |
| return find_odd_cycle (graph, index_map, partition_map, result); |
| } |
| |
| /** |
| * Checks a given graph for bipartiteness. If the graph is not bipartite, a |
| * sequence of vertices, producing an odd-cycle, is written to the output |
| * iterator. The final iterator value is returned. The graph must have an |
| * internal vertex_index property. Runs in linear time in the size of the |
| * graph, if access to the property maps is in constant time. |
| * |
| * @param graph The given graph. |
| * @param result An iterator to write the odd-cycle vertices to. |
| * @return The final iterator value after writing. |
| */ |
| |
| template <typename Graph, typename OutputIterator> |
| OutputIterator find_odd_cycle (const Graph& graph, OutputIterator result) |
| { |
| return find_odd_cycle (graph, get (vertex_index, graph), result); |
| } |
| } |
| |
| #endif /// BOOST_GRAPH_BIPARTITE_HPP |