#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/lookup_edge.hpp>
-#include <boost/test/minimal.hpp>
+#include <boost/core/lightweight_test.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)
+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));
- }
+ 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)
+template < typename Graph, typename RandomAccessIterator >
+void check_odd_cycle(
+ const Graph& g, RandomAccessIterator first, RandomAccessIterator beyond)
{
- typedef boost::graph_traits <Graph> traits;
+ typedef boost::graph_traits< Graph > traits;
- typename traits::vertex_descriptor first_vertex, current_vertex, last_vertex;
+ typename traits::vertex_descriptor first_vertex, current_vertex,
+ last_vertex;
- BOOST_CHECK ((beyond - first) % 2 == 1);
+ BOOST_TEST((beyond - first) % 2 == 1);
- // std::cout << "odd_cycle: " << int(*first) << std::endl;
+ // 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;
+ for (first_vertex = current_vertex = *first++; first != beyond; ++first)
+ {
+ // std::cout << "odd_cycle: " << int(*first) << std::endl;
- last_vertex = current_vertex;
- current_vertex = *first;
+ last_vertex = current_vertex;
+ current_vertex = *first;
- BOOST_REQUIRE (boost::lookup_edge (current_vertex, last_vertex, g).second);
- }
+ BOOST_TEST(
+ boost::lookup_edge(current_vertex, last_vertex, g).second);
+ }
- BOOST_REQUIRE (boost::lookup_edge (first_vertex, current_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)
+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);
- }
+ 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 test_main (int argc, char **argv)
+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_REQUIRE (is_bipartite (bipartite_vector_graph));
- BOOST_REQUIRE (!is_bipartite (non_bipartite_vector_graph));
-
- return 0;
+ 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();
}
projects / ceph.git / blobdiff