boost/graph/bipartite.hpp

0001 /**
0002  *
0003  * Copyright (c) 2010 Matthias Walter (xammy@xammy.homelinux.net)
0004  *
0005  * Authors: Matthias Walter
0006  *
0007  * Distributed under the Boost Software License, Version 1.0. (See
0008  * accompanying file LICENSE_1_0.txt or copy at
0009  * http://www.boost.org/LICENSE_1_0.txt)
0010  *
0011  */
0012
0013 #ifndef BOOST_GRAPH_BIPARTITE_HPP
0014 #define BOOST_GRAPH_BIPARTITE_HPP
0015
0016 #include <utility>
0017 #include <vector>
0018 #include <exception>
0019 #include <boost/graph/properties.hpp>
0020 #include <boost/graph/adjacency_list.hpp>
0021 #include <boost/graph/depth_first_search.hpp>
0022 #include <boost/graph/one_bit_color_map.hpp>
0023
0024 namespace boost
0025 {
0026
0027 namespace detail
0028 {
0029
0030     /**
0031      * The bipartite_visitor_error is thrown if an edge cannot be colored.
0032      * The witnesses are the edges incident vertices.
0033      */
0034
0035     template < typename Vertex >
0036     struct BOOST_SYMBOL_VISIBLE bipartite_visitor_error : std::exception
0037     {
0038         std::pair< Vertex, Vertex > witnesses;
0039
0040         bipartite_visitor_error(Vertex a, Vertex b) : witnesses(a, b) {}
0041
0042         const char* what() const throw() { return "Graph is not bipartite."; }
0043     };
0044
0045     /**
0046      * Functor which colors edges to be non-monochromatic.
0047      */
0048
0049     template < typename PartitionMap > struct bipartition_colorize
0050     {
0051         typedef on_tree_edge event_filter;
0052
0053         bipartition_colorize(PartitionMap partition_map)
0054         : partition_map_(partition_map)
0055         {
0056         }
0057
0058         template < typename Edge, typename Graph >
0059         void operator()(Edge e, const Graph& g)
0060         {
0061             typedef typename graph_traits< Graph >::vertex_descriptor
0062                 vertex_descriptor_t;
0063             typedef color_traits<
0064                 typename property_traits< PartitionMap >::value_type >
0065                 color_traits;
0066
0067             vertex_descriptor_t source_vertex = source(e, g);
0068             vertex_descriptor_t target_vertex = target(e, g);
0069             if (get(partition_map_, source_vertex) == color_traits::white())
0070                 put(partition_map_, target_vertex, color_traits::black());
0071             else
0072                 put(partition_map_, target_vertex, color_traits::white());
0073         }
0074
0075     private:
0076         PartitionMap partition_map_;
0077     };
0078
0079     /**
0080      * Creates a bipartition_colorize functor which colors edges
0081      * to be non-monochromatic.
0082      *
0083      * @param partition_map Color map for the bipartition
0084      * @return The functor.
0085      */
0086
0087     template < typename PartitionMap >
0088     inline bipartition_colorize< PartitionMap > colorize_bipartition(
0089         PartitionMap partition_map)
0090     {
0091         return bipartition_colorize< PartitionMap >(partition_map);
0092     }
0093
0094     /**
0095      * Functor which tests an edge to be monochromatic.
0096      */
0097
0098     template < typename PartitionMap > struct bipartition_check
0099     {
0100         typedef on_back_edge event_filter;
0101
0102         bipartition_check(PartitionMap partition_map)
0103         : partition_map_(partition_map)
0104         {
0105         }
0106
0107         template < typename Edge, typename Graph >
0108         void operator()(Edge e, const Graph& g)
0109         {
0110             typedef typename graph_traits< Graph >::vertex_descriptor
0111                 vertex_descriptor_t;
0112
0113             vertex_descriptor_t source_vertex = source(e, g);
0114             vertex_descriptor_t target_vertex = target(e, g);
0115             if (get(partition_map_, source_vertex)
0116                 == get(partition_map_, target_vertex))
0117                 throw bipartite_visitor_error< vertex_descriptor_t >(
0118                     source_vertex, target_vertex);
0119         }
0120
0121     private:
0122         PartitionMap partition_map_;
0123     };
0124
0125     /**
0126      * Creates a bipartition_check functor which raises an error if a
0127      * monochromatic edge is found.
0128      *
0129      * @param partition_map The map for a bipartition.
0130      * @return The functor.
0131      */
0132
0133     template < typename PartitionMap >
0134     inline bipartition_check< PartitionMap > check_bipartition(
0135         PartitionMap partition_map)
0136     {
0137         return bipartition_check< PartitionMap >(partition_map);
0138     }
0139
0140     /**
0141      * Find the beginning of a common suffix of two sequences
0142      *
0143      * @param sequence1 Pair of bidirectional iterators defining the first
0144      * sequence.
0145      * @param sequence2 Pair of bidirectional iterators defining the second
0146      * sequence.
0147      * @return Pair of iterators pointing to the beginning of the common suffix.
0148      */
0149
0150     template < typename BiDirectionalIterator1,
0151         typename BiDirectionalIterator2 >
0152     inline std::pair< BiDirectionalIterator1, BiDirectionalIterator2 >
0153     reverse_mismatch(
0154         std::pair< BiDirectionalIterator1, BiDirectionalIterator1 > sequence1,
0155         std::pair< BiDirectionalIterator2, BiDirectionalIterator2 > sequence2)
0156     {
0157         if (sequence1.first == sequence1.second
0158             || sequence2.first == sequence2.second)
0159             return std::make_pair(sequence1.first, sequence2.first);
0160
0161         BiDirectionalIterator1 iter1 = sequence1.second;
0162         BiDirectionalIterator2 iter2 = sequence2.second;
0163
0164         while (true)
0165         {
0166             --iter1;
0167             --iter2;
0168             if (*iter1 != *iter2)
0169             {
0170                 ++iter1;
0171                 ++iter2;
0172                 break;
0173             }
0174             if (iter1 == sequence1.first)
0175                 break;
0176             if (iter2 == sequence2.first)
0177                 break;
0178         }
0179
0180         return std::make_pair(iter1, iter2);
0181     }
0182
0183 }
0184
0185 /**
0186  * Checks a given graph for bipartiteness and fills the given color map with
0187  * white and black according to the bipartition. If the graph is not
0188  * bipartite, the contents of the color map are undefined. Runs in linear
0189  * time in the size of the graph, if access to the property maps is in
0190  * constant time.
0191  *
0192  * @param graph The given graph.
0193  * @param index_map An index map associating vertices with an index.
0194  * @param partition_map A color map to fill with the bipartition.
0195  * @return true if and only if the given graph is bipartite.
0196  */
0197
0198 template < typename Graph, typename IndexMap, typename PartitionMap >
0199 bool is_bipartite(
0200     const Graph& graph, const IndexMap index_map, PartitionMap partition_map)
0201 {
0202     /// General types and variables
0203     typedef
0204         typename property_traits< PartitionMap >::value_type partition_color_t;
0205     typedef
0206         typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t;
0207
0208     /// Declare dfs visitor
0209     //    detail::empty_recorder recorder;
0210     //    typedef detail::bipartite_visitor <PartitionMap,
0211     //    detail::empty_recorder> dfs_visitor_t; dfs_visitor_t dfs_visitor
0212     //    (partition_map, recorder);
0213
0214     /// Call dfs
0215     try
0216     {
0217         depth_first_search(graph,
0218             vertex_index_map(index_map).visitor(make_dfs_visitor(
0219                 std::make_pair(detail::colorize_bipartition(partition_map),
0220                     std::make_pair(detail::check_bipartition(partition_map),
0221                         put_property(partition_map,
0222                             color_traits< partition_color_t >::white(),
0223                             on_start_vertex()))))));
0224     }
0225     catch (const detail::bipartite_visitor_error< vertex_descriptor_t >&)
0226     {
0227         return false;
0228     }
0229
0230     return true;
0231 }
0232
0233 /**
0234  * Checks a given graph for bipartiteness.
0235  *
0236  * @param graph The given graph.
0237  * @param index_map An index map associating vertices with an index.
0238  * @return true if and only if the given graph is bipartite.
0239  */
0240
0241 template < typename Graph, typename IndexMap >
0242 bool is_bipartite(const Graph& graph, const IndexMap index_map)
0243 {
0244     typedef one_bit_color_map< IndexMap > partition_map_t;
0245     partition_map_t partition_map(num_vertices(graph), index_map);
0246
0247     return is_bipartite(graph, index_map, partition_map);
0248 }
0249
0250 /**
0251  * Checks a given graph for bipartiteness. The graph must
0252  * have an internal vertex_index property. Runs in linear time in the
0253  * size of the graph, if access to the property maps is in constant time.
0254  *
0255  * @param graph The given graph.
0256  * @return true if and only if the given graph is bipartite.
0257  */
0258
0259 template < typename Graph > bool is_bipartite(const Graph& graph)
0260 {
0261     return is_bipartite(graph, get(vertex_index, graph));
0262 }
0263
0264 /**
0265  * Checks a given graph for bipartiteness and fills a given color map with
0266  * white and black according to the bipartition. If the graph is not
0267  * bipartite, a sequence of vertices, producing an odd-cycle, is written to
0268  * the output iterator. The final iterator value is returned. Runs in linear
0269  * time in the size of the graph, if access to the property maps is in
0270  * constant time.
0271  *
0272  * @param graph The given graph.
0273  * @param index_map An index map associating vertices with an index.
0274  * @param partition_map A color map to fill with the bipartition.
0275  * @param result An iterator to write the odd-cycle vertices to.
0276  * @return The final iterator value after writing.
0277  */
0278
0279 template < typename Graph, typename IndexMap, typename PartitionMap,
0280     typename OutputIterator >
0281 OutputIterator find_odd_cycle(const Graph& graph, const IndexMap index_map,
0282     PartitionMap partition_map, OutputIterator result)
0283 {
0284     /// General types and variables
0285     typedef
0286         typename property_traits< PartitionMap >::value_type partition_color_t;
0287     typedef
0288         typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t;
0289     typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
0290     vertex_iterator_t vertex_iter, vertex_end;
0291
0292     /// Declare predecessor map
0293     typedef std::vector< vertex_descriptor_t > predecessors_t;
0294     typedef iterator_property_map< typename predecessors_t::iterator, IndexMap,
0295         vertex_descriptor_t, vertex_descriptor_t& >
0296         predecessor_map_t;
0297
0298     predecessors_t predecessors(
0299         num_vertices(graph), graph_traits< Graph >::null_vertex());
0300     predecessor_map_t predecessor_map(predecessors.begin(), index_map);
0301
0302     /// Initialize predecessor map
0303     for (boost::tie(vertex_iter, vertex_end) = vertices(graph);
0304          vertex_iter != vertex_end; ++vertex_iter)
0305     {
0306         put(predecessor_map, *vertex_iter, *vertex_iter);
0307     }
0308
0309     /// Call dfs
0310     try
0311     {
0312         depth_first_search(graph,
0313             vertex_index_map(index_map).visitor(make_dfs_visitor(
0314                 std::make_pair(detail::colorize_bipartition(partition_map),
0315                     std::make_pair(detail::check_bipartition(partition_map),
0316                         std::make_pair(
0317                             put_property(partition_map,
0318                                 color_traits< partition_color_t >::white(),
0319                                 on_start_vertex()),
0320                             record_predecessors(
0321                                 predecessor_map, on_tree_edge())))))));
0322     }
0323     catch (const detail::bipartite_visitor_error< vertex_descriptor_t >& error)
0324     {
0325         typedef std::vector< vertex_descriptor_t > path_t;
0326
0327         path_t path1, path2;
0328         vertex_descriptor_t next, current;
0329
0330         /// First path
0331         next = error.witnesses.first;
0332         do
0333         {
0334             current = next;
0335             path1.push_back(current);
0336             next = predecessor_map[current];
0337         } while (current != next);
0338
0339         /// Second path
0340         next = error.witnesses.second;
0341         do
0342         {
0343             current = next;
0344             path2.push_back(current);
0345             next = predecessor_map[current];
0346         } while (current != next);
0347
0348         /// Find beginning of common suffix
0349         std::pair< typename path_t::iterator, typename path_t::iterator >
0350             mismatch = detail::reverse_mismatch(
0351                 std::make_pair(path1.begin(), path1.end()),
0352                 std::make_pair(path2.begin(), path2.end()));
0353
0354         /// Copy the odd-length cycle
0355         result = std::copy(path1.begin(), mismatch.first + 1, result);
0356         return std::reverse_copy(path2.begin(), mismatch.second, result);
0357     }
0358
0359     return result;
0360 }
0361
0362 /**
0363  * Checks a given graph for bipartiteness. If the graph is not bipartite, a
0364  * sequence of vertices, producing an odd-cycle, is written to the output
0365  * iterator. The final iterator value is returned. Runs in linear time in the
0366  * size of the graph, if access to the property maps is in constant time.
0367  *
0368  * @param graph The given graph.
0369  * @param index_map An index map associating vertices with an index.
0370  * @param result An iterator to write the odd-cycle vertices to.
0371  * @return The final iterator value after writing.
0372  */
0373
0374 template < typename Graph, typename IndexMap, typename OutputIterator >
0375 OutputIterator find_odd_cycle(
0376     const Graph& graph, const IndexMap index_map, OutputIterator result)
0377 {
0378     typedef one_bit_color_map< IndexMap > partition_map_t;
0379     partition_map_t partition_map(num_vertices(graph), index_map);
0380
0381     return find_odd_cycle(graph, index_map, partition_map, result);
0382 }
0383
0384 /**
0385  * Checks a given graph for bipartiteness. If the graph is not bipartite, a
0386  * sequence of vertices, producing an odd-cycle, is written to the output
0387  * iterator. The final iterator value is returned. The graph must have an
0388  * internal vertex_index property. Runs in linear time in the size of the
0389  * graph, if access to the property maps is in constant time.
0390  *
0391  * @param graph The given graph.
0392  * @param result An iterator to write the odd-cycle vertices to.
0393  * @return The final iterator value after writing.
0394  */
0395
0396 template < typename Graph, typename OutputIterator >
0397 OutputIterator find_odd_cycle(const Graph& graph, OutputIterator result)
0398 {
0399     return find_odd_cycle(graph, get(vertex_index, graph), result);
0400 }
0401 }
0402
0403 #endif /// BOOST_GRAPH_BIPARTITE_HPP