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: components_recorder(ComponentsPA c,comp_type & c_count,DFSVisitor v)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> start_vertex(Vertex u,Graph & g)39 void start_vertex(Vertex u, Graph& g) { 40 ++m_count; 41 DFSVisitor::start_vertex(u, g); 42 } 43 template <class Vertex, class Graph> discover_vertex(Vertex u,Graph & g)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: time_recorder(DiscoverTimeMap d,FinishTimeMap f,TimeT & t,DFSVisitor v)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> discover_vertex(Vertex u,Graph & g)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> finish_vertex(Vertex u,Graph & g)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> record_times(DiscoverTimeMap d,FinishTimeMap f,TimeT & t,DFSVisitor vis)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 build_components_header(Parent p,OutputIterator header,Integer num_nodes)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> push_front(Next next,T & head,V x)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 link_components(Parent1 component,Parent2 header,Integer num_nodes,Integer num_components)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 construct_component_index(IndexContainer & index,HeaderContainer & header)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 component_iterator()180 component_iterator() {} component_iterator(IndexIterator x,Integer i)181 component_iterator(IndexIterator x, Integer i) 182 : next(x), node(i) {} operator *() const183 Integer operator*() const { 184 return node; 185 } operator ++()186 self& operator++() { 187 node = next[node]; 188 return *this; 189 } 190 }; 191 192 template <class IndexIterator, class Integer, class Distance> 193 inline bool operator ==(const component_iterator<IndexIterator,Integer,Distance> & x,const component_iterator<IndexIterator,Integer,Distance> & y)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 209