123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189 |
- /**
- *
- * 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 <boost/graph/adjacency_list.hpp>
- #include <boost/graph/lookup_edge.hpp>
- #include <boost/test/minimal.hpp>
- #include <boost/graph/bipartite.hpp>
- /// 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_REQUIRE (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_CHECK ((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_REQUIRE (boost::lookup_edge (current_vertex, last_vertex, g).second);
- }
- BOOST_REQUIRE (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_REQUIRE (first_result == boost::is_bipartite(g, index_map));
- if (first_result)
- check_two_coloring (g, partition_map);
- BOOST_CHECK (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_CHECK (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_CHECK (second_beyond == second_first);
- }
- else
- {
- check_odd_cycle (g, second_first, second_beyond);
- }
- }
- int test_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_REQUIRE (is_bipartite (bipartite_vector_graph));
- BOOST_REQUIRE (!is_bipartite (non_bipartite_vector_graph));
- return 0;
- }
|