diff -r 666f914201fb -r 2fe1408b6811 epoc32/include/stdapis/boost/graph/connected_components.hpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/epoc32/include/stdapis/boost/graph/connected_components.hpp Tue Mar 16 16:12:26 2010 +0000 @@ -0,0 +1,101 @@ +// +//======================================================================= +// Copyright 1997-2001 University of Notre Dame. +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +//======================================================================= +// +#ifndef BOOST_GRAPH_CONNECTED_COMPONENTS_HPP +#define BOOST_GRAPH_CONNECTED_COMPONENTS_HPP + +#include +#include +#include +#include + +#include + +namespace boost { + + namespace detail { + + // This visitor is used both in the connected_components algorithm + // and in the kosaraju strong components algorithm during the + // second DFS traversal. + template + class components_recorder : public dfs_visitor<> + { + typedef typename property_traits::value_type comp_type; + public: + components_recorder(ComponentsMap c, + comp_type& c_count) + : m_component(c), m_count(c_count) {} + + template + void start_vertex(Vertex, Graph&) { + if (m_count == (std::numeric_limits::max)()) + m_count = 0; // start counting components at zero + else + ++m_count; + } + template + void discover_vertex(Vertex u, Graph&) { + put(m_component, u, m_count); + } + protected: + ComponentsMap m_component; + comp_type& m_count; + }; + + } // namespace detail + + // This function computes the connected components of an undirected + // graph using a single application of depth first search. + + template + inline typename property_traits::value_type + connected_components(const Graph& g, ComponentMap c, + const bgl_named_params& params) + { + if (num_vertices(g) == 0) return 0; + + typedef typename graph_traits::vertex_descriptor Vertex; + function_requires< WritablePropertyMapConcept >(); + typedef typename boost::graph_traits::directed_category directed; + BOOST_STATIC_ASSERT((boost::is_same::value)); + + typedef typename property_traits::value_type comp_type; + // c_count initialized to "nil" (with nil represented by (max)()) + comp_type c_count((std::numeric_limits::max)()); + detail::components_recorder vis(c, c_count); + depth_first_search(g, params.visitor(vis)); + return c_count + 1; + } + + template + inline typename property_traits::value_type + connected_components(const Graph& g, ComponentMap c) + { + if (num_vertices(g) == 0) return 0; + + typedef typename graph_traits::vertex_descriptor Vertex; + function_requires< WritablePropertyMapConcept >(); + typedef typename boost::graph_traits::directed_category directed; + BOOST_STATIC_ASSERT((boost::is_same::value)); + + typedef typename property_traits::value_type comp_type; + // c_count initialized to "nil" (with nil represented by (max)()) + comp_type c_count((std::numeric_limits::max)()); + detail::components_recorder vis(c, c_count); + depth_first_search(g, visitor(vis)); + return c_count + 1; + } + + +} // namespace boost + + +#endif // BOOST_GRAPH_CONNECTED_COMPONENTS_HPP