1 // (C) Copyright Jeremy Siek 2004
2 // (C) Copyright Andrew Sutton 2009
3 // Distributed under the Boost Software License, Version 1.0. (See
4 // accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6
7 #include <set>
8
9 #include <boost/random/mersenne_twister.hpp>
10
11 #include <boost/graph/adjacency_list.hpp>
12 #include <boost/graph/subgraph.hpp>
13 #include <boost/graph/random.hpp>
14 #include "graph_test.hpp"
15 #include <boost/graph/iteration_macros.hpp>
16
17 using namespace boost;
18
19 struct node
20 {
21 int color;
22 };
23
24 struct arc
25 {
26 int weight;
27 };
28 typedef property< edge_index_t, std::size_t, arc > arc_prop;
29
30 typedef adjacency_list< vecS, vecS, bidirectionalS, node, arc_prop > Graph;
31
32 typedef subgraph< Graph > Subgraph;
33 typedef graph_traits< Subgraph >::vertex_descriptor Vertex;
34 typedef graph_traits< Subgraph >::edge_descriptor Edge;
35 typedef graph_traits< Subgraph >::vertex_iterator VertexIter;
36 typedef graph_traits< Subgraph >::edge_iterator EdgeIter;
37
main(int,char * [])38 int main(int, char*[])
39 {
40 mt19937 gen;
41 for (int t = 0; t < 100; t += 5)
42 {
43 Subgraph g;
44 int N = t + 2;
45 std::vector< Vertex > vertex_set;
46 std::vector< std::pair< Vertex, Vertex > > edge_set;
47
48 generate_random_graph(g, N, N * 2, gen, std::back_inserter(vertex_set),
49 std::back_inserter(edge_set));
50 graph_test< Subgraph > gt;
51
52 gt.test_incidence_graph(vertex_set, edge_set, g);
53 gt.test_bidirectional_graph(vertex_set, edge_set, g);
54 gt.test_adjacency_graph(vertex_set, edge_set, g);
55 gt.test_vertex_list_graph(vertex_set, g);
56 gt.test_edge_list_graph(vertex_set, edge_set, g);
57 gt.test_adjacency_matrix(vertex_set, edge_set, g);
58
59 std::vector< Vertex > sub_vertex_set;
60 std::vector< Vertex > sub_global_map;
61 std::vector< Vertex > global_sub_map(num_vertices(g));
62 std::vector< std::pair< Vertex, Vertex > > sub_edge_set;
63
64 Subgraph& g_s = g.create_subgraph();
65
66 const std::set< Vertex >::size_type Nsub = N / 2;
67
68 // Collect a set of random vertices to put in the subgraph
69 std::set< Vertex > verts;
70 while (verts.size() < Nsub)
71 verts.insert(random_vertex(g, gen));
72
73 for (std::set< Vertex >::iterator it = verts.begin(); it != verts.end();
74 ++it)
75 {
76 Vertex v_global = *it;
77 Vertex v = add_vertex(v_global, g_s);
78 sub_vertex_set.push_back(v);
79 sub_global_map.push_back(v_global);
80 global_sub_map[v_global] = v;
81 }
82
83 // compute induced edges
84 BGL_FORALL_EDGES(e, g, Subgraph)
85 if (container_contains(sub_global_map, source(e, g))
86 && container_contains(sub_global_map, target(e, g)))
87 sub_edge_set.push_back(std::make_pair(
88 global_sub_map[source(e, g)], global_sub_map[target(e, g)]));
89
90 gt.test_incidence_graph(sub_vertex_set, sub_edge_set, g_s);
91 gt.test_bidirectional_graph(sub_vertex_set, sub_edge_set, g_s);
92 gt.test_adjacency_graph(sub_vertex_set, sub_edge_set, g_s);
93 gt.test_vertex_list_graph(sub_vertex_set, g_s);
94 gt.test_edge_list_graph(sub_vertex_set, sub_edge_set, g_s);
95 gt.test_adjacency_matrix(sub_vertex_set, sub_edge_set, g_s);
96
97 if (num_vertices(g_s) == 0)
98 return 0;
99
100 // Test property maps for vertices.
101 typedef property_map< Subgraph, int node::* >::type ColorMap;
102 ColorMap colors = get(&node::color, g_s);
103 for (std::pair< VertexIter, VertexIter > r = vertices(g_s);
104 r.first != r.second; ++r.first)
105 colors[*r.first] = 0;
106
107 // Test property maps for edges.
108 typedef property_map< Subgraph, int arc::* >::type WeightMap;
109 WeightMap weights = get(&arc::weight, g_s);
110 for (std::pair< EdgeIter, EdgeIter > r = edges(g_s);
111 r.first != r.second; ++r.first)
112 {
113 weights[*r.first] = 12;
114 }
115
116 // A regression test: the copy constructor of subgraph did not
117 // copy one of the members, so local_edge->global_edge mapping
118 // was broken.
119 {
120 Subgraph g;
121 graph_traits< Graph >::vertex_descriptor v1, v2;
122 v1 = add_vertex(g);
123 v2 = add_vertex(g);
124 add_edge(v1, v2, g);
125
126 Subgraph sub
127 = g.create_subgraph(vertices(g).first, vertices(g).second);
128
129 graph_traits< Graph >::edge_iterator ei, ee;
130 for (boost::tie(ei, ee) = edges(sub); ei != ee; ++ei)
131 {
132 // This used to segfault.
133 get(&arc::weight, sub, *ei);
134 }
135 }
136 }
137 return boost::report_errors();
138 }
139