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