1 | // |
2 | //======================================================================= |
3 | // Copyright 1997-2001 University of Notre Dame. |
4 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
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 | #ifndef BOOST_GRAPH_CONNECTED_COMPONENTS_HPP |
12 | #define BOOST_GRAPH_CONNECTED_COMPONENTS_HPP |
13 | |
14 | #include <boost/config.hpp> |
15 | #include <boost/graph/depth_first_search.hpp> |
16 | #include <boost/graph/properties.hpp> |
17 | #include <boost/graph/graph_concepts.hpp> |
18 | #include <boost/graph/overloading.hpp> |
19 | #include <boost/static_assert.hpp> |
20 | #include <boost/concept/assert.hpp> |
21 | |
22 | namespace boost { |
23 | |
24 | namespace detail { |
25 | |
26 | // This visitor is used both in the connected_components algorithm |
27 | // and in the kosaraju strong components algorithm during the |
28 | // second DFS traversal. |
29 | template <class ComponentsMap> |
30 | class components_recorder : public dfs_visitor<> |
31 | { |
32 | typedef typename property_traits<ComponentsMap>::value_type comp_type; |
33 | public: |
34 | components_recorder(ComponentsMap c, |
35 | comp_type& c_count) |
36 | : m_component(c), m_count(c_count) {} |
37 | |
38 | template <class Vertex, class Graph> |
39 | void start_vertex(Vertex, Graph&) { |
40 | if (m_count == (std::numeric_limits<comp_type>::max)()) |
41 | m_count = 0; // start counting components at zero |
42 | else |
43 | ++m_count; |
44 | } |
45 | template <class Vertex, class Graph> |
46 | void discover_vertex(Vertex u, Graph&) { |
47 | put(m_component, u, m_count); |
48 | } |
49 | protected: |
50 | ComponentsMap m_component; |
51 | comp_type& m_count; |
52 | }; |
53 | |
54 | } // namespace detail |
55 | |
56 | // This function computes the connected components of an undirected |
57 | // graph using a single application of depth first search. |
58 | |
59 | template <class Graph, class ComponentMap, class P, class T, class R> |
60 | inline typename property_traits<ComponentMap>::value_type |
61 | connected_components(const Graph& g, ComponentMap c, |
62 | const bgl_named_params<P, T, R>& params |
63 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag)) |
64 | { |
65 | if (num_vertices(g) == 0) return 0; |
66 | |
67 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
68 | BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<ComponentMap, Vertex> )); |
69 | typedef typename boost::graph_traits<Graph>::directed_category directed; |
70 | BOOST_STATIC_ASSERT((boost::is_same<directed, undirected_tag>::value)); |
71 | |
72 | typedef typename property_traits<ComponentMap>::value_type comp_type; |
73 | // c_count initialized to "nil" (with nil represented by (max)()) |
74 | comp_type c_count((std::numeric_limits<comp_type>::max)()); |
75 | detail::components_recorder<ComponentMap> vis(c, c_count); |
76 | depth_first_search(g, params.visitor(vis)); |
77 | return c_count + 1; |
78 | } |
79 | |
80 | template <class Graph, class ComponentMap> |
81 | inline typename property_traits<ComponentMap>::value_type |
82 | connected_components(const Graph& g, ComponentMap c |
83 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag)) |
84 | { |
85 | if (num_vertices(g) == 0) return 0; |
86 | |
87 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
88 | BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<ComponentMap, Vertex> )); |
89 | // typedef typename boost::graph_traits<Graph>::directed_category directed; |
90 | // BOOST_STATIC_ASSERT((boost::is_same<directed, undirected_tag>::value)); |
91 | |
92 | typedef typename property_traits<ComponentMap>::value_type comp_type; |
93 | // c_count initialized to "nil" (with nil represented by (max)()) |
94 | comp_type c_count((std::numeric_limits<comp_type>::max)()); |
95 | detail::components_recorder<ComponentMap> vis(c, c_count); |
96 | depth_first_search(g, visitor(vis)); |
97 | return c_count + 1; |
98 | } |
99 | |
100 | |
101 | } // namespace boost |
102 | |
103 | #ifdef BOOST_GRAPH_USE_MPI |
104 | # include <boost/graph/distributed/connected_components.hpp> |
105 | #endif |
106 | |
107 | #endif // BOOST_GRAPH_CONNECTED_COMPONENTS_HPP |
108 | |