1 | //======================================================================= |
2 | // Copyright 2009 Trustees of Indiana University. |
3 | // Authors: Michael Hansen, Andrew Lumsdaine |
4 | // |
5 | // Distributed under the Boost Software License, Version 1.0. (See |
6 | // accompanying file LICENSE_1_0.txt or copy at |
7 | // http://www.boost.org/LICENSE_1_0.txt) |
8 | //======================================================================= |
9 | |
10 | #include <iostream> |
11 | #include <map> |
12 | #include <set> |
13 | #include <ctime> |
14 | |
15 | #include <boost/foreach.hpp> |
16 | #include <boost/graph/adjacency_list.hpp> |
17 | #include <boost/graph/incremental_components.hpp> |
18 | #include <boost/graph/random.hpp> |
19 | #include <boost/lexical_cast.hpp> |
20 | #include <boost/property_map/property_map.hpp> |
21 | #include <boost/random.hpp> |
22 | #include <boost/core/lightweight_test.hpp> |
23 | |
24 | using namespace boost; |
25 | |
26 | typedef adjacency_list< vecS, vecS, undirectedS > VectorGraph; |
27 | |
28 | typedef adjacency_list< listS, listS, undirectedS, |
29 | property< vertex_index_t, unsigned int > > |
30 | ListGraph; |
31 | |
32 | template < typename Graph > void test_graph(const Graph& graph) |
33 | { |
34 | typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor; |
35 | typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor; |
36 | typedef |
37 | typename graph_traits< Graph >::vertices_size_type vertices_size_type; |
38 | |
39 | typedef |
40 | typename property_map< Graph, vertex_index_t >::type IndexPropertyMap; |
41 | |
42 | typedef std::map< vertex_descriptor, vertices_size_type > RankMap; |
43 | typedef associative_property_map< RankMap > RankPropertyMap; |
44 | |
45 | typedef std::vector< vertex_descriptor > ParentMap; |
46 | typedef iterator_property_map< typename ParentMap::iterator, |
47 | IndexPropertyMap, vertex_descriptor, vertex_descriptor& > |
48 | IndexParentMap; |
49 | |
50 | RankMap rank_map; |
51 | RankPropertyMap rank_property_map(rank_map); |
52 | |
53 | ParentMap parent_map(num_vertices(graph)); |
54 | IndexParentMap index_parent_map(parent_map.begin()); |
55 | |
56 | // Create disjoint sets of vertices from the graph |
57 | disjoint_sets< RankPropertyMap, IndexParentMap > vertex_sets( |
58 | rank_property_map, index_parent_map); |
59 | |
60 | initialize_incremental_components(graph, vertex_sets); |
61 | incremental_components(graph, vertex_sets); |
62 | |
63 | // Build component index from the graph's vertices, its index map, |
64 | // and the disjoint sets. |
65 | typedef component_index< vertices_size_type > Components; |
66 | Components vertex_components( |
67 | parent_map.begin(), parent_map.end(), get(boost::vertex_index, graph)); |
68 | |
69 | // Create a reverse-lookup map for vertex indices |
70 | std::vector< vertex_descriptor > reverse_index_map(num_vertices(graph)); |
71 | |
72 | BOOST_FOREACH (vertex_descriptor vertex, vertices(graph)) |
73 | { |
74 | reverse_index_map[get(get(boost::vertex_index, graph), vertex)] |
75 | = vertex; |
76 | } |
77 | |
78 | // Verify that components are really connected |
79 | BOOST_FOREACH (vertices_size_type component_index, vertex_components) |
80 | { |
81 | |
82 | std::set< vertex_descriptor > component_vertices; |
83 | |
84 | BOOST_FOREACH ( |
85 | vertices_size_type child_index, vertex_components[component_index]) |
86 | { |
87 | |
88 | vertex_descriptor child_vertex = reverse_index_map[child_index]; |
89 | component_vertices.insert(child_vertex); |
90 | |
91 | } // foreach child_index |
92 | |
93 | // Verify that children are connected to each other in some |
94 | // manner, but not to vertices outside their component. |
95 | BOOST_FOREACH (vertex_descriptor child_vertex, component_vertices) |
96 | { |
97 | |
98 | // Skip orphan vertices |
99 | if (out_degree(child_vertex, graph) == 0) |
100 | { |
101 | continue; |
102 | } |
103 | |
104 | // Make sure at least one edge exists between [child_vertex] and |
105 | // another vertex in the component. |
106 | bool edge_exists = false; |
107 | |
108 | BOOST_FOREACH ( |
109 | edge_descriptor child_edge, out_edges(child_vertex, graph)) |
110 | { |
111 | |
112 | if (component_vertices.count(target(child_edge, graph)) > 0) |
113 | { |
114 | edge_exists = true; |
115 | break; |
116 | } |
117 | |
118 | } // foreach child_edge |
119 | |
120 | BOOST_TEST(edge_exists); |
121 | |
122 | } // foreach child_vertex |
123 | |
124 | } // foreach component_index |
125 | |
126 | } // test_graph |
127 | |
128 | int main(int argc, char* argv[]) |
129 | { |
130 | std::size_t vertices_to_generate = 100, edges_to_generate = 50, |
131 | random_seed = std::time(timer: 0); |
132 | |
133 | // Parse command-line arguments |
134 | |
135 | if (argc > 1) |
136 | { |
137 | vertices_to_generate = lexical_cast< std::size_t >(arg: argv[1]); |
138 | } |
139 | |
140 | if (argc > 2) |
141 | { |
142 | edges_to_generate = lexical_cast< std::size_t >(arg: argv[2]); |
143 | } |
144 | |
145 | if (argc > 3) |
146 | { |
147 | random_seed = lexical_cast< std::size_t >(arg: argv[3]); |
148 | } |
149 | |
150 | minstd_rand generator(random_seed); |
151 | |
152 | // Generate random vector and list graphs |
153 | VectorGraph vector_graph; |
154 | generate_random_graph(g&: vector_graph, V: vertices_to_generate, E: edges_to_generate, |
155 | gen&: generator, allow_parallel: false); |
156 | |
157 | test_graph(graph: vector_graph); |
158 | |
159 | ListGraph list_graph; |
160 | generate_random_graph( |
161 | g&: list_graph, V: vertices_to_generate, E: edges_to_generate, gen&: generator, allow_parallel: false); |
162 | |
163 | // Assign indices to list_graph's vertices |
164 | graph_traits< ListGraph >::vertices_size_type index = 0; |
165 | BOOST_FOREACH (graph_traits< ListGraph >::vertex_descriptor vertex, |
166 | vertices(list_graph)) |
167 | { |
168 | put(pa: get(p: boost::vertex_index, g&: list_graph), k: vertex, v: index++); |
169 | } |
170 | |
171 | test_graph(graph: list_graph); |
172 | |
173 | return boost::report_errors(); |
174 | } |
175 | |