ceph/src/boost/boost/graph/detail/connected_components.hpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9 #ifndef BOOST_GRAPH_DETAIL_CONNECTED_COMPONENTS_HPP
  10 #define BOOST_GRAPH_DETAIL_CONNECTED_COMPONENTS_HPP
  11
  12 #if defined(__sgi) && !defined(__GNUC__)
  13 #pragma set woff 1234
  14 #endif
  15
  16 #include <boost/operators.hpp>
  17
  18 namespace boost
  19 {
  20
  21 namespace detail
  22 {
  23
  24     //=========================================================================
  25     // Implementation details of connected_components
  26
  27     // This is used both in the connected_components algorithm and in
  28     // the kosaraju strong components algorithm during the second DFS
  29     // traversal.
  30     template < class ComponentsPA, class DFSVisitor >
  31     class components_recorder : public DFSVisitor
  32     {
  33         typedef typename property_traits< ComponentsPA >::value_type comp_type;
  34
  35     public:
  36         components_recorder(ComponentsPA c, comp_type& c_count, DFSVisitor v)
  37         : DFSVisitor(v), m_component(c), m_count(c_count)
  38         {
  39         }
  40
  41         template < class Vertex, class Graph >
  42         void start_vertex(Vertex u, Graph& g)
  43         {
  44             ++m_count;
  45             DFSVisitor::start_vertex(u, g);
  46         }
  47         template < class Vertex, class Graph >
  48         void discover_vertex(Vertex u, Graph& g)
  49         {
  50             put(m_component, u, m_count);
  51             DFSVisitor::discover_vertex(u, g);
  52         }
  53
  54     protected:
  55         ComponentsPA m_component;
  56         comp_type& m_count;
  57     };
  58
  59     template < class DiscoverTimeMap, class FinishTimeMap, class TimeT,
  60         class DFSVisitor >
  61     class time_recorder : public DFSVisitor
  62     {
  63     public:
  64         time_recorder(
  65             DiscoverTimeMap d, FinishTimeMap f, TimeT& t, DFSVisitor v)
  66         : DFSVisitor(v), m_discover_time(d), m_finish_time(f), m_t(t)
  67         {
  68         }
  69
  70         template < class Vertex, class Graph >
  71         void discover_vertex(Vertex u, Graph& g)
  72         {
  73             put(m_discover_time, u, ++m_t);
  74             DFSVisitor::discover_vertex(u, g);
  75         }
  76         template < class Vertex, class Graph >
  77         void finish_vertex(Vertex u, Graph& g)
  78         {
  79             put(m_finish_time, u, ++m_t);
  80             DFSVisitor::discover_vertex(u, g);
  81         }
  82
  83     protected:
  84         DiscoverTimeMap m_discover_time;
  85         FinishTimeMap m_finish_time;
  86         TimeT m_t;
  87     };
  88     template < class DiscoverTimeMap, class FinishTimeMap, class TimeT,
  89         class DFSVisitor >
  90     time_recorder< DiscoverTimeMap, FinishTimeMap, TimeT, DFSVisitor >
  91     record_times(DiscoverTimeMap d, FinishTimeMap f, TimeT& t, DFSVisitor vis)
  92     {
  93         return time_recorder< DiscoverTimeMap, FinishTimeMap, TimeT,
  94             DFSVisitor >(d, f, t, vis);
  95     }
  96
  97     //=========================================================================
  98     // Implementation detail of dynamic_components
  99
 100     //-------------------------------------------------------------------------
 101     // Helper functions for the component_index class
 102
 103     // Record the representative vertices in the header array.
 104     // Representative vertices now point to the component number.
 105
 106     template < class Parent, class OutputIterator, class Integer >
 107     inline void build_components_header(
 108         Parent p, OutputIterator header, Integer num_nodes)
 109     {
 110         Parent component = p;
 111         Integer component_num = 0;
 112         for (Integer v = 0; v != num_nodes; ++v)
 113             if (p[v] == v)
 114             {
 115                 *header++ = v;
 116                 component[v] = component_num++;
 117             }
 118     }
 119
 120     // Pushes x onto the front of the list. The list is represented in
 121     // an array.
 122     template < class Next, class T, class V >
 123     inline void push_front(Next next, T& head, V x)
 124     {
 125         T tmp = head;
 126         head = x;
 127         next[x] = tmp;
 128     }
 129
 130     // Create a linked list of the vertices in each component
 131     // by reusing the representative array.
 132     template < class Parent1, class Parent2, class Integer >
 133     void link_components(Parent1 component, Parent2 header, Integer num_nodes,
 134         Integer num_components)
 135     {
 136         // Make the non-representative vertices point to their component
 137         Parent1 representative = component;
 138         for (Integer v = 0; v != num_nodes; ++v)
 139             if (component[v] >= num_components || header[component[v]] != v)
 140                 component[v] = component[representative[v]];
 141
 142         // initialize the "head" of the lists to "NULL"
 143         std::fill_n(header, num_components, num_nodes);
 144
 145         // Add each vertex to the linked list for its component
 146         Parent1 next = component;
 147         for (Integer k = 0; k != num_nodes; ++k)
 148             push_front(next, header[component[k]], k);
 149     }
 150
 151     template < class IndexContainer, class HeaderContainer >
 152     void construct_component_index(
 153         IndexContainer& index, HeaderContainer& header)
 154     {
 155         build_components_header(index.begin(), std::back_inserter(header),
 156             index.end() - index.begin());
 157
 158         link_components(index.begin(), header.begin(),
 159             index.end() - index.begin(), header.end() - header.begin());
 160     }
 161
 162     template < class IndexIterator, class Integer, class Distance >
 163     class component_iterator
 164     : boost::forward_iterator_helper<
 165           component_iterator< IndexIterator, Integer, Distance >, Integer,
 166           Distance, Integer*, Integer& >
 167     {
 168     public:
 169         typedef component_iterator self;
 170
 171         IndexIterator next;
 172         Integer node;
 173
 174         typedef std::forward_iterator_tag iterator_category;
 175         typedef Integer value_type;
 176         typedef Integer& reference;
 177         typedef Integer* pointer;
 178         typedef Distance difference_type;
 179
 180         component_iterator() {}
 181         component_iterator(IndexIterator x, Integer i) : next(x), node(i) {}
 182         Integer operator*() const { return node; }
 183         self& operator++()
 184         {
 185             node = next[node];
 186             return *this;
 187         }
 188     };
 189
 190     template < class IndexIterator, class Integer, class Distance >
 191     inline bool operator==(
 192         const component_iterator< IndexIterator, Integer, Distance >& x,
 193         const component_iterator< IndexIterator, Integer, Distance >& y)
 194     {
 195         return x.node == y.node;
 196     }
 197
 198 } // namespace detail
 199
 200 } // namespace detail
 201
 202 #if defined(__sgi) && !defined(__GNUC__)
 203 #pragma reset woff 1234
 204 #endif
 205
 206 #endif