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: components_recorder(ComponentsMap c,comp_type & c_count)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> start_vertex(Vertex,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> discover_vertex(Vertex u,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 connected_components(const Graph & g,ComponentMap c,const bgl_named_params<P,T,R> & params BOOST_GRAPH_ENABLE_IF_MODELS_PARM (Graph,vertex_list_graph_tag))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 connected_components(const Graph & g,ComponentMap c BOOST_GRAPH_ENABLE_IF_MODELS_PARM (Graph,vertex_list_graph_tag))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