]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
3 | // Copyright 2004, 2005 Trustees of Indiana University | |
4 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, | |
5 | // Doug Gregor, D. Kevin McGrath | |
6 | // | |
7 | // Distributed under the Boost Software License, Version 1.0. (See | |
8 | // accompanying file LICENSE_1_0.txt or copy at | |
9 | // http://www.boost.org/LICENSE_1_0.txt) | |
10 | //=======================================================================// | |
11 | #ifndef BOOST_GRAPH_KING_HPP | |
12 | #define BOOST_GRAPH_KING_HPP | |
13 | ||
1e59de90 TL |
14 | #include <deque> |
15 | #include <vector> | |
16 | #include <algorithm> | |
7c673cae | 17 | #include <boost/config.hpp> |
1e59de90 TL |
18 | #include <boost/bind/bind.hpp> |
19 | #include <boost/tuple/tuple.hpp> | |
7c673cae FG |
20 | #include <boost/graph/detail/sparse_ordering.hpp> |
21 | #include <boost/graph/graph_utility.hpp> | |
22 | ||
23 | /* | |
24 | King Algorithm for matrix reordering | |
25 | */ | |
26 | ||
f67539c2 TL |
27 | namespace boost |
28 | { | |
29 | namespace detail | |
30 | { | |
31 | template < typename OutputIterator, typename Buffer, typename Compare, | |
32 | typename PseudoDegreeMap, typename VecMap, typename VertexIndexMap > | |
33 | class bfs_king_visitor : public default_bfs_visitor | |
7c673cae FG |
34 | { |
35 | public: | |
f67539c2 TL |
36 | bfs_king_visitor(OutputIterator* iter, Buffer* b, Compare compare, |
37 | PseudoDegreeMap deg, std::vector< int > loc, VecMap color, | |
38 | VertexIndexMap vertices) | |
39 | : permutation(iter) | |
40 | , Qptr(b) | |
41 | , degree(deg) | |
42 | , comp(compare) | |
43 | , Qlocation(loc) | |
44 | , colors(color) | |
45 | , vertex_map(vertices) | |
46 | { | |
7c673cae FG |
47 | } |
48 | ||
f67539c2 TL |
49 | template < typename Vertex, typename Graph > |
50 | void finish_vertex(Vertex, Graph& g) | |
51 | { | |
1e59de90 TL |
52 | using namespace boost::placeholders; |
53 | ||
f67539c2 TL |
54 | typename graph_traits< Graph >::out_edge_iterator ei, ei_end; |
55 | Vertex v, w; | |
56 | ||
57 | typedef typename std::deque< Vertex >::reverse_iterator | |
58 | reverse_iterator; | |
59 | ||
60 | reverse_iterator rend = Qptr->rend() - index_begin; | |
61 | reverse_iterator rbegin = Qptr->rbegin(); | |
62 | ||
63 | // heap the vertices already there | |
64 | std::make_heap(rbegin, rend, boost::bind< bool >(comp, _2, _1)); | |
65 | ||
66 | unsigned i = 0; | |
67 | ||
68 | for (i = index_begin; i != Qptr->size(); ++i) | |
69 | { | |
70 | colors[get(vertex_map, (*Qptr)[i])] = 1; | |
71 | Qlocation[get(vertex_map, (*Qptr)[i])] = i; | |
7c673cae | 72 | } |
f67539c2 TL |
73 | |
74 | i = 0; | |
75 | ||
76 | for (; rbegin != rend; rend--) | |
77 | { | |
78 | percolate_down< Vertex >(i); | |
79 | w = (*Qptr)[index_begin + i]; | |
80 | for (boost::tie(ei, ei_end) = out_edges(w, g); ei != ei_end; | |
81 | ++ei) | |
82 | { | |
83 | v = target(*ei, g); | |
84 | put(degree, v, get(degree, v) - 1); | |
85 | ||
86 | if (colors[get(vertex_map, v)] == 1) | |
87 | { | |
88 | percolate_up< Vertex >(get(vertex_map, v), i); | |
89 | } | |
90 | } | |
91 | ||
92 | colors[get(vertex_map, w)] = 0; | |
93 | i++; | |
94 | } | |
95 | } | |
96 | ||
97 | template < typename Vertex, typename Graph > | |
98 | void examine_vertex(Vertex u, const Graph&) | |
99 | { | |
100 | ||
101 | *(*permutation)++ = u; | |
102 | index_begin = Qptr->size(); | |
7c673cae | 103 | } |
f67539c2 | 104 | |
7c673cae | 105 | protected: |
f67539c2 TL |
106 | // this function replaces pop_heap, and tracks state information |
107 | template < typename Vertex > void percolate_down(int offset) | |
108 | { | |
109 | int heap_last = index_begin + offset; | |
110 | int heap_first = Qptr->size() - 1; | |
111 | ||
112 | // pop_heap functionality: | |
113 | // swap first, last | |
114 | std::swap((*Qptr)[heap_last], (*Qptr)[heap_first]); | |
115 | ||
116 | // swap in the location queue | |
117 | std::swap(Qlocation[heap_first], Qlocation[heap_last]); | |
118 | ||
119 | // set drifter, children | |
120 | int drifter = heap_first; | |
121 | int drifter_heap = Qptr->size() - drifter; | |
122 | ||
123 | int right_child_heap = drifter_heap * 2 + 1; | |
124 | int right_child = Qptr->size() - right_child_heap; | |
125 | ||
126 | int left_child_heap = drifter_heap * 2; | |
127 | int left_child = Qptr->size() - left_child_heap; | |
128 | ||
129 | // check that we are staying in the heap | |
130 | bool valid = (right_child < heap_last) ? false : true; | |
131 | ||
132 | // pick smallest child of drifter, and keep in mind there might only | |
133 | // be left child | |
134 | int smallest_child = (valid | |
135 | && get(degree, (*Qptr)[left_child]) | |
136 | > get(degree, (*Qptr)[right_child])) | |
137 | ? right_child | |
138 | : left_child; | |
139 | ||
140 | while (valid && smallest_child < heap_last | |
141 | && comp((*Qptr)[drifter], (*Qptr)[smallest_child])) | |
142 | { | |
7c673cae | 143 | |
f67539c2 TL |
144 | // if smallest child smaller than drifter, swap them |
145 | std::swap((*Qptr)[smallest_child], (*Qptr)[drifter]); | |
146 | std::swap(Qlocation[drifter], Qlocation[smallest_child]); | |
7c673cae | 147 | |
f67539c2 TL |
148 | // update the values, run again, as necessary |
149 | drifter = smallest_child; | |
150 | drifter_heap = Qptr->size() - drifter; | |
151 | ||
152 | right_child_heap = drifter_heap * 2 + 1; | |
153 | right_child = Qptr->size() - right_child_heap; | |
154 | ||
155 | left_child_heap = drifter_heap * 2; | |
156 | left_child = Qptr->size() - left_child_heap; | |
157 | ||
158 | valid = (right_child < heap_last) ? false : true; | |
159 | ||
160 | smallest_child = (valid | |
161 | && get(degree, (*Qptr)[left_child]) | |
162 | > get(degree, (*Qptr)[right_child])) | |
163 | ? right_child | |
164 | : left_child; | |
165 | } | |
7c673cae FG |
166 | } |
167 | ||
f67539c2 TL |
168 | // this is like percolate down, but we always compare against the |
169 | // parent, as there is only a single choice | |
170 | template < typename Vertex > void percolate_up(int vertex, int offset) | |
171 | { | |
172 | ||
173 | int child_location = Qlocation[vertex]; | |
174 | int heap_child_location = Qptr->size() - child_location; | |
175 | int heap_parent_location = (int)(heap_child_location / 2); | |
176 | unsigned parent_location = Qptr->size() - heap_parent_location; | |
177 | ||
178 | bool valid = (heap_parent_location != 0 | |
179 | && child_location > index_begin + offset | |
180 | && parent_location < Qptr->size()); | |
181 | ||
182 | while (valid | |
183 | && comp((*Qptr)[child_location], (*Qptr)[parent_location])) | |
184 | { | |
185 | ||
186 | // swap in the heap | |
187 | std::swap((*Qptr)[child_location], (*Qptr)[parent_location]); | |
188 | ||
189 | // swap in the location queue | |
190 | std::swap( | |
191 | Qlocation[child_location], Qlocation[parent_location]); | |
192 | ||
193 | child_location = parent_location; | |
194 | heap_child_location = heap_parent_location; | |
195 | heap_parent_location = (int)(heap_child_location / 2); | |
196 | parent_location = Qptr->size() - heap_parent_location; | |
197 | valid = (heap_parent_location != 0 | |
198 | && child_location > index_begin + offset); | |
199 | } | |
7c673cae | 200 | } |
f67539c2 TL |
201 | |
202 | OutputIterator* permutation; | |
203 | int index_begin; | |
204 | Buffer* Qptr; | |
205 | PseudoDegreeMap degree; | |
206 | Compare comp; | |
207 | std::vector< int > Qlocation; | |
208 | VecMap colors; | |
209 | VertexIndexMap vertex_map; | |
7c673cae | 210 | }; |
f67539c2 TL |
211 | |
212 | } // namespace detail | |
213 | ||
214 | template < class Graph, class OutputIterator, class ColorMap, class DegreeMap, | |
215 | typename VertexIndexMap > | |
216 | OutputIterator king_ordering(const Graph& g, | |
217 | std::deque< typename graph_traits< Graph >::vertex_descriptor > | |
218 | vertex_queue, | |
219 | OutputIterator permutation, ColorMap color, DegreeMap degree, | |
220 | VertexIndexMap index_map) | |
221 | { | |
222 | typedef typename property_traits< DegreeMap >::value_type ds_type; | |
223 | typedef typename property_traits< ColorMap >::value_type ColorValue; | |
224 | typedef color_traits< ColorValue > Color; | |
225 | typedef typename graph_traits< Graph >::vertex_descriptor Vertex; | |
226 | typedef iterator_property_map< typename std::vector< ds_type >::iterator, | |
227 | VertexIndexMap, ds_type, ds_type& > | |
228 | PseudoDegreeMap; | |
229 | typedef indirect_cmp< PseudoDegreeMap, std::less< ds_type > > Compare; | |
230 | typedef typename boost::sparse::sparse_ordering_queue< Vertex > queue; | |
231 | typedef typename detail::bfs_king_visitor< OutputIterator, queue, Compare, | |
232 | PseudoDegreeMap, std::vector< int >, VertexIndexMap > | |
233 | Visitor; | |
234 | typedef | |
235 | typename graph_traits< Graph >::vertices_size_type vertices_size_type; | |
236 | std::vector< ds_type > pseudo_degree_vec(num_vertices(g)); | |
7c673cae | 237 | PseudoDegreeMap pseudo_degree(pseudo_degree_vec.begin(), index_map); |
f67539c2 TL |
238 | |
239 | typename graph_traits< Graph >::vertex_iterator ui, ui_end; | |
7c673cae FG |
240 | queue Q; |
241 | // Copy degree to pseudo_degree | |
242 | // initialize the color map | |
f67539c2 TL |
243 | for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) |
244 | { | |
245 | put(pseudo_degree, *ui, get(degree, *ui)); | |
246 | put(color, *ui, Color::white()); | |
7c673cae | 247 | } |
f67539c2 | 248 | |
7c673cae | 249 | Compare comp(pseudo_degree); |
f67539c2 | 250 | std::vector< int > colors(num_vertices(g)); |
7c673cae | 251 | |
f67539c2 TL |
252 | for (vertices_size_type i = 0; i < num_vertices(g); i++) |
253 | colors[i] = 0; | |
7c673cae | 254 | |
f67539c2 | 255 | std::vector< int > loc(num_vertices(g)); |
7c673cae | 256 | |
f67539c2 | 257 | // create the visitor |
7c673cae | 258 | Visitor vis(&permutation, &Q, comp, pseudo_degree, loc, colors, index_map); |
f67539c2 TL |
259 | |
260 | while (!vertex_queue.empty()) | |
261 | { | |
262 | Vertex s = vertex_queue.front(); | |
263 | vertex_queue.pop_front(); | |
264 | ||
265 | // call BFS with visitor | |
266 | breadth_first_visit(g, s, Q, vis, color); | |
7c673cae FG |
267 | } |
268 | ||
269 | return permutation; | |
f67539c2 TL |
270 | } |
271 | ||
272 | // This is the case where only a single starting vertex is supplied. | |
273 | template < class Graph, class OutputIterator, class ColorMap, class DegreeMap, | |
274 | typename VertexIndexMap > | |
275 | OutputIterator king_ordering(const Graph& g, | |
276 | typename graph_traits< Graph >::vertex_descriptor s, | |
277 | OutputIterator permutation, ColorMap color, DegreeMap degree, | |
278 | VertexIndexMap index_map) | |
279 | { | |
280 | ||
281 | std::deque< typename graph_traits< Graph >::vertex_descriptor > | |
282 | vertex_queue; | |
283 | vertex_queue.push_front(s); | |
284 | return king_ordering( | |
285 | g, vertex_queue, permutation, color, degree, index_map); | |
286 | } | |
287 | ||
288 | template < class Graph, class OutputIterator, class ColorMap, class DegreeMap, | |
289 | class VertexIndexMap > | |
290 | OutputIterator king_ordering(const Graph& G, OutputIterator permutation, | |
291 | ColorMap color, DegreeMap degree, VertexIndexMap index_map) | |
292 | { | |
7c673cae | 293 | if (has_no_vertices(G)) |
f67539c2 | 294 | return permutation; |
7c673cae | 295 | |
f67539c2 TL |
296 | typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex; |
297 | typedef typename property_traits< ColorMap >::value_type ColorValue; | |
298 | typedef color_traits< ColorValue > Color; | |
7c673cae | 299 | |
f67539c2 | 300 | std::deque< Vertex > vertex_queue; |
7c673cae FG |
301 | |
302 | // Mark everything white | |
303 | BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white()); | |
304 | ||
f67539c2 TL |
305 | // Find one vertex from each connected component |
306 | BGL_FORALL_VERTICES_T(v, G, Graph) | |
307 | { | |
308 | if (get(color, v) == Color::white()) | |
309 | { | |
310 | depth_first_visit(G, v, dfs_visitor<>(), color); | |
311 | vertex_queue.push_back(v); | |
312 | } | |
7c673cae FG |
313 | } |
314 | ||
315 | // Find starting nodes for all vertices | |
316 | // TBD: How to do this with a directed graph? | |
f67539c2 | 317 | for (typename std::deque< Vertex >::iterator i = vertex_queue.begin(); |
7c673cae | 318 | i != vertex_queue.end(); ++i) |
f67539c2 TL |
319 | *i = find_starting_node(G, *i, color, degree); |
320 | ||
321 | return king_ordering( | |
322 | G, vertex_queue, permutation, color, degree, index_map); | |
323 | } | |
324 | ||
325 | template < typename Graph, typename OutputIterator, typename VertexIndexMap > | |
326 | OutputIterator king_ordering( | |
327 | const Graph& G, OutputIterator permutation, VertexIndexMap index_map) | |
328 | { | |
7c673cae | 329 | if (has_no_vertices(G)) |
f67539c2 | 330 | return permutation; |
7c673cae | 331 | |
f67539c2 TL |
332 | std::vector< default_color_type > colors(num_vertices(G)); |
333 | return king_ordering(G, permutation, | |
334 | make_iterator_property_map(&colors[0], index_map, colors[0]), | |
335 | make_out_degree_map(G), index_map); | |
336 | } | |
7c673cae | 337 | |
f67539c2 TL |
338 | template < typename Graph, typename OutputIterator > |
339 | inline OutputIterator king_ordering(const Graph& G, OutputIterator permutation) | |
340 | { | |
341 | return king_ordering(G, permutation, get(vertex_index, G)); | |
342 | } | |
7c673cae FG |
343 | |
344 | } // namespace boost | |
345 | ||
7c673cae | 346 | #endif // BOOST_GRAPH_KING_HPP |