]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
10 | #include <boost/config.hpp> | |
11 | #include <iostream> | |
12 | #include <vector> | |
13 | #include <algorithm> | |
14 | #include <utility> | |
15 | #include <boost/graph/adjacency_list.hpp> | |
16 | #include <boost/graph/connected_components.hpp> | |
17 | ||
18 | /* | |
19 | ||
20 | This example demonstrates the usage of the connected_components | |
21 | algorithm on a undirected graph. The example graphs come from | |
22 | "Introduction to Algorithms", Cormen, Leiserson, and Rivest p. 87 | |
23 | (though we number the vertices from zero instead of one). | |
24 | ||
25 | Sample output: | |
26 | ||
27 | Total number of components: 3 | |
28 | Vertex 0 is in component 0 | |
29 | Vertex 1 is in component 0 | |
30 | Vertex 2 is in component 1 | |
31 | Vertex 3 is in component 2 | |
32 | Vertex 4 is in component 0 | |
33 | Vertex 5 is in component 1 | |
34 | ||
35 | */ | |
36 | ||
37 | using namespace std; | |
38 | ||
f67539c2 | 39 | int main(int, char*[]) |
7c673cae | 40 | { |
f67539c2 TL |
41 | using namespace boost; |
42 | { | |
43 | typedef adjacency_list< vecS, vecS, undirectedS > Graph; | |
44 | ||
45 | Graph G; | |
46 | add_edge(0, 1, G); | |
47 | add_edge(1, 4, G); | |
48 | add_edge(4, 0, G); | |
49 | add_edge(2, 5, G); | |
50 | ||
51 | std::vector< int > component(num_vertices(G)); | |
52 | int num = connected_components(G, &component[0]); | |
53 | ||
54 | std::vector< int >::size_type i; | |
55 | cout << "Total number of components: " << num << endl; | |
56 | for (i = 0; i != component.size(); ++i) | |
57 | cout << "Vertex " << i << " is in component " << component[i] | |
58 | << endl; | |
59 | cout << endl; | |
60 | } | |
61 | return 0; | |
7c673cae | 62 | } |