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