1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/connected_components.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,101 @@
     1.4 +//
     1.5 +//=======================================================================
     1.6 +// Copyright 1997-2001 University of Notre Dame.
     1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     1.8 +//
     1.9 +// Distributed under the Boost Software License, Version 1.0. (See
    1.10 +// accompanying file LICENSE_1_0.txt or copy at
    1.11 +// http://www.boost.org/LICENSE_1_0.txt)
    1.12 +//=======================================================================
    1.13 +//
    1.14 +#ifndef BOOST_GRAPH_CONNECTED_COMPONENTS_HPP
    1.15 +#define BOOST_GRAPH_CONNECTED_COMPONENTS_HPP
    1.16 +
    1.17 +#include <boost/config.hpp>
    1.18 +#include <boost/graph/depth_first_search.hpp>
    1.19 +#include <boost/graph/properties.hpp>
    1.20 +#include <boost/graph/graph_concepts.hpp>
    1.21 +
    1.22 +#include <boost/static_assert.hpp>
    1.23 +
    1.24 +namespace boost {
    1.25 +
    1.26 +  namespace detail {
    1.27 +
    1.28 +    // This visitor is used both in the connected_components algorithm
    1.29 +    // and in the kosaraju strong components algorithm during the
    1.30 +    // second DFS traversal.
    1.31 +    template <class ComponentsMap>
    1.32 +    class components_recorder : public dfs_visitor<>
    1.33 +    {
    1.34 +      typedef typename property_traits<ComponentsMap>::value_type comp_type;
    1.35 +    public:
    1.36 +      components_recorder(ComponentsMap c, 
    1.37 +                          comp_type& c_count)
    1.38 +        : m_component(c), m_count(c_count) {}
    1.39 +
    1.40 +      template <class Vertex, class Graph>
    1.41 +      void start_vertex(Vertex, Graph&) {
    1.42 +        if (m_count == (std::numeric_limits<comp_type>::max)())
    1.43 +          m_count = 0; // start counting components at zero
    1.44 +        else
    1.45 +          ++m_count;
    1.46 +      }
    1.47 +      template <class Vertex, class Graph>
    1.48 +      void discover_vertex(Vertex u, Graph&) {
    1.49 +        put(m_component, u, m_count);
    1.50 +      }
    1.51 +    protected:
    1.52 +      ComponentsMap m_component;
    1.53 +      comp_type& m_count;
    1.54 +    };
    1.55 +
    1.56 +  } // namespace detail
    1.57 +
    1.58 +  // This function computes the connected components of an undirected
    1.59 +  // graph using a single application of depth first search.
    1.60 +
    1.61 +  template <class Graph, class ComponentMap, class P, class T, class R>
    1.62 +  inline typename property_traits<ComponentMap>::value_type
    1.63 +  connected_components(const Graph& g, ComponentMap c, 
    1.64 +                       const bgl_named_params<P, T, R>& params)
    1.65 +  {
    1.66 +    if (num_vertices(g) == 0) return 0;
    1.67 +
    1.68 +    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    1.69 +    function_requires< WritablePropertyMapConcept<ComponentMap, Vertex> >();
    1.70 +    typedef typename boost::graph_traits<Graph>::directed_category directed;
    1.71 +    BOOST_STATIC_ASSERT((boost::is_same<directed, undirected_tag>::value));
    1.72 +
    1.73 +    typedef typename property_traits<ComponentMap>::value_type comp_type;
    1.74 +    // c_count initialized to "nil" (with nil represented by (max)())
    1.75 +    comp_type c_count((std::numeric_limits<comp_type>::max)());
    1.76 +    detail::components_recorder<ComponentMap> vis(c, c_count);
    1.77 +    depth_first_search(g, params.visitor(vis));
    1.78 +    return c_count + 1;
    1.79 +  }
    1.80 +
    1.81 +  template <class Graph, class ComponentMap>
    1.82 +  inline typename property_traits<ComponentMap>::value_type
    1.83 +  connected_components(const Graph& g, ComponentMap c)
    1.84 +  {
    1.85 +    if (num_vertices(g) == 0) return 0;
    1.86 +
    1.87 +    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    1.88 +    function_requires< WritablePropertyMapConcept<ComponentMap, Vertex> >();
    1.89 +    typedef typename boost::graph_traits<Graph>::directed_category directed;
    1.90 +    BOOST_STATIC_ASSERT((boost::is_same<directed, undirected_tag>::value));
    1.91 +
    1.92 +    typedef typename property_traits<ComponentMap>::value_type comp_type;
    1.93 +    // c_count initialized to "nil" (with nil represented by (max)())
    1.94 +    comp_type c_count((std::numeric_limits<comp_type>::max)());
    1.95 +    detail::components_recorder<ComponentMap> vis(c, c_count);
    1.96 +    depth_first_search(g, visitor(vis));
    1.97 +    return c_count + 1;
    1.98 +  }
    1.99 +
   1.100 +  
   1.101 +} // namespace boost
   1.102 +
   1.103 +
   1.104 +#endif // BOOST_GRAPH_CONNECTED_COMPONENTS_HPP