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)
8 #include <boost/test/minimal.hpp>
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>
17 #include "test_graph.hpp"
22 // This is a helper function to recusively compare two subgraphs,
23 // including the index for every local edges and their children.
24 template<typename subgraph_t
>
25 void sub_cmp(subgraph_t
const &g1
, subgraph_t
const &g2
)
27 BOOST_CHECK(g1
.is_root() == g2
.is_root());
28 BOOST_CHECK(num_vertices(g1
) == num_vertices(g2
));
29 BOOST_CHECK(num_edges(g1
) == num_edges(g2
));
30 typename
subgraph_t::edge_iterator e1_i
, e1_i_end
, e2_i
, e2_i_end
;
31 boost::tie(e1_i
, e1_i_end
) = edges(g1
);
32 boost::tie(e2_i
, e2_i_end
) = edges(g2
);
33 for(; e1_i
!= e1_i_end
; ++e1_i
, ++e2_i
)
35 BOOST_CHECK(get(boost::edge_index
, g1
, *e1_i
)
36 == get(boost::edge_index
, g2
, *e2_i
));
38 typename
subgraph_t::const_children_iterator g1_i
, g1_i_end
, g2_i
, g2_i_end
;
39 boost::tie(g1_i
, g1_i_end
) = g1
.children();
40 boost::tie(g2_i
, g2_i_end
) = g2
.children();
41 for(; g1_i
!= g1_i_end
&& g2_i
!= g2_i_end
; ++g1_i
, ++g2_i
)
43 sub_cmp(*g1_i
, *g2_i
);
45 BOOST_CHECK(g1_i
== g1_i_end
&& g2_i
== g2_i_end
);
48 int test_main(int, char*[])
50 using namespace boost
;
51 typedef adjacency_list
<vecS
, vecS
, bidirectionalS
,
52 property
<vertex_color_t
, int>,
53 property
<edge_index_t
, std::size_t, property
<edge_weight_t
, int> >
55 typedef subgraph
<graph_t
> subgraph_t
;
56 typedef graph_traits
<subgraph_t
>::vertex_descriptor vertex_t
;
59 for (int t
= 0; t
< 100; t
+= 5) {
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
,
65 std::back_inserter(vertex_set
),
66 std::back_inserter(edge_set
));
68 graph_test
< subgraph_t
> gt
;
70 gt
.test_incidence_graph(vertex_set
, edge_set
, g
);
71 gt
.test_bidirectional_graph(vertex_set
, edge_set
, g
);
72 gt
.test_adjacency_graph(vertex_set
, edge_set
, g
);
73 gt
.test_vertex_list_graph(vertex_set
, g
);
74 gt
.test_edge_list_graph(vertex_set
, edge_set
, g
);
75 gt
.test_adjacency_matrix(vertex_set
, edge_set
, g
);
77 std::vector
<vertex_t
> sub_vertex_set
;
78 std::vector
<vertex_t
> sub_global_map
;
79 std::vector
<vertex_t
> global_sub_map(num_vertices(g
));
80 std::vector
< std::pair
<vertex_t
, vertex_t
> > sub_edge_set
;
82 subgraph_t
& g_s
= g
.create_subgraph();
84 const std::set
<vertex_t
>::size_type Nsub
= N
/2;
86 // Collect a set of random vertices to put in the subgraph
87 std::set
<vertex_t
> verts
;
88 while (verts
.size() < Nsub
)
89 verts
.insert(random_vertex(g
, gen
));
91 for (std::set
<vertex_t
>::iterator it
= verts
.begin();
92 it
!= verts
.end(); ++it
) {
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
;
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(global_sub_map
[source(e
, g
)],
105 global_sub_map
[target(e
, g
)]));
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
);
114 if (num_vertices(g_s
) == 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
);
121 // A regression test: the copy constructor of subgraph did not
122 // copy one of the members, so local_edge->global_edge mapping
126 graph_t::vertex_descriptor v1
, v2
;
131 subgraph_t sub
= g
.create_subgraph(vertices(g
).first
, vertices(g
).second
);
133 graph_t::edge_iterator ei
, ee
;
134 for (boost::tie(ei
, ee
) = edges(sub
); ei
!= ee
; ++ei
) {
135 // This used to segfault.
136 get(edge_weight
, sub
, *ei
);
140 // This block generates a complete graph with 8 vertices,
141 // and puts the first and last four of the vertices into two children.
142 // Do these again to the children, so there are 4 grandchildren with 2 vertices for each.
143 // Use the copy constructor to generate a copy and compare with the original one.
147 for(size_t i
= 0; i
< 8; i
++)
151 subgraph_t::vertex_iterator vi_start
, vi
, vi_end
, vj_start
, vj
, vj_end
;
152 for(tie(vi
, vi_end
) = vertices(g1
); vi
!= vi_end
; ++vi
)
154 for(tie(vj
, vj_end
) = vertices(g1
); vj
!= vj_end
; ++vj
)
158 add_edge(*vi
, *vj
, g1
);
162 tie(vi_start
, vi_end
) = vertices(g1
);
164 for(size_t i
= 0; i
< 4; i
++)
168 g1
.create_subgraph(vi_start
, vi
);
169 g1
.create_subgraph(++vi
, vi_end
);
170 subgraph_t::children_iterator gi1
, gi2
;
171 gi2
= g1
.children().first
;
173 tie(vi_start
, vi_end
) = vertices(*gi1
);
175 tie(vj_start
, vj_end
) = vertices(*gi2
);
177 for(size_t i
= 0; i
< 2; i
++)
182 (*gi1
).create_subgraph(vi_start
, vi
);
183 (*gi1
).create_subgraph(++vi
, vi_end
);
184 (*gi2
).create_subgraph(vj_start
, vj
);
185 (*gi2
).create_subgraph(++vj
, vj_end
);
190 // Bootstrap the test_graph framework.
191 // TODO: Subgraph is fundamentally broken for property types.
192 // TODO: Under construction.
194 using namespace boost
;
195 typedef property
<edge_index_t
, size_t, EdgeBundle
> EdgeProp
;
196 typedef adjacency_list
<vecS
, vecS
, directedS
, VertexBundle
, EdgeProp
> BaseGraph
;
197 typedef subgraph
<BaseGraph
> Graph
;
198 typedef graph_traits
<Graph
>::vertex_descriptor Vertex
;
200 Vertex v
= add_vertex(g
);
202 typedef property_map
<Graph
, int VertexBundle::*>::type BundleMap
;
203 BundleMap map
= get(&VertexBundle::value
, g
);
206 // BOOST_ASSERT(get(map, v) == 5);