123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175 |
- // Copyright (C) 2005-2008 The Trustees of Indiana University.
- // Use, modification and distribution is subject to 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)
- // Authors: Douglas Gregor
- // Andrew Lumsdaine
- //
- // Test of Hohberg's distributed biconnected components algorithm.
- #include <boost/graph/use_mpi.hpp>
- #include <boost/config.hpp>
- #include <boost/throw_exception.hpp>
- #include <boost/graph/distributed/hohberg_biconnected_components.hpp>
- #include <boost/graph/distributed/mpi_process_group.hpp>
- #include <boost/graph/distributed/adjacency_list.hpp>
- #include <boost/test/minimal.hpp>
- #ifdef BOOST_NO_EXCEPTIONS
- void
- boost::throw_exception(std::exception const& ex)
- {
- std::cout << ex.what() << std::endl;
- abort();
- }
- #endif
- using boost::graph::distributed::mpi_process_group;
- using namespace boost;
- template<typename Graph>
- void check_components(const Graph& g, std::size_t num_comps)
- {
- std::size_t not_mapped = (std::numeric_limits<std::size_t>::max)();
- std::vector<std::size_t> color_to_name(num_comps, not_mapped);
- BGL_FORALL_EDGES_T(e, g, Graph) {
- BOOST_CHECK(get(edge_color, g, e) < num_comps);
- if (color_to_name[get(edge_color, g, e)] == not_mapped)
- color_to_name[get(edge_color, g, e)] = get(edge_name, g, e);
- BOOST_CHECK(color_to_name[get(edge_color,g,e)] == get(edge_name,g,e));
- if (color_to_name[get(edge_color,g,e)] != get(edge_name,g,e)) {
- for (std::size_t i = 0; i < color_to_name.size(); ++i)
- std::cerr << color_to_name[i] << ' ';
-
- std::cerr << std::endl;
- std::cerr << color_to_name[get(edge_color,g,e)] << " != "
- << get(edge_name,g,e) << " on edge "
- << local(source(e, g)) << " -> " << local(target(e, g))
- << std::endl;
- }
- }
- }
- template<typename Graph>
- void
- test_small_hohberg_biconnected_components(Graph& g, int n, int comps_expected,
- bool single_component = true)
- {
- using boost::graph::distributed::hohberg_biconnected_components;
- bool is_root = (process_id(process_group(g)) == 0);
- if (single_component) {
- for (int i = 0; i < n; ++i) {
- if (is_root) std::cerr << "Testing with leader = " << i << std::endl;
-
- // Scramble edge_color_map
- BGL_FORALL_EDGES_T(e, g, Graph)
- put(edge_color, g, e, 17);
-
- typename graph_traits<Graph>::vertex_descriptor leader = vertex(i, g);
- int num_comps =
- hohberg_biconnected_components(g, get(edge_color, g), &leader,
- &leader + 1);
-
- BOOST_CHECK(num_comps == comps_expected);
- check_components(g, num_comps);
- }
- }
- if (is_root) std::cerr << "Testing simple interface." << std::endl;
- synchronize(g);
- // Scramble edge_color_map
- int i = 0;
- BGL_FORALL_EDGES_T(e, g, Graph) {
- ++i;
- put(edge_color, g, e, 17);
- }
- std::cerr << process_id(process_group(g)) << " has "
- << i << " edges.\n";
- int num_comps = hohberg_biconnected_components(g, get(edge_color, g));
- BOOST_CHECK(num_comps == comps_expected);
- check_components(g, num_comps);
- }
- int test_main(int argc, char* argv[])
- {
- mpi::environment env(argc, argv);
- typedef adjacency_list<listS,
- distributedS<mpi_process_group, vecS>,
- undirectedS,
- // Vertex properties
- no_property,
- // Edge properties
- property<edge_name_t, std::size_t,
- property<edge_color_t, std::size_t> > > Graph;
- typedef std::pair<int, int> E;
- {
- // Example 1: A single component with 2 bicomponents
- E edges_init[] = { E(0, 1), E(0, 2), E(1, 3), E(2, 4), E(3, 4), E(4, 5),
- E(4, 6), E(5, 6) };
- const int m = sizeof(edges_init) / sizeof(E);
- std::size_t expected_components[m] = { 0, 0, 0, 0, 0, 1, 1, 1 };
- const int n = 7;
- Graph g(&edges_init[0], &edges_init[0] + m, &expected_components[0], n);
- int num_comps_expected =
- *std::max_element(&expected_components[0], &expected_components[0] + m)
- + 1;
- test_small_hohberg_biconnected_components(g, n, num_comps_expected);
- }
- {
- // Example 2: A single component with 4 bicomponents
- E edges_init[] = { E(0, 1), E(1, 2), E(2, 0), E(2, 3), E(3, 4), E(4, 5),
- E(5, 2), E(3, 6), E(6, 7), E(7, 8), E(8, 6) };
- const int m = sizeof(edges_init) / sizeof(E);
- std::size_t expected_components[m] = { 0, 0, 0, 1, 1, 1, 1, 2, 3, 3, 3 };
- const int n = 9;
- Graph g(&edges_init[0], &edges_init[0] + m, &expected_components[0], n);
- int num_comps_expected =
- *std::max_element(&expected_components[0], &expected_components[0] + m)
- + 1;
- test_small_hohberg_biconnected_components(g, n, num_comps_expected);
- }
- {
- // Example 3: Two components, 6 bicomponents
- // This is just the concatenation of the two previous graphs.
- E edges_init[] = { /* Example 1 graph */
- E(0, 1), E(0, 2), E(1, 3), E(2, 4), E(3, 4), E(4, 5),
- E(4, 6), E(5, 6),
- /* Example 2 graph */
- E(7, 8), E(8, 9), E(9, 7), E(9, 10), E(10, 11),
- E(11, 12), E(12, 9), E(10, 13), E(13, 14), E(14, 15),
- E(15, 13) };
- const int m = sizeof(edges_init) / sizeof(E);
- std::size_t expected_components[m] =
- { /* Example 1 */0, 0, 0, 0, 0, 1, 1, 1,
- /* Example 2 */2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5 };
- const int n = 16;
- Graph g(&edges_init[0], &edges_init[0] + m, &expected_components[0], n);
- int num_comps_expected =
- *std::max_element(&expected_components[0], &expected_components[0] + m)
- + 1;
- test_small_hohberg_biconnected_components(g, n, num_comps_expected,
- false);
- }
- return 0;
- }
|