| //======================================================================= |
| // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
| // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| //======================================================================= |
| #include <boost/config.hpp> |
| #include <iostream> |
| #include <iterator> |
| #include <vector> |
| #include <algorithm> |
| #include <utility> |
| #include <boost/graph/edge_list.hpp> |
| #include <boost/graph/incremental_components.hpp> |
| #include <boost/pending/disjoint_sets.hpp> |
| #include <boost/utility.hpp> |
| #include <boost/graph/graph_utility.hpp> |
| |
| /* |
| |
| This example demonstrates the usage of the |
| connected_components_on_edgelist algorithm. This differs from the |
| connect_components algorithm in that the graph object |
| only needs to provide access to the "list" of edges (via the |
| edges() function). |
| |
| The example graphs come from "Introduction to |
| Algorithms", Cormen, Leiserson, and Rivest p. 87 (though we number |
| the vertices from zero instead of one). |
| |
| Sample output: |
| |
| An undirected graph (edge list): |
| (0,1) (1,4) (4,0) (2,5) |
| Total number of components: 3 |
| Vertex 0 is in the component who's representative is 1 |
| Vertex 1 is in the component who's representative is 1 |
| Vertex 2 is in the component who's representative is 5 |
| Vertex 3 is in the component who's representative is 3 |
| Vertex 4 is in the component who's representative is 1 |
| Vertex 5 is in the component who's representative is 5 |
| |
| component 0 contains: 4 1 0 |
| component 1 contains: 3 |
| component 2 contains: 5 2 |
| |
| */ |
| |
| |
| using namespace std; |
| using boost::tie; |
| |
| int main(int , char* []) |
| { |
| using namespace boost; |
| typedef int Index; // ID of a Vertex |
| typedef pair<Index,Index> Edge; |
| const int N = 6; |
| const int E = 4; |
| Edge edgelist[] = { Edge(0, 1), Edge(1, 4), Edge(4, 0), Edge(2, 5) }; |
| |
| |
| |
| edge_list<Edge*,Edge,ptrdiff_t,std::random_access_iterator_tag> g(edgelist, edgelist + E); |
| cout << "An undirected graph (edge list):" << endl; |
| print_edges(g, identity_property_map()); |
| cout << endl; |
| |
| disjoint_sets_with_storage<> ds(N); |
| incremental_components(g, ds); |
| |
| component_index<int> components(&ds.parents()[0], |
| &ds.parents()[0] + ds.parents().size()); |
| |
| cout << "Total number of components: " << components.size() << endl; |
| for (int k = 0; k != N; ++k) |
| cout << "Vertex " << k << " is in the component who's representative is " |
| << ds.find_set(k) << endl; |
| cout << endl; |
| |
| for (std::size_t i = 0; i < components.size(); ++i) { |
| cout << "component " << i << " contains: "; |
| component_index<int>::component_iterator |
| j = components[i].first, |
| jend = components[i].second; |
| for ( ; j != jend; ++j) |
| cout << *j << " "; |
| cout << endl; |
| } |
| |
| return 0; |
| } |