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 std::cout << "representative[" << current_vertex << "] = " <<
91 ds.find_set(current_vertex) << std::endl;
92 }
93
94 std::cout << std::endl;
95
96 typedef component_index<VertexIndex> Components;
97
98 // NOTE: Because we're using vecS for the graph type, we're
99 // effectively using identity_property_map for a vertex index map.
100 // If we were to use listS instead, the index map would need to be
101 // explicitly passed to the component_index constructor.
102 Components components(parent.begin(), parent.end());
103
104 // Iterate through the component indices
105 BOOST_FOREACH(VertexIndex current_index, components) {
106 std::cout << "component " << current_index << " contains: ";
107
108 // Iterate through the child vertex indices for [current_index]
109 BOOST_FOREACH(VertexIndex child_index,
110 components[current_index]) {
111 std::cout << child_index << " ";
112 }
113
114 std::cout << std::endl;
115 }
116
117 return (0);
118 }
119
120