epoc32/include/stdapis/boost/graph/connected_components.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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 
    19 #include <boost/static_assert.hpp>
    20 
    21 namespace boost {
    22 
    23   namespace detail {
    24 
    25     // This visitor is used both in the connected_components algorithm
    26     // and in the kosaraju strong components algorithm during the
    27     // second DFS traversal.
    28     template <class ComponentsMap>
    29     class components_recorder : public dfs_visitor<>
    30     {
    31       typedef typename property_traits<ComponentsMap>::value_type comp_type;
    32     public:
    33       components_recorder(ComponentsMap c, 
    34                           comp_type& c_count)
    35         : m_component(c), m_count(c_count) {}
    36 
    37       template <class Vertex, class Graph>
    38       void start_vertex(Vertex, Graph&) {
    39         if (m_count == (std::numeric_limits<comp_type>::max)())
    40           m_count = 0; // start counting components at zero
    41         else
    42           ++m_count;
    43       }
    44       template <class Vertex, class Graph>
    45       void discover_vertex(Vertex u, Graph&) {
    46         put(m_component, u, m_count);
    47       }
    48     protected:
    49       ComponentsMap m_component;
    50       comp_type& m_count;
    51     };
    52 
    53   } // namespace detail
    54 
    55   // This function computes the connected components of an undirected
    56   // graph using a single application of depth first search.
    57 
    58   template <class Graph, class ComponentMap, class P, class T, class R>
    59   inline typename property_traits<ComponentMap>::value_type
    60   connected_components(const Graph& g, ComponentMap c, 
    61                        const bgl_named_params<P, T, R>& params)
    62   {
    63     if (num_vertices(g) == 0) return 0;
    64 
    65     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    66     function_requires< WritablePropertyMapConcept<ComponentMap, Vertex> >();
    67     typedef typename boost::graph_traits<Graph>::directed_category directed;
    68     BOOST_STATIC_ASSERT((boost::is_same<directed, undirected_tag>::value));
    69 
    70     typedef typename property_traits<ComponentMap>::value_type comp_type;
    71     // c_count initialized to "nil" (with nil represented by (max)())
    72     comp_type c_count((std::numeric_limits<comp_type>::max)());
    73     detail::components_recorder<ComponentMap> vis(c, c_count);
    74     depth_first_search(g, params.visitor(vis));
    75     return c_count + 1;
    76   }
    77 
    78   template <class Graph, class ComponentMap>
    79   inline typename property_traits<ComponentMap>::value_type
    80   connected_components(const Graph& g, ComponentMap c)
    81   {
    82     if (num_vertices(g) == 0) return 0;
    83 
    84     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    85     function_requires< WritablePropertyMapConcept<ComponentMap, Vertex> >();
    86     typedef typename boost::graph_traits<Graph>::directed_category directed;
    87     BOOST_STATIC_ASSERT((boost::is_same<directed, undirected_tag>::value));
    88 
    89     typedef typename property_traits<ComponentMap>::value_type comp_type;
    90     // c_count initialized to "nil" (with nil represented by (max)())
    91     comp_type c_count((std::numeric_limits<comp_type>::max)());
    92     detail::components_recorder<ComponentMap> vis(c, c_count);
    93     depth_first_search(g, visitor(vis));
    94     return c_count + 1;
    95   }
    96 
    97   
    98 } // namespace boost
    99 
   100 
   101 #endif // BOOST_GRAPH_CONNECTED_COMPONENTS_HPP