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