1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
// 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;
}
|
