1 //=======================================================================
2 // Copyright 2007 Aaron Windsor
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
8
9 #include <boost/graph/adjacency_list.hpp>
10 #include <boost/graph/properties.hpp>
11 #include <boost/graph/make_connected.hpp>
12 #include <boost/graph/connected_components.hpp>
13 #include <boost/property_map/property_map.hpp>
14 #include <boost/property_map/vector_property_map.hpp>
15 #include <boost/core/lightweight_test.hpp>
16
17 using namespace boost;
18
reset_edge_index(Graph & g)19 template < typename Graph > void reset_edge_index(Graph& g)
20 {
21 typename property_map< Graph, edge_index_t >::type index
22 = get(edge_index, g);
23 typename graph_traits< Graph >::edge_iterator ei, ei_end;
24 typename graph_traits< Graph >::edges_size_type cnt = 0;
25 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
26 put(index, *ei, cnt++);
27 }
28
reset_vertex_index(Graph & g)29 template < typename Graph > void reset_vertex_index(Graph& g)
30 {
31 typename property_map< Graph, vertex_index_t >::type index
32 = get(vertex_index, g);
33 typename graph_traits< Graph >::vertex_iterator vi, vi_end;
34 typename graph_traits< Graph >::vertices_size_type cnt = 0;
35 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
36 put(index, *vi, cnt++);
37 }
38
39 template < typename Graph >
make_disconnected_cycles(Graph & g,int num_cycles,int cycle_size)40 void make_disconnected_cycles(Graph& g, int num_cycles, int cycle_size)
41 {
42 // This graph will consist of num_cycles cycles, each of which
43 // has cycle_size vertices and edges. The entire graph has
44 // num_cycles * cycle_size vertices and edges, and requires
45 // num_cycles - 1 edges to make it connected
46
47 typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
48
49 for (int i = 0; i < num_cycles; ++i)
50 {
51 vertex_t first_vertex = add_vertex(g);
52 vertex_t prev_vertex;
53 vertex_t curr_vertex = first_vertex;
54 for (int j = 1; j < cycle_size; ++j)
55 {
56 prev_vertex = curr_vertex;
57 curr_vertex = add_vertex(g);
58 add_edge(prev_vertex, curr_vertex, g);
59 }
60 add_edge(curr_vertex, first_vertex, g);
61 }
62 }
63
main(int,char * [])64 int main(int, char*[])
65 {
66 typedef adjacency_list< vecS, vecS, undirectedS,
67 property< vertex_index_t, int >, property< edge_index_t, int > >
68 VVgraph_t;
69
70 typedef adjacency_list< vecS, listS, undirectedS,
71 property< vertex_index_t, int >, property< edge_index_t, int > >
72 VLgraph_t;
73
74 typedef adjacency_list< listS, vecS, undirectedS,
75 property< vertex_index_t, int >, property< edge_index_t, int > >
76 LVgraph_t;
77
78 typedef adjacency_list< listS, listS, undirectedS,
79 property< vertex_index_t, int >, property< edge_index_t, int > >
80 LLgraph_t;
81
82 VVgraph_t gVV;
83 std::size_t num_cycles = 10;
84 std::size_t cycle_size = 10;
85 make_disconnected_cycles(gVV, num_cycles, cycle_size);
86 reset_edge_index(gVV);
87 std::vector< int > gVV_components(num_vertices(gVV));
88 boost::iterator_property_map< std::vector< int >::iterator,
89 boost::property_map< VVgraph_t, boost::vertex_index_t >::const_type >
90 gVV_components_pm(
91 gVV_components.begin(), get(boost::vertex_index, gVV));
92 BOOST_TEST(connected_components(gVV, gVV_components_pm)
93 == static_cast< int >(num_cycles));
94 make_connected(gVV);
95 BOOST_TEST(connected_components(gVV, gVV_components_pm) == 1);
96 BOOST_TEST(num_edges(gVV) == num_cycles * cycle_size + num_cycles - 1);
97
98 LVgraph_t gLV;
99 num_cycles = 20;
100 cycle_size = 20;
101 make_disconnected_cycles(gLV, num_cycles, cycle_size);
102 reset_edge_index(gLV);
103 std::vector< int > gLV_components(num_vertices(gLV));
104 boost::iterator_property_map< std::vector< int >::iterator,
105 boost::property_map< VVgraph_t, boost::vertex_index_t >::const_type >
106 gLV_components_pm(
107 gLV_components.begin(), get(boost::vertex_index, gLV));
108 BOOST_TEST(connected_components(gLV, gLV_components_pm)
109 == static_cast< int >(num_cycles));
110 make_connected(gLV);
111 BOOST_TEST(connected_components(gLV, gLV_components_pm) == 1);
112 BOOST_TEST(num_edges(gLV) == num_cycles * cycle_size + num_cycles - 1);
113
114 VLgraph_t gVL;
115 num_cycles = 30;
116 cycle_size = 30;
117 make_disconnected_cycles(gVL, num_cycles, cycle_size);
118 reset_edge_index(gVL);
119 reset_vertex_index(gVL);
120 BOOST_TEST(connected_components(gVL,
121 make_vector_property_map< int >(get(vertex_index, gVL)))
122 == static_cast< int >(num_cycles));
123 make_connected(gVL);
124 BOOST_TEST(connected_components(gVL,
125 make_vector_property_map< int >(get(vertex_index, gVL)))
126 == 1);
127 BOOST_TEST(num_edges(gVL) == num_cycles * cycle_size + num_cycles - 1);
128
129 LLgraph_t gLL;
130 num_cycles = 40;
131 cycle_size = 40;
132 make_disconnected_cycles(gLL, num_cycles, cycle_size);
133 reset_edge_index(gLL);
134 reset_vertex_index(gLL);
135 BOOST_TEST(connected_components(gLL,
136 make_vector_property_map< int >(get(vertex_index, gLL)))
137 == static_cast< int >(num_cycles));
138 make_connected(gLL);
139 BOOST_TEST(connected_components(gLL,
140 make_vector_property_map< int >(get(vertex_index, gLL)))
141 == 1);
142 BOOST_TEST(num_edges(gLL) == num_cycles * cycle_size + num_cycles - 1);
143
144 // Now make sure that no edges are added to an already connected graph
145 // when you call make_connected again
146
147 graph_traits< VVgraph_t >::edges_size_type VV_num_edges(num_edges(gVV));
148 make_connected(gVV);
149 BOOST_TEST(num_edges(gVV) == VV_num_edges);
150
151 graph_traits< VLgraph_t >::edges_size_type VL_num_edges(num_edges(gVL));
152 make_connected(gVL);
153 BOOST_TEST(num_edges(gVL) == VL_num_edges);
154
155 graph_traits< LVgraph_t >::edges_size_type LV_num_edges(num_edges(gLV));
156 make_connected(gLV);
157 BOOST_TEST(num_edges(gLV) == LV_num_edges);
158
159 graph_traits< LLgraph_t >::edges_size_type LL_num_edges(num_edges(gLL));
160 make_connected(gLL);
161 BOOST_TEST(num_edges(gLL) == LL_num_edges);
162
163 return boost::report_errors();
164 }
165