/** * * 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) * */ #include #include #include #include /// Verifies a 2-coloring template < typename Graph, typename ColorMap > void check_two_coloring(const Graph& g, const ColorMap color_map) { typedef boost::graph_traits< Graph > traits; typename traits::edge_iterator edge_iter, edge_end; for (boost::tie(edge_iter, edge_end) = boost::edges(g); edge_iter != edge_end; ++edge_iter) { typename traits::vertex_descriptor source, target; source = boost::source(*edge_iter, g); target = boost::target(*edge_iter, g); BOOST_TEST( boost::get(color_map, source) != boost::get(color_map, target)); } } /// Tests for a vertex sequence to define an odd cycle template < typename Graph, typename RandomAccessIterator > void check_odd_cycle( const Graph& g, RandomAccessIterator first, RandomAccessIterator beyond) { typedef boost::graph_traits< Graph > traits; typename traits::vertex_descriptor first_vertex, current_vertex, last_vertex; BOOST_TEST((beyond - first) % 2 == 1); // std::cout << "odd_cycle: " << int(*first) << std::endl; for (first_vertex = current_vertex = *first++; first != beyond; ++first) { // std::cout << "odd_cycle: " << int(*first) << std::endl; last_vertex = current_vertex; current_vertex = *first; BOOST_TEST( boost::lookup_edge(current_vertex, last_vertex, g).second); } BOOST_TEST(boost::lookup_edge(first_vertex, current_vertex, g).second); } /// Call the is_bipartite and find_odd_cycle functions and verify their results. template < typename Graph, typename IndexMap > void check_bipartite(const Graph& g, IndexMap index_map, bool is_bipartite) { typedef boost::graph_traits< Graph > traits; typedef std::vector< boost::default_color_type > partition_t; typedef std::vector< typename traits::vertex_descriptor > vertex_vector_t; typedef boost::iterator_property_map< partition_t::iterator, IndexMap > partition_map_t; partition_t partition(boost::num_vertices(g)); partition_map_t partition_map(partition.begin(), index_map); vertex_vector_t odd_cycle(boost::num_vertices(g)); bool first_result = boost::is_bipartite(g, index_map, partition_map); BOOST_TEST(first_result == boost::is_bipartite(g, index_map)); if (first_result) check_two_coloring(g, partition_map); BOOST_TEST(first_result == is_bipartite); typename vertex_vector_t::iterator second_first = odd_cycle.begin(); typename vertex_vector_t::iterator second_beyond = boost::find_odd_cycle(g, index_map, partition_map, second_first); if (is_bipartite) { BOOST_TEST(second_beyond == second_first); check_two_coloring(g, partition_map); } else { check_odd_cycle(g, second_first, second_beyond); } second_beyond = boost::find_odd_cycle(g, index_map, second_first); if (is_bipartite) { BOOST_TEST(second_beyond == second_first); } else { check_odd_cycle(g, second_first, second_beyond); } } int main(int argc, char** argv) { typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS > vector_graph_t; typedef boost::adjacency_list< boost::listS, boost::listS, boost::undirectedS > list_graph_t; typedef std::pair< int, int > E; typedef std::map< boost::graph_traits< list_graph_t >::vertex_descriptor, size_t > index_map_t; typedef boost::associative_property_map< index_map_t > index_property_map_t; /** * Create the graph drawn below. * * 0 - 1 - 2 * | | * 3 - 4 - 5 - 6 * / \ / * | 7 * | | * 8 - 9 - 10 **/ E bipartite_edges[] = { E(0, 1), E(0, 4), E(1, 2), E(2, 6), E(3, 4), E(3, 8), E(4, 5), E(4, 7), E(5, 6), E(6, 7), E(7, 10), E(8, 9), E(9, 10) }; vector_graph_t bipartite_vector_graph(&bipartite_edges[0], &bipartite_edges[0] + sizeof(bipartite_edges) / sizeof(E), 11); list_graph_t bipartite_list_graph(&bipartite_edges[0], &bipartite_edges[0] + sizeof(bipartite_edges) / sizeof(E), 11); /** * Create the graph drawn below. * * 2 - 1 - 0 * | | * 3 - 6 - 5 - 4 * / \ / * | 7 * | / * 8 ---- 9 * **/ E non_bipartite_edges[] = { E(0, 1), E(0, 4), E(1, 2), E(2, 6), E(3, 4), E(3, 8), E(4, 5), E(4, 7), E(5, 6), E(6, 7), E(7, 9), E(8, 9) }; vector_graph_t non_bipartite_vector_graph(&non_bipartite_edges[0], &non_bipartite_edges[0] + sizeof(non_bipartite_edges) / sizeof(E), 10); list_graph_t non_bipartite_list_graph(&non_bipartite_edges[0], &non_bipartite_edges[0] + sizeof(non_bipartite_edges) / sizeof(E), 10); /// Create index maps index_map_t bipartite_index_map, non_bipartite_index_map; boost::graph_traits< list_graph_t >::vertex_iterator vertex_iter, vertex_end; size_t i = 0; for (boost::tie(vertex_iter, vertex_end) = boost::vertices(bipartite_list_graph); vertex_iter != vertex_end; ++vertex_iter) { bipartite_index_map[*vertex_iter] = i++; } index_property_map_t bipartite_index_property_map = index_property_map_t(bipartite_index_map); i = 0; for (boost::tie(vertex_iter, vertex_end) = boost::vertices(non_bipartite_list_graph); vertex_iter != vertex_end; ++vertex_iter) { non_bipartite_index_map[*vertex_iter] = i++; } index_property_map_t non_bipartite_index_property_map = index_property_map_t(non_bipartite_index_map); /// Call real checks check_bipartite(bipartite_vector_graph, boost::get(boost::vertex_index, bipartite_vector_graph), true); check_bipartite(bipartite_list_graph, bipartite_index_property_map, true); check_bipartite(non_bipartite_vector_graph, boost::get(boost::vertex_index, non_bipartite_vector_graph), false); check_bipartite( non_bipartite_list_graph, non_bipartite_index_property_map, false); /// Test some more interfaces BOOST_TEST(is_bipartite(bipartite_vector_graph)); BOOST_TEST(!is_bipartite(non_bipartite_vector_graph)); return boost::report_errors(); }