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   namespace detail {
  21
  22     //=========================================================================
  23     // Implementation details of connected_components
  24
  25     // This is used both in the connected_components algorithm and in
  26     // the kosaraju strong components algorithm during the second DFS
  27     // traversal.
  28     template <class ComponentsPA, class DFSVisitor>
  29     class components_recorder : public DFSVisitor
  30     {
  31       typedef typename property_traits<ComponentsPA>::value_type comp_type;
  32     public:
  33       components_recorder(ComponentsPA c,
  34                           comp_type& c_count,
  35                           DFSVisitor v)
  36         : DFSVisitor(v), m_component(c), m_count(c_count) {}
  37
  38       template <class Vertex, class Graph>
  39       void start_vertex(Vertex u, Graph& g) {
  40         ++m_count;
  41         DFSVisitor::start_vertex(u, g);
  42       }
  43       template <class Vertex, class Graph>
  44       void discover_vertex(Vertex u, Graph& g) {
  45         put(m_component, u, m_count);
  46         DFSVisitor::discover_vertex(u, g);
  47       }
  48     protected:
  49       ComponentsPA m_component;
  50       comp_type& m_count;
  51     };
  52
  53     template <class DiscoverTimeMap, class FinishTimeMap, class TimeT,
  54       class DFSVisitor>
  55     class time_recorder : public DFSVisitor
  56     {
  57     public:
  58       time_recorder(DiscoverTimeMap d, FinishTimeMap f, TimeT& t, DFSVisitor v)
  59         : DFSVisitor(v), m_discover_time(d), m_finish_time(f), m_t(t) {}
  60
  61       template <class Vertex, class Graph>
  62       void discover_vertex(Vertex u, Graph& g) {
  63         put(m_discover_time, u, ++m_t);
  64         DFSVisitor::discover_vertex(u, g);
  65       }
  66       template <class Vertex, class Graph>
  67       void finish_vertex(Vertex u, Graph& g) {
  68         put(m_finish_time, u, ++m_t);
  69         DFSVisitor::discover_vertex(u, g);
  70       }
  71     protected:
  72       DiscoverTimeMap m_discover_time;
  73       FinishTimeMap m_finish_time;
  74       TimeT m_t;
  75     };
  76     template <class DiscoverTimeMap, class FinishTimeMap, class TimeT,
  77       class DFSVisitor>
  78     time_recorder<DiscoverTimeMap, FinishTimeMap, TimeT, DFSVisitor>
  79     record_times(DiscoverTimeMap d, FinishTimeMap f, TimeT& t, DFSVisitor vis)
  80     {
  81       return time_recorder<DiscoverTimeMap, FinishTimeMap, TimeT, DFSVisitor>
  82         (d, f, t, vis);
  83     }
  84
  85     //=========================================================================
  86     // Implementation detail of dynamic_components
  87
  88
  89     //-------------------------------------------------------------------------
  90     // Helper functions for the component_index class
  91
  92     // Record the representative vertices in the header array.
  93     // Representative vertices now point to the component number.
  94
  95     template <class Parent, class OutputIterator, class Integer>
  96     inline void
  97     build_components_header(Parent p,
  98                             OutputIterator header,
  99                             Integer num_nodes)
 100     {
 101       Parent component = p;
 102       Integer component_num = 0;
 103       for (Integer v = 0; v != num_nodes; ++v)
 104         if (p[v] == v) {
 105           *header++ = v;
 106           component[v] = component_num++;
 107         }
 108     }
 109
 110
 111     // Pushes x onto the front of the list. The list is represented in
 112     // an array.
 113     template <class Next, class T, class V>
 114     inline void push_front(Next next, T& head, V x)
 115     {
 116       T tmp = head;
 117       head = x;
 118       next[x] = tmp;
 119     }
 120
 121
 122     // Create a linked list of the vertices in each component
 123     // by reusing the representative array.
 124     template <class Parent1, class Parent2,
 125               class Integer>
 126     void
 127     link_components(Parent1 component, Parent2 header,
 128                     Integer num_nodes, Integer num_components)
 129     {
 130       // Make the non-representative vertices point to their component
 131       Parent1 representative = component;
 132       for (Integer v = 0; v != num_nodes; ++v)
 133         if (component[v] >= num_components || header[component[v]] != v)
 134           component[v] = component[representative[v]];
 135
 136       // initialize the "head" of the lists to "NULL"
 137       std::fill_n(header, num_components, num_nodes);
 138
 139       // Add each vertex to the linked list for its component
 140       Parent1 next = component;
 141       for (Integer k = 0; k != num_nodes; ++k)
 142         push_front(next, header[component[k]], k);
 143     }
 144
 145
 146
 147     template <class IndexContainer, class HeaderContainer>
 148     void
 149     construct_component_index(IndexContainer& index, HeaderContainer& header)
 150     {
 151       build_components_header(index.begin(),
 152                               std::back_inserter(header),
 153                               index.end() - index.begin());
 154
 155       link_components(index.begin(), header.begin(),
 156                       index.end() - index.begin(),
 157                       header.end() - header.begin());
 158     }
 159
 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>,
 166               Integer, 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)
 182         : next(x), node(i) {}
 183       Integer operator*() const {
 184         return node;
 185       }
 186       self& operator++() {
 187         node = next[node];
 188         return *this;
 189       }
 190     };
 191
 192     template <class IndexIterator, class Integer, class Distance>
 193     inline bool
 194     operator==(const component_iterator<IndexIterator, Integer, Distance>& x,
 195                const component_iterator<IndexIterator, Integer, Distance>& y)
 196     {
 197       return x.node == y.node;
 198     }
 199
 200   } // namespace detail
 201
 202 } // namespace detail
 203
 204 #if defined(__sgi) && !defined(__GNUC__)
 205 #pragma reset woff 1234
 206 #endif
 207
 208 #endif