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 >
sub_cmp(subgraph_t const & g1,subgraph_t const & g2)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
main(int,char * [])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, N, N * 2, gen, std::back_inserter(vertex_set),
65 std::back_inserter(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(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(v_global, g_s);
95 sub_vertex_set.push_back(v);
96 sub_global_map.push_back(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(sub_global_map, source(e, g))
103 && container_contains(sub_global_map, target(e, g)))
104 sub_edge_set.push_back(std::make_pair(
105 global_sub_map[source(e, g)], global_sub_map[target(e, g)]));
106
107 gt.test_incidence_graph(sub_vertex_set, sub_edge_set, g_s);
108 gt.test_bidirectional_graph(sub_vertex_set, sub_edge_set, g_s);
109 gt.test_adjacency_graph(sub_vertex_set, sub_edge_set, g_s);
110 gt.test_vertex_list_graph(sub_vertex_set, g_s);
111 gt.test_edge_list_graph(sub_vertex_set, sub_edge_set, g_s);
112 gt.test_adjacency_matrix(sub_vertex_set, sub_edge_set, g_s);
113
114 if (num_vertices(g_s) == 0)
115 return 0;
116 std::vector< int > weights;
117 for (unsigned i = 0; i < num_vertices(g_s); ++i)
118 weights.push_back(i * 2);
119 gt.test_vertex_property_graph(weights, vertex_color_t(), 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(v1, v2, g);
130
131 subgraph_t sub
132 = g.create_subgraph(vertices(g).first, vertices(g).second);
133
134 graph_t::edge_iterator ei, ee;
135 for (boost::tie(ei, ee) = edges(sub); ei != ee; ++ei)
136 {
137 // This used to segfault.
138 get(edge_weight, sub, *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(g1);
153 }
154 subgraph_t::vertex_iterator vi_start, vi, vi_end, vj_start, vj,
155 vj_end;
156 for (tie(vi, vi_end) = vertices(g1); vi != vi_end; ++vi)
157 {
158 for (tie(vj, vj_end) = vertices(g1); vj != vj_end; ++vj)
159 {
160 if (*vi != *vj)
161 {
162 add_edge(*vi, *vj, g1);
163 }
164 }
165 }
166 tie(vi_start, vi_end) = vertices(g1);
167 vi = vi_start;
168 for (size_t i = 0; i < 4; i++)
169 {
170 ++vi;
171 }
172 g1.create_subgraph(vi_start, vi);
173 g1.create_subgraph(++vi, vi_end);
174 subgraph_t::children_iterator gi1, gi2;
175 gi2 = g1.children().first;
176 gi1 = gi2++;
177 tie(vi_start, vi_end) = vertices(*gi1);
178 vi = vi_start;
179 tie(vj_start, vj_end) = vertices(*gi2);
180 vj = vj_start;
181 for (size_t i = 0; i < 2; i++)
182 {
183 ++vi;
184 ++vj;
185 }
186 (*gi1).create_subgraph(vi_start, vi);
187 (*gi1).create_subgraph(++vi, vi_end);
188 (*gi2).create_subgraph(vj_start, vj);
189 (*gi2).create_subgraph(++vj, 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(&VertexBundle::value, g);
210 get(map, 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