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(a&: Qlocation[heap_first], b&: 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(a&: Qlocation[drifter], b&: 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(a&: Qlocation[child_location], b&: 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 |
317 | |