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
24using namespace boost;
25
26typedef adjacency_list< vecS, vecS, undirectedS > VectorGraph;
27
28typedef adjacency_list< listS, listS, undirectedS,
29 property< vertex_index_t, unsigned int > >
30 ListGraph;
31
32template < 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
128int 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

source code of boost/libs/graph/test/incremental_components_test.cpp