123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403 |
- #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>
- namespace boost
- {
- namespace detail
- {
-
- template < typename Vertex >
- struct BOOST_SYMBOL_VISIBLE 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."; }
- };
-
- 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_;
- };
-
- template < typename PartitionMap >
- inline bipartition_colorize< PartitionMap > colorize_bipartition(
- PartitionMap partition_map)
- {
- return bipartition_colorize< PartitionMap >(partition_map);
- }
-
- 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_;
- };
-
- template < typename PartitionMap >
- inline bipartition_check< PartitionMap > check_bipartition(
- PartitionMap partition_map)
- {
- return bipartition_check< PartitionMap >(partition_map);
- }
-
- 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);
- }
- }
- template < typename Graph, typename IndexMap, typename PartitionMap >
- bool is_bipartite(
- const Graph& graph, const IndexMap index_map, PartitionMap partition_map)
- {
-
- typedef
- typename property_traits< PartitionMap >::value_type partition_color_t;
- typedef
- typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t;
-
-
-
-
-
-
- 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()))))));
- }
- catch (const detail::bipartite_visitor_error< vertex_descriptor_t >&)
- {
- return false;
- }
- return true;
- }
- 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);
- }
- template < typename Graph > bool is_bipartite(const Graph& graph)
- {
- return is_bipartite(graph, get(vertex_index, graph));
- }
- 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)
- {
-
- 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;
-
- 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;
- predecessors_t predecessors(
- num_vertices(graph), graph_traits< Graph >::null_vertex());
- predecessor_map_t predecessor_map(predecessors.begin(), index_map);
-
- for (boost::tie(vertex_iter, vertex_end) = vertices(graph);
- vertex_iter != vertex_end; ++vertex_iter)
- {
- put(predecessor_map, *vertex_iter, *vertex_iter);
- }
-
- 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 (const 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;
-
- next = error.witnesses.first;
- do
- {
- current = next;
- path1.push_back(current);
- next = predecessor_map[current];
- } while (current != next);
-
- next = error.witnesses.second;
- do
- {
- current = next;
- path2.push_back(current);
- next = predecessor_map[current];
- } while (current != next);
-
- 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()));
-
- result = std::copy(path1.begin(), mismatch.first + 1, result);
- return std::reverse_copy(path2.begin(), mismatch.second, result);
- }
- return result;
- }
- 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);
- }
- 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
|