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