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.
23template < typename subgraph_t >
24void 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
47int 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

source code of boost/libs/graph/test/subgraph.cpp