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 | |
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, V: N, E: N * 2, gen, vertex_out: std::back_inserter(x&: vertex_set), |
49 | edge_out: std::back_inserter(x&: 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(x: 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(u_global: v_global, g&: g_s); |
78 | sub_vertex_set.push_back(x: v); |
79 | sub_global_map.push_back(x: 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(c: sub_global_map, value: source(e, g)) |
86 | && container_contains(c: sub_global_map, value: target(e, g))) |
87 | sub_edge_set.push_back(x: std::make_pair( |
88 | x&: global_sub_map[source(e, g)], y&: global_sub_map[target(e, g)])); |
89 | |
90 | gt.test_incidence_graph(vertex_set: sub_vertex_set, edge_set: sub_edge_set, g: g_s); |
91 | gt.test_bidirectional_graph(vertex_set: sub_vertex_set, edge_set: sub_edge_set, g: g_s); |
92 | gt.test_adjacency_graph(vertex_set: sub_vertex_set, edge_set: sub_edge_set, g: g_s); |
93 | gt.test_vertex_list_graph(vertex_set: sub_vertex_set, g: g_s); |
94 | gt.test_edge_list_graph(vertex_set: sub_vertex_set, edge_set: sub_edge_set, g: g_s); |
95 | gt.test_adjacency_matrix(vertex_set: sub_vertex_set, edge_set: sub_edge_set, g: g_s); |
96 | |
97 | if (num_vertices(g: 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(p: &node::color, g&: g_s); |
103 | for (std::pair< VertexIter, VertexIter > r = vertices(g: 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(p: &arc::weight, g&: g_s); |
110 | for (std::pair< EdgeIter, EdgeIter > r = edges(g: 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(u: v1, v: v2, g); |
125 | |
126 | Subgraph sub |
127 | = g.create_subgraph(first: vertices(g).first, last: vertices(g).second); |
128 | |
129 | graph_traits< Graph >::edge_iterator ei, ee; |
130 | for (boost::tie(t0&: ei, t1&: ee) = edges(g: sub); ei != ee; ++ei) |
131 | { |
132 | // This used to segfault. |
133 | get(p: &arc::weight, g: sub, k: *ei); |
134 | } |
135 | } |
136 | } |
137 | return boost::report_errors(); |
138 | } |
139 | |