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 | |
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 | |
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 > |
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 | |
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(g&: gVV, num_cycles, cycle_size); |
86 | reset_edge_index(g&: gVV); |
87 | std::vector< int > gVV_components(num_vertices(g_: 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(p: boost::vertex_index, g&: gVV)); |
92 | BOOST_TEST(connected_components(gVV, gVV_components_pm) |
93 | == static_cast< int >(num_cycles)); |
94 | make_connected(g&: 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(g&: gLV, num_cycles, cycle_size); |
102 | reset_edge_index(g&: gLV); |
103 | std::vector< int > gLV_components(num_vertices(g_: 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(p: boost::vertex_index, g&: gLV)); |
108 | BOOST_TEST(connected_components(gLV, gLV_components_pm) |
109 | == static_cast< int >(num_cycles)); |
110 | make_connected(g&: 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(g&: gVL, num_cycles, cycle_size); |
118 | reset_edge_index(g&: gVL); |
119 | reset_vertex_index(g&: 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(g&: 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(g&: gLL, num_cycles, cycle_size); |
133 | reset_edge_index(g&: gLL); |
134 | reset_vertex_index(g&: 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(g&: 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(g_: gVV)); |
148 | make_connected(g&: gVV); |
149 | BOOST_TEST(num_edges(gVV) == VV_num_edges); |
150 | |
151 | graph_traits< VLgraph_t >::edges_size_type VL_num_edges(num_edges(g_: gVL)); |
152 | make_connected(g&: gVL); |
153 | BOOST_TEST(num_edges(gVL) == VL_num_edges); |
154 | |
155 | graph_traits< LVgraph_t >::edges_size_type LV_num_edges(num_edges(g_: gLV)); |
156 | make_connected(g&: gLV); |
157 | BOOST_TEST(num_edges(gLV) == LV_num_edges); |
158 | |
159 | graph_traits< LLgraph_t >::edges_size_type LL_num_edges(num_edges(g_: gLL)); |
160 | make_connected(g&: gLL); |
161 | BOOST_TEST(num_edges(gLL) == LL_num_edges); |
162 | |
163 | return boost::report_errors(); |
164 | } |
165 | |