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
17using namespace boost;
18
19struct node
20{
21 int color;
22};
23
24struct arc
25{
26 int weight;
27};
28typedef property< edge_index_t, std::size_t, arc > arc_prop;
29
30typedef adjacency_list< vecS, vecS, bidirectionalS, node, arc_prop > Graph;
31
32typedef subgraph< Graph > Subgraph;
33typedef graph_traits< Subgraph >::vertex_descriptor Vertex;
34typedef graph_traits< Subgraph >::edge_descriptor Edge;
35typedef graph_traits< Subgraph >::vertex_iterator VertexIter;
36typedef graph_traits< Subgraph >::edge_iterator EdgeIter;
37
38int 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

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