1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 #include <boost/config.hpp>
10 #include <iostream>
11 #include <iterator>
12 #include <vector>
13 #include <algorithm>
14 #include <utility>
15 #include <boost/graph/edge_list.hpp>
16 #include <boost/graph/incremental_components.hpp>
17 #include <boost/pending/disjoint_sets.hpp>
18 #include <boost/utility.hpp>
19 #include <boost/graph/graph_utility.hpp>
20
21 /*
22
23 This example demonstrates the usage of the
24 connected_components_on_edgelist algorithm. This differs from the
25 connect_components algorithm in that the graph object
26 only needs to provide access to the "list" of edges (via the
27 edges() function).
28
29 The example graphs come from "Introduction to
30 Algorithms", Cormen, Leiserson, and Rivest p. 87 (though we number
31 the vertices from zero instead of one).
32
33 Sample output:
34
35 An undirected graph (edge list):
36 (0,1) (1,4) (4,0) (2,5)
37 Total number of components: 3
38 Vertex 0 is in the component who's representative is 1
39 Vertex 1 is in the component who's representative is 1
40 Vertex 2 is in the component who's representative is 5
41 Vertex 3 is in the component who's representative is 3
42 Vertex 4 is in the component who's representative is 1
43 Vertex 5 is in the component who's representative is 5
44
45 component 0 contains: 4 1 0
46 component 1 contains: 3
47 component 2 contains: 5 2
48
49 */
50
51 using namespace std;
52 using boost::tie;
53
main(int,char * [])54 int main(int, char*[])
55 {
56 using namespace boost;
57 typedef int Index; // ID of a Vertex
58 typedef pair< Index, Index > Edge;
59 const int N = 6;
60 const int E = 4;
61 Edge edgelist[] = { Edge(0, 1), Edge(1, 4), Edge(4, 0), Edge(2, 5) };
62
63 edge_list< Edge*, Edge, ptrdiff_t, std::random_access_iterator_tag > g(
64 edgelist, edgelist + E);
65 cout << "An undirected graph (edge list):" << endl;
66 print_edges(g, identity_property_map());
67 cout << endl;
68
69 disjoint_sets_with_storage<> ds(N);
70 incremental_components(g, ds);
71
72 component_index< int > components(
73 &ds.parents()[0], &ds.parents()[0] + ds.parents().size());
74
75 cout << "Total number of components: " << components.size() << endl;
76 for (int k = 0; k != N; ++k)
77 cout << "Vertex " << k
78 << " is in the component who's representative is "
79 << ds.find_set(k) << endl;
80 cout << endl;
81
82 for (std::size_t i = 0; i < components.size(); ++i)
83 {
84 cout << "component " << i << " contains: ";
85 component_index< int >::component_iterator j = components[i].first,
86 jend = components[i].second;
87 for (; j != jend; ++j)
88 cout << *j << " ";
89 cout << endl;
90 }
91
92 return 0;
93 }
94