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
176
177
178
179
180
181
182
183
184
|
//=======================================================================
// Copyright 2007 Aaron Windsor
//
// 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/properties.hpp>
#include <boost/graph/make_connected.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/property_map.hpp>
#include <boost/vector_property_map.hpp>
#include <boost/test/minimal.hpp>
using namespace boost;
template <typename Graph>
void reset_edge_index(Graph& g)
{
typename property_map<Graph, edge_index_t>::type index = get(edge_index, g);
typename graph_traits<Graph>::edge_iterator ei, ei_end;
typename graph_traits<Graph>::edges_size_type cnt = 0;
for(tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
put(index, *ei, cnt++);
}
template <typename Graph>
void reset_vertex_index(Graph& g)
{
typename property_map<Graph, vertex_index_t>::type index = get(vertex_index, g);
typename graph_traits<Graph>::vertex_iterator vi, vi_end;
typename graph_traits<Graph>::vertices_size_type cnt = 0;
for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
put(index, *vi, cnt++);
}
template <typename Graph>
void make_disconnected_cycles(Graph& g, int num_cycles, int cycle_size)
{
// This graph will consist of num_cycles cycles, each of which
// has cycle_size vertices and edges. The entire graph has
// num_cycles * cycle_size vertices and edges, and requires
// num_cycles - 1 edges to make it connected
typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
for(int i = 0; i < num_cycles; ++i)
{
vertex_t first_vertex = add_vertex(g);
vertex_t prev_vertex;
vertex_t curr_vertex = first_vertex;
for(int j = 1; j < cycle_size; ++j)
{
prev_vertex = curr_vertex;
curr_vertex = add_vertex(g);
add_edge(prev_vertex, curr_vertex, g);
}
add_edge(curr_vertex, first_vertex, g);
}
}
int test_main(int, char* [])
{
typedef adjacency_list
<vecS,
vecS,
undirectedS,
property<vertex_index_t, int>,
property<edge_index_t, int>
>
VVgraph_t;
typedef adjacency_list
<vecS,
listS,
undirectedS,
property<vertex_index_t, int>,
property<edge_index_t, int>
>
VLgraph_t;
typedef adjacency_list
<listS,
vecS,
undirectedS,
property<vertex_index_t, int>,
property<edge_index_t, int>
>
LVgraph_t;
typedef adjacency_list
<listS,
listS,
undirectedS,
property<vertex_index_t, int>,
property<edge_index_t, int>
>
LLgraph_t;
VVgraph_t gVV;
std::size_t num_cycles = 10;
std::size_t cycle_size = 10;
make_disconnected_cycles(gVV, num_cycles, cycle_size);
reset_edge_index(gVV);
std::vector<int> gVV_components(num_vertices(gVV));
BOOST_CHECK(connected_components(gVV, &gVV_components[0]) ==
static_cast<int>(num_cycles));
make_connected(gVV);
BOOST_CHECK(connected_components(gVV, &gVV_components[0]) == 1);
BOOST_CHECK(num_edges(gVV) == num_cycles * cycle_size + num_cycles - 1);
LVgraph_t gLV;
num_cycles = 20;
cycle_size = 20;
make_disconnected_cycles(gLV, num_cycles, cycle_size);
reset_edge_index(gLV);
std::vector<int> gLV_components(num_vertices(gLV));
BOOST_CHECK(connected_components(gLV, &gLV_components[0]) ==
static_cast<int>(num_cycles));
make_connected(gLV);
BOOST_CHECK(connected_components(gLV, &gLV_components[0]) == 1);
BOOST_CHECK(num_edges(gLV) == num_cycles * cycle_size + num_cycles - 1);
VLgraph_t gVL;
num_cycles = 30;
cycle_size = 30;
make_disconnected_cycles(gVL, num_cycles, cycle_size);
reset_edge_index(gVL);
reset_vertex_index(gVL);
BOOST_CHECK(connected_components(gVL, make_vector_property_map<int>(get(vertex_index,gVL)))
== static_cast<int>(num_cycles)
);
make_connected(gVL);
BOOST_CHECK(connected_components(gVL, make_vector_property_map<int>(get(vertex_index,gVL)))
== 1
);
BOOST_CHECK(num_edges(gVL) == num_cycles * cycle_size + num_cycles - 1);
LLgraph_t gLL;
num_cycles = 40;
cycle_size = 40;
make_disconnected_cycles(gLL, num_cycles, cycle_size);
reset_edge_index(gLL);
reset_vertex_index(gLL);
BOOST_CHECK(connected_components(gLL, make_vector_property_map<int>(get(vertex_index,gLL)))
== static_cast<int>(num_cycles));
make_connected(gLL);
BOOST_CHECK(connected_components(gLL, make_vector_property_map<int>(get(vertex_index,gLL)))
== 1
);
BOOST_CHECK(num_edges(gLL) == num_cycles * cycle_size + num_cycles - 1);
// Now make sure that no edges are added to an already connected graph
// when you call make_connected again
graph_traits<VVgraph_t>::edges_size_type VV_num_edges(num_edges(gVV));
make_connected(gVV);
BOOST_CHECK(num_edges(gVV) == VV_num_edges);
graph_traits<VLgraph_t>::edges_size_type VL_num_edges(num_edges(gVL));
make_connected(gVL);
BOOST_CHECK(num_edges(gVL) == VL_num_edges);
graph_traits<LVgraph_t>::edges_size_type LV_num_edges(num_edges(gLV));
make_connected(gLV);
BOOST_CHECK(num_edges(gLV) == LV_num_edges);
graph_traits<LLgraph_t>::edges_size_type LL_num_edges(num_edges(gLL));
make_connected(gLL);
BOOST_CHECK(num_edges(gLL) == LL_num_edges);
return 0;
}
|
