]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |