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>
21 #include <boost/core/lightweight_test.hpp>
22
23 using namespace boost;
24
25 typedef adjacency_list< vecS, vecS, undirectedS > VectorGraph;
26
27 typedef adjacency_list< listS, listS, undirectedS,
28 property< vertex_index_t, unsigned int > >
29 ListGraph;
30
test_graph(const Graph & graph)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;
40
41 typedef std::map< vertex_descriptor, vertices_size_type > RankMap;
42 typedef associative_property_map< RankMap > RankPropertyMap;
43
44 typedef std::vector< vertex_descriptor > ParentMap;
45 typedef iterator_property_map< typename ParentMap::iterator,
46 IndexPropertyMap, vertex_descriptor, vertex_descriptor& >
47 IndexParentMap;
48
49 RankMap rank_map;
50 RankPropertyMap rank_property_map(rank_map);
51
52 ParentMap parent_map(num_vertices(graph));
53 IndexParentMap index_parent_map(parent_map.begin());
54
55 // Create disjoint sets of vertices from the graph
56 disjoint_sets< RankPropertyMap, IndexParentMap > vertex_sets(
57 rank_property_map, index_parent_map);
58
59 initialize_incremental_components(graph, vertex_sets);
60 incremental_components(graph, vertex_sets);
61
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));
67
68 // Create a reverse-lookup map for vertex indices
69 std::vector< vertex_descriptor > reverse_index_map(num_vertices(graph));
70
71 BOOST_FOREACH (vertex_descriptor vertex, vertices(graph))
72 {
73 reverse_index_map[get(get(boost::vertex_index, graph), vertex)]
74 = vertex;
75 }
76
77 // Verify that components are really connected
78 BOOST_FOREACH (vertices_size_type component_index, vertex_components)
79 {
80
81 std::set< vertex_descriptor > component_vertices;
82
83 BOOST_FOREACH (
84 vertices_size_type child_index, vertex_components[component_index])
85 {
86
87 vertex_descriptor child_vertex = reverse_index_map[child_index];
88 component_vertices.insert(child_vertex);
89
90 } // foreach child_index
91
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 {
96
97 // Skip orphan vertices
98 if (out_degree(child_vertex, graph) == 0)
99 {
100 continue;
101 }
102
103 // Make sure at least one edge exists between [child_vertex] and
104 // another vertex in the component.
105 bool edge_exists = false;
106
107 BOOST_FOREACH (
108 edge_descriptor child_edge, out_edges(child_vertex, graph))
109 {
110
111 if (component_vertices.count(target(child_edge, graph)) > 0)
112 {
113 edge_exists = true;
114 break;
115 }
116
117 } // foreach child_edge
118
119 BOOST_TEST(edge_exists);
120
121 } // foreach child_vertex
122
123 } // foreach component_index
124
125 } // test_graph
126
main(int argc,char * argv[])127 int main(int argc, char* argv[])
128 {
129 std::size_t vertices_to_generate = 100, edges_to_generate = 50,
130 random_seed = time(0);
131
132 // Parse command-line arguments
133
134 if (argc > 1)
135 {
136 vertices_to_generate = lexical_cast< std::size_t >(argv[1]);
137 }
138
139 if (argc > 2)
140 {
141 edges_to_generate = lexical_cast< std::size_t >(argv[2]);
142 }
143
144 if (argc > 3)
145 {
146 random_seed = lexical_cast< std::size_t >(argv[3]);
147 }
148
149 minstd_rand generator(random_seed);
150
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);
155
156 test_graph(vector_graph);
157
158 ListGraph list_graph;
159 generate_random_graph(
160 list_graph, vertices_to_generate, edges_to_generate, generator, false);
161
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 }
169
170 test_graph(list_graph);
171
172 return boost::report_errors();
173 }
174