1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Copyright 2009 Trustees of Indiana University.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
5 //
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
10 #include <iostream>
11 #include <vector>
12
13 #include <boost/foreach.hpp>
14 #include <boost/graph/adjacency_list.hpp>
15 #include <boost/graph/graph_utility.hpp>
16 #include <boost/graph/incremental_components.hpp>
17 #include <boost/pending/disjoint_sets.hpp>
18
19 /*
20
21 This example shows how to use the disjoint set data structure
22 to compute the connected components of an undirected, changing
23 graph.
24
25 Sample output:
26
27 An undirected graph:
28 0 <--> 1 4
29 1 <--> 0 4
30 2 <--> 5
31 3 <-->
32 4 <--> 1 0
33 5 <--> 2
34
35 representative[0] = 1
36 representative[1] = 1
37 representative[2] = 5
38 representative[3] = 3
39 representative[4] = 1
40 representative[5] = 5
41
42 component 0 contains: 4 1 0
43 component 1 contains: 3
44 component 2 contains: 5 2
45
46 */
47
48 using namespace boost;
49
main(int argc,char * argv[])50 int main(int argc, char* argv[])
51 {
52 typedef adjacency_list< vecS, vecS, undirectedS > Graph;
53 typedef graph_traits< Graph >::vertex_descriptor Vertex;
54 typedef graph_traits< Graph >::vertices_size_type VertexIndex;
55
56 const int VERTEX_COUNT = 6;
57 Graph graph(VERTEX_COUNT);
58
59 std::vector< VertexIndex > rank(num_vertices(graph));
60 std::vector< Vertex > parent(num_vertices(graph));
61
62 typedef VertexIndex* Rank;
63 typedef Vertex* Parent;
64
65 disjoint_sets< Rank, Parent > ds(&rank[0], &parent[0]);
66
67 initialize_incremental_components(graph, ds);
68 incremental_components(graph, ds);
69
70 graph_traits< Graph >::edge_descriptor edge;
71 bool flag;
72
73 boost::tie(edge, flag) = add_edge(0, 1, graph);
74 ds.union_set(0, 1);
75
76 boost::tie(edge, flag) = add_edge(1, 4, graph);
77 ds.union_set(1, 4);
78
79 boost::tie(edge, flag) = add_edge(4, 0, graph);
80 ds.union_set(4, 0);
81
82 boost::tie(edge, flag) = add_edge(2, 5, graph);
83 ds.union_set(2, 5);
84
85 std::cout << "An undirected graph:" << std::endl;
86 print_graph(graph, get(boost::vertex_index, graph));
87 std::cout << std::endl;
88
89 BOOST_FOREACH (Vertex current_vertex, vertices(graph))
90 {
91 std::cout << "representative[" << current_vertex
92 << "] = " << ds.find_set(current_vertex) << std::endl;
93 }
94
95 std::cout << std::endl;
96
97 typedef component_index< VertexIndex > Components;
98
99 // NOTE: Because we're using vecS for the graph type, we're
100 // effectively using identity_property_map for a vertex index map.
101 // If we were to use listS instead, the index map would need to be
102 // explicitly passed to the component_index constructor.
103 Components components(parent.begin(), parent.end());
104
105 // Iterate through the component indices
106 BOOST_FOREACH (VertexIndex current_index, components)
107 {
108 std::cout << "component " << current_index << " contains: ";
109
110 // Iterate through the child vertex indices for [current_index]
111 BOOST_FOREACH (VertexIndex child_index, components[current_index])
112 {
113 std::cout << child_index << " ";
114 }
115
116 std::cout << std::endl;
117 }
118
119 return (0);
120 }
121