source: NonGTP/Boost/boost/graph/connected_components.hpp @ 857

Revision 857, 3.7 KB checked in by igarcia, 19 years ago (diff)
Line 
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
21namespace 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
Note: See TracBrowser for help on using the repository browser.