]>
Commit | Line | Data |
---|---|---|
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 |