1 //=======================================================================
2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
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
11 #include <iostream>
12 #include <vector>
13
14 #include <boost/foreach.hpp>
15 #include <boost/graph/adjacency_list.hpp>
16 #include <boost/graph/incremental_components.hpp>
17 #include <boost/pending/disjoint_sets.hpp>
18
19 using namespace boost;
20
main(int argc,char * argv[])21 int main(int argc, char* argv[])
22 {
23 typedef adjacency_list< vecS, vecS, undirectedS > Graph;
24 typedef graph_traits< Graph >::vertex_descriptor Vertex;
25 // typedef graph_traits<Graph>::edge_descriptor Edge;
26 typedef graph_traits< Graph >::vertices_size_type VertexIndex;
27
28 // Create a graph
29 const int VERTEX_COUNT = 6;
30 Graph graph(VERTEX_COUNT);
31
32 add_edge(0, 1, graph);
33 add_edge(1, 4, graph);
34
35 // reate the disjoint-sets object, which requires rank and parent
36 // vertex properties.
37 std::vector< Vertex > rank(num_vertices(graph));
38 std::vector< Vertex > parent(num_vertices(graph));
39
40 typedef VertexIndex* Rank;
41 typedef Vertex* Parent;
42 disjoint_sets< Rank, Parent > ds(&rank[0], &parent[0]);
43
44 // Determine the connected components, storing the results in the
45 // disjoint-sets object.
46 initialize_incremental_components(graph, ds);
47 incremental_components(graph, ds);
48
49 // Add a couple more edges and update the disjoint-sets
50 add_edge(4, 0, graph);
51 add_edge(2, 5, graph);
52
53 ds.union_set(4, 0);
54 ds.union_set(2, 5);
55
56 BOOST_FOREACH (Vertex current_vertex, vertices(graph))
57 {
58 std::cout << "representative[" << current_vertex
59 << "] = " << ds.find_set(current_vertex) << std::endl;
60 }
61
62 std::cout << std::endl;
63
64 // Generate component index. NOTE: We would need to pass in a vertex
65 // index map into the component_index constructor if our graph type
66 // used listS instead of vecS (identity_property_map is used by
67 // default).
68 typedef component_index< VertexIndex > Components;
69 Components components(parent.begin(), parent.end());
70
71 // Iterate through the component indices
72 BOOST_FOREACH (VertexIndex component_index, components)
73 {
74 std::cout << "component " << component_index << " contains: ";
75
76 // Iterate through the child vertex indices for [component_index]
77 BOOST_FOREACH (VertexIndex child_index, components[component_index])
78 {
79 std::cout << child_index << " ";
80 }
81
82 std::cout << std::endl;
83 }
84
85 return (0);
86 }
87