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