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)
9 #include <boost/random/mersenne_twister.hpp>
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>
17 using namespace boost
;
28 typedef property
< edge_index_t
, std::size_t, arc
> arc_prop
;
30 typedef adjacency_list
< vecS
, vecS
, bidirectionalS
, node
, arc_prop
> Graph
;
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
;
38 int main(int, char*[])
41 for (int t
= 0; t
< 100; t
+= 5)
45 std::vector
< Vertex
> vertex_set
;
46 std::vector
< std::pair
< Vertex
, Vertex
> > edge_set
;
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
;
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
);
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
;
64 Subgraph
& g_s
= g
.create_subgraph();
66 const std::set
< Vertex
>::size_type Nsub
= N
/ 2;
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
));
73 for (std::set
< Vertex
>::iterator it
= verts
.begin(); it
!= verts
.end();
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
;
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
)]));
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
);
97 if (num_vertices(g_s
) == 0)
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;
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
)
113 weights
[*r
.first
] = 12;
116 // A regression test: the copy constructor of subgraph did not
117 // copy one of the members, so local_edge->global_edge mapping
121 graph_traits
< Graph
>::vertex_descriptor v1
, v2
;
127 = g
.create_subgraph(vertices(g
).first
, vertices(g
).second
);
129 graph_traits
< Graph
>::edge_iterator ei
, ee
;
130 for (boost::tie(ei
, ee
) = edges(sub
); ei
!= ee
; ++ei
)
132 // This used to segfault.
133 get(&arc::weight
, sub
, *ei
);
137 return boost::report_errors();