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 <boost/graph/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<
31 vecS, vecS, bidirectionalS,
32 node, arc_prop
33 > Graph;
34
35 typedef subgraph<Graph> Subgraph;
36 typedef graph_traits<Subgraph>::vertex_descriptor Vertex;
37 typedef graph_traits<Subgraph>::edge_descriptor Edge;
38 typedef graph_traits<Subgraph>::vertex_iterator VertexIter;
39 typedef graph_traits<Subgraph>::edge_iterator EdgeIter;
40
test_main(int,char * [])41 int test_main(int, char*[])
42 {
43 mt19937 gen;
44 for (int t = 0; t < 100; t += 5) {
45 Subgraph g;
46 int N = t + 2;
47 std::vector<Vertex> vertex_set;
48 std::vector< std::pair<Vertex, Vertex> > edge_set;
49
50 generate_random_graph(g, N, N * 2, gen,
51 std::back_inserter(vertex_set),
52 std::back_inserter(edge_set));
53 graph_test< Subgraph > gt;
54
55 gt.test_incidence_graph(vertex_set, edge_set, g);
56 gt.test_bidirectional_graph(vertex_set, edge_set, g);
57 gt.test_adjacency_graph(vertex_set, edge_set, g);
58 gt.test_vertex_list_graph(vertex_set, g);
59 gt.test_edge_list_graph(vertex_set, edge_set, g);
60 gt.test_adjacency_matrix(vertex_set, edge_set, g);
61
62 std::vector<Vertex> sub_vertex_set;
63 std::vector<Vertex> sub_global_map;
64 std::vector<Vertex> global_sub_map(num_vertices(g));
65 std::vector< std::pair<Vertex, Vertex> > sub_edge_set;
66
67 Subgraph& g_s = g.create_subgraph();
68
69 const std::set<Vertex>::size_type Nsub = N/2;
70
71 // Collect a set of random vertices to put in the subgraph
72 std::set<Vertex> verts;
73 while (verts.size() < Nsub)
74 verts.insert(random_vertex(g, gen));
75
76 for (std::set<Vertex>::iterator it = verts.begin();
77 it != verts.end(); ++it) {
78 Vertex v_global = *it;
79 Vertex v = add_vertex(v_global, g_s);
80 sub_vertex_set.push_back(v);
81 sub_global_map.push_back(v_global);
82 global_sub_map[v_global] = v;
83 }
84
85 // compute induced edges
86 BGL_FORALL_EDGES(e, g, Subgraph)
87 if (container_contains(sub_global_map, source(e, g))
88 && container_contains(sub_global_map, target(e, g)))
89 sub_edge_set.push_back(std::make_pair(global_sub_map[source(e, g)],
90 global_sub_map[target(e, g)]));
91
92 gt.test_incidence_graph(sub_vertex_set, sub_edge_set, g_s);
93 gt.test_bidirectional_graph(sub_vertex_set, sub_edge_set, g_s);
94 gt.test_adjacency_graph(sub_vertex_set, sub_edge_set, g_s);
95 gt.test_vertex_list_graph(sub_vertex_set, g_s);
96 gt.test_edge_list_graph(sub_vertex_set, sub_edge_set, g_s);
97 gt.test_adjacency_matrix(sub_vertex_set, sub_edge_set, g_s);
98
99 if (num_vertices(g_s) == 0)
100 return 0;
101
102 // Test property maps for vertices.
103 typedef property_map<Subgraph, int node::*>::type ColorMap;
104 ColorMap colors = get(&node::color, g_s);
105 for(std::pair<VertexIter, VertexIter> r = vertices(g_s); r.first != r.second; ++r.first)
106 colors[*r.first] = 0;
107
108 // Test property maps for edges.
109 typedef property_map<Subgraph, int arc::*>::type WeightMap;
110 WeightMap weights = get(&arc::weight, g_s);
111 for(std::pair<EdgeIter, EdgeIter> r = edges(g_s); r.first != r.second; ++r.first) {
112 weights[*r.first] = 12;
113 }
114
115 // A regression test: the copy constructor of subgraph did not
116 // copy one of the members, so local_edge->global_edge mapping
117 // was broken.
118 {
119 Subgraph g;
120 graph_traits<Graph>::vertex_descriptor v1, v2;
121 v1 = add_vertex(g);
122 v2 = add_vertex(g);
123 add_edge(v1, v2, g);
124
125 Subgraph sub = g.create_subgraph(vertices(g).first, vertices(g).second);
126
127 graph_traits<Graph>::edge_iterator ei, ee;
128 for (boost::tie(ei, ee) = edges(sub); ei != ee; ++ei) {
129 // This used to segfault.
130 get(&arc::weight, sub, *ei);
131 }
132 }
133
134 }
135 return 0;
136 }
137