Chris@16: //
Chris@16: //=======================================================================
Chris@16: // Copyright 1997-2001 University of Notre Dame.
Chris@16: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: //
Chris@16: #ifndef BOOST_GRAPH_CONNECTED_COMPONENTS_HPP
Chris@16: #define BOOST_GRAPH_CONNECTED_COMPONENTS_HPP
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/graph/depth_first_search.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: #include <boost/graph/graph_concepts.hpp>
Chris@16: #include <boost/graph/overloading.hpp>
Chris@16: #include <boost/static_assert.hpp>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     // This visitor is used both in the connected_components algorithm
Chris@16:     // and in the kosaraju strong components algorithm during the
Chris@16:     // second DFS traversal.
Chris@16:     template <class ComponentsMap>
Chris@16:     class components_recorder : public dfs_visitor<>
Chris@16:     {
Chris@16:       typedef typename property_traits<ComponentsMap>::value_type comp_type;
Chris@16:     public:
Chris@16:       components_recorder(ComponentsMap c, 
Chris@16:                           comp_type& c_count)
Chris@16:         : m_component(c), m_count(c_count) {}
Chris@16: 
Chris@16:       template <class Vertex, class Graph>
Chris@16:       void start_vertex(Vertex, Graph&) {
Chris@16:         if (m_count == (std::numeric_limits<comp_type>::max)())
Chris@16:           m_count = 0; // start counting components at zero
Chris@16:         else
Chris@16:           ++m_count;
Chris@16:       }
Chris@16:       template <class Vertex, class Graph>
Chris@16:       void discover_vertex(Vertex u, Graph&) {
Chris@16:         put(m_component, u, m_count);
Chris@16:       }
Chris@16:     protected:
Chris@16:       ComponentsMap m_component;
Chris@16:       comp_type& m_count;
Chris@16:     };
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   // This function computes the connected components of an undirected
Chris@16:   // graph using a single application of depth first search.
Chris@16: 
Chris@16:   template <class Graph, class ComponentMap, class P, class T, class R>
Chris@16:   inline typename property_traits<ComponentMap>::value_type
Chris@16:   connected_components(const Graph& g, ComponentMap c, 
Chris@16:                        const bgl_named_params<P, T, R>& params
Chris@16:                        BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
Chris@16:   {
Chris@16:     if (num_vertices(g) == 0) return 0;
Chris@16: 
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<ComponentMap, Vertex> ));
Chris@16:     typedef typename boost::graph_traits<Graph>::directed_category directed;
Chris@16:     BOOST_STATIC_ASSERT((boost::is_same<directed, undirected_tag>::value));
Chris@16: 
Chris@16:     typedef typename property_traits<ComponentMap>::value_type comp_type;
Chris@16:     // c_count initialized to "nil" (with nil represented by (max)())
Chris@16:     comp_type c_count((std::numeric_limits<comp_type>::max)());
Chris@16:     detail::components_recorder<ComponentMap> vis(c, c_count);
Chris@16:     depth_first_search(g, params.visitor(vis));
Chris@16:     return c_count + 1;
Chris@16:   }
Chris@16: 
Chris@16:   template <class Graph, class ComponentMap>
Chris@16:   inline typename property_traits<ComponentMap>::value_type
Chris@16:   connected_components(const Graph& g, ComponentMap c
Chris@16:                        BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
Chris@16:   {
Chris@16:     if (num_vertices(g) == 0) return 0;
Chris@16: 
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<ComponentMap, Vertex> ));
Chris@16:     // typedef typename boost::graph_traits<Graph>::directed_category directed;
Chris@16:     // BOOST_STATIC_ASSERT((boost::is_same<directed, undirected_tag>::value));
Chris@16: 
Chris@16:     typedef typename property_traits<ComponentMap>::value_type comp_type;
Chris@16:     // c_count initialized to "nil" (with nil represented by (max)())
Chris@16:     comp_type c_count((std::numeric_limits<comp_type>::max)());
Chris@16:     detail::components_recorder<ComponentMap> vis(c, c_count);
Chris@16:     depth_first_search(g, visitor(vis));
Chris@16:     return c_count + 1;
Chris@16:   }
Chris@16: 
Chris@16:   
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #ifdef BOOST_GRAPH_USE_MPI
Chris@16: #  include <boost/graph/distributed/connected_components.hpp>
Chris@16: #endif
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_CONNECTED_COMPONENTS_HPP