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
22namespace 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

source code of boost/boost/graph/king_ordering.hpp