1 | // (C) Copyright Jeremy Siek 2004 |
2 | // Distributed under the Boost Software License, Version 1.0. (See |
3 | // accompanying file LICENSE_1_0.txt or copy at |
4 | // http://www.boost.org/LICENSE_1_0.txt) |
5 | |
6 | #include <set> |
7 | |
8 | #include <boost/core/lightweight_test.hpp> |
9 | |
10 | #include <boost/graph/subgraph.hpp> |
11 | #include <boost/graph/adjacency_list.hpp> |
12 | #include <boost/graph/random.hpp> |
13 | #include "graph_test.hpp" |
14 | #include <boost/graph/iteration_macros.hpp> |
15 | #include <boost/random/mersenne_twister.hpp> |
16 | |
17 | #include "test_graph.hpp" |
18 | |
19 | // UNDER CONSTRUCTION |
20 | |
21 | // This is a helper function to recusively compare two subgraphs, |
22 | // including the index for every local edges and their children. |
23 | template < typename subgraph_t > |
24 | void sub_cmp(subgraph_t const& g1, subgraph_t const& g2) |
25 | { |
26 | BOOST_TEST(g1.is_root() == g2.is_root()); |
27 | BOOST_TEST(num_vertices(g1) == num_vertices(g2)); |
28 | BOOST_TEST(num_edges(g1) == num_edges(g2)); |
29 | typename subgraph_t::edge_iterator e1_i, e1_i_end, e2_i, e2_i_end; |
30 | boost::tie(e1_i, e1_i_end) = edges(g1); |
31 | boost::tie(e2_i, e2_i_end) = edges(g2); |
32 | for (; e1_i != e1_i_end; ++e1_i, ++e2_i) |
33 | { |
34 | BOOST_TEST(get(boost::edge_index, g1, *e1_i) |
35 | == get(boost::edge_index, g2, *e2_i)); |
36 | } |
37 | typename subgraph_t::const_children_iterator g1_i, g1_i_end, g2_i, g2_i_end; |
38 | boost::tie(g1_i, g1_i_end) = g1.children(); |
39 | boost::tie(g2_i, g2_i_end) = g2.children(); |
40 | for (; g1_i != g1_i_end && g2_i != g2_i_end; ++g1_i, ++g2_i) |
41 | { |
42 | sub_cmp(*g1_i, *g2_i); |
43 | } |
44 | BOOST_TEST(g1_i == g1_i_end && g2_i == g2_i_end); |
45 | } |
46 | |
47 | int main(int, char*[]) |
48 | { |
49 | using namespace boost; |
50 | typedef adjacency_list< vecS, vecS, bidirectionalS, |
51 | property< vertex_color_t, int >, |
52 | property< edge_index_t, std::size_t, property< edge_weight_t, int > > > |
53 | graph_t; |
54 | typedef subgraph< graph_t > subgraph_t; |
55 | typedef graph_traits< subgraph_t >::vertex_descriptor vertex_t; |
56 | |
57 | mt19937 gen; |
58 | for (int t = 0; t < 100; t += 5) |
59 | { |
60 | subgraph_t g; |
61 | int N = t + 2; |
62 | std::vector< vertex_t > vertex_set; |
63 | std::vector< std::pair< vertex_t, vertex_t > > edge_set; |
64 | generate_random_graph(g, V: N, E: N * 2, gen, vertex_out: std::back_inserter(x&: vertex_set), |
65 | edge_out: std::back_inserter(x&: edge_set)); |
66 | |
67 | graph_test< subgraph_t > gt; |
68 | |
69 | gt.test_incidence_graph(vertex_set, edge_set, g); |
70 | gt.test_bidirectional_graph(vertex_set, edge_set, g); |
71 | gt.test_adjacency_graph(vertex_set, edge_set, g); |
72 | gt.test_vertex_list_graph(vertex_set, g); |
73 | gt.test_edge_list_graph(vertex_set, edge_set, g); |
74 | gt.test_adjacency_matrix(vertex_set, edge_set, g); |
75 | |
76 | std::vector< vertex_t > sub_vertex_set; |
77 | std::vector< vertex_t > sub_global_map; |
78 | std::vector< vertex_t > global_sub_map(num_vertices(g)); |
79 | std::vector< std::pair< vertex_t, vertex_t > > sub_edge_set; |
80 | |
81 | subgraph_t& g_s = g.create_subgraph(); |
82 | |
83 | const std::set< vertex_t >::size_type Nsub = N / 2; |
84 | |
85 | // Collect a set of random vertices to put in the subgraph |
86 | std::set< vertex_t > verts; |
87 | while (verts.size() < Nsub) |
88 | verts.insert(x: random_vertex(g, gen)); |
89 | |
90 | for (std::set< vertex_t >::iterator it = verts.begin(); |
91 | it != verts.end(); ++it) |
92 | { |
93 | vertex_t v_global = *it; |
94 | vertex_t v = add_vertex(u_global: v_global, g&: g_s); |
95 | sub_vertex_set.push_back(x: v); |
96 | sub_global_map.push_back(x: v_global); |
97 | global_sub_map[v_global] = v; |
98 | } |
99 | |
100 | // compute induced edges |
101 | BGL_FORALL_EDGES(e, g, subgraph_t) |
102 | if (container_contains(c: sub_global_map, value: source(e, g)) |
103 | && container_contains(c: sub_global_map, value: target(e, g))) |
104 | sub_edge_set.push_back(x: std::make_pair( |
105 | x&: global_sub_map[source(e, g)], y&: global_sub_map[target(e, g)])); |
106 | |
107 | gt.test_incidence_graph(vertex_set: sub_vertex_set, edge_set: sub_edge_set, g: g_s); |
108 | gt.test_bidirectional_graph(vertex_set: sub_vertex_set, edge_set: sub_edge_set, g: g_s); |
109 | gt.test_adjacency_graph(vertex_set: sub_vertex_set, edge_set: sub_edge_set, g: g_s); |
110 | gt.test_vertex_list_graph(vertex_set: sub_vertex_set, g: g_s); |
111 | gt.test_edge_list_graph(vertex_set: sub_vertex_set, edge_set: sub_edge_set, g: g_s); |
112 | gt.test_adjacency_matrix(vertex_set: sub_vertex_set, edge_set: sub_edge_set, g: g_s); |
113 | |
114 | if (num_vertices(g: g_s) == 0) |
115 | return 0; |
116 | std::vector< int > weights; |
117 | for (unsigned i = 0; i < num_vertices(g: g_s); ++i) |
118 | weights.push_back(x: i * 2); |
119 | gt.test_vertex_property_graph(vertex_prop: weights, tag: vertex_color_t(), g&: g_s); |
120 | |
121 | // A regression test: the copy constructor of subgraph did not |
122 | // copy one of the members, so local_edge->global_edge mapping |
123 | // was broken. |
124 | { |
125 | subgraph_t g; |
126 | graph_t::vertex_descriptor v1, v2; |
127 | v1 = add_vertex(g); |
128 | v2 = add_vertex(g); |
129 | add_edge(u: v1, v: v2, g); |
130 | |
131 | subgraph_t sub |
132 | = g.create_subgraph(first: vertices(g).first, last: vertices(g).second); |
133 | |
134 | graph_t::edge_iterator ei, ee; |
135 | for (boost::tie(t0&: ei, t1&: ee) = edges(g: sub); ei != ee; ++ei) |
136 | { |
137 | // This used to segfault. |
138 | get(p: edge_weight, g: sub, k: *ei); |
139 | } |
140 | } |
141 | |
142 | // This block generates a complete graph with 8 vertices, |
143 | // and puts the first and last four of the vertices into two children. |
144 | // Do these again to the children, so there are 4 grandchildren with 2 |
145 | // vertices for each. Use the copy constructor to generate a copy and |
146 | // compare with the original one. |
147 | { |
148 | subgraph_t g1; |
149 | |
150 | for (size_t i = 0; i < 8; i++) |
151 | { |
152 | add_vertex(g&: g1); |
153 | } |
154 | subgraph_t::vertex_iterator vi_start, vi, vi_end, vj_start, vj, |
155 | vj_end; |
156 | for (tie(t0&: vi, t1&: vi_end) = vertices(g: g1); vi != vi_end; ++vi) |
157 | { |
158 | for (tie(t0&: vj, t1&: vj_end) = vertices(g: g1); vj != vj_end; ++vj) |
159 | { |
160 | if (*vi != *vj) |
161 | { |
162 | add_edge(u: *vi, v: *vj, g&: g1); |
163 | } |
164 | } |
165 | } |
166 | tie(t0&: vi_start, t1&: vi_end) = vertices(g: g1); |
167 | vi = vi_start; |
168 | for (size_t i = 0; i < 4; i++) |
169 | { |
170 | ++vi; |
171 | } |
172 | g1.create_subgraph(first: vi_start, last: vi); |
173 | g1.create_subgraph(first: ++vi, last: vi_end); |
174 | subgraph_t::children_iterator gi1, gi2; |
175 | gi2 = g1.children().first; |
176 | gi1 = gi2++; |
177 | tie(t0&: vi_start, t1&: vi_end) = vertices(g: *gi1); |
178 | vi = vi_start; |
179 | tie(t0&: vj_start, t1&: vj_end) = vertices(g: *gi2); |
180 | vj = vj_start; |
181 | for (size_t i = 0; i < 2; i++) |
182 | { |
183 | ++vi; |
184 | ++vj; |
185 | } |
186 | (*gi1).create_subgraph(first: vi_start, last: vi); |
187 | (*gi1).create_subgraph(first: ++vi, last: vi_end); |
188 | (*gi2).create_subgraph(first: vj_start, last: vj); |
189 | (*gi2).create_subgraph(first: ++vj, last: vj_end); |
190 | subgraph_t g2(g1); |
191 | sub_cmp(g1, g2); |
192 | } |
193 | |
194 | // Bootstrap the test_graph framework. |
195 | // TODO: Subgraph is fundamentally broken for property types. |
196 | // TODO: Under construction. |
197 | { |
198 | using namespace boost; |
199 | typedef property< edge_index_t, size_t, EdgeBundle > EdgeProp; |
200 | typedef adjacency_list< vecS, vecS, directedS, VertexBundle, |
201 | EdgeProp > |
202 | BaseGraph; |
203 | typedef subgraph< BaseGraph > Graph; |
204 | typedef graph_traits< Graph >::vertex_descriptor Vertex; |
205 | Graph g; |
206 | Vertex v = add_vertex(g); |
207 | |
208 | typedef property_map< Graph, int VertexBundle::* >::type BundleMap; |
209 | BundleMap map = get(p: &VertexBundle::value, g); |
210 | get(pa: map, k: v); |
211 | // put(map, v, 5); |
212 | // BOOST_ASSERT(get(map, v) == 5); |
213 | |
214 | // test_graph(g); |
215 | return boost::report_errors(); |
216 | } |
217 | } |
218 | return boost::report_errors(); |
219 | } |
220 | |