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
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
14 #include <boost/config.hpp>
15 #include <boost/graph/detail/sparse_ordering.hpp>
16 #include <boost/graph/graph_utility.hpp>
19 King Algorithm for matrix reordering
24 template<typename OutputIterator, typename Buffer, typename Compare,
25 typename PseudoDegreeMap, typename VecMap, typename VertexIndexMap>
26 class bfs_king_visitor:public default_bfs_visitor
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) { }
35 template <typename Vertex, typename Graph>
36 void finish_vertex(Vertex, Graph& g) {
37 typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
40 typedef typename std::deque<Vertex>::reverse_iterator reverse_iterator;
42 reverse_iterator rend = Qptr->rend()-index_begin;
43 reverse_iterator rbegin = Qptr->rbegin();
46 //heap the vertices already there
47 std::make_heap(rbegin, rend, boost::bind<bool>(comp, _2, _1));
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;
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) {
63 put(degree, v, get(degree, v) - 1);
65 if (colors[get(vertex_map, v)] == 1) {
66 percolate_up<Vertex>(get(vertex_map, v), i);
70 colors[get(vertex_map, w)] = 0;
75 template <typename Vertex, typename Graph>
76 void examine_vertex(Vertex u, const Graph&) {
78 *(*permutation)++ = u;
79 index_begin = Qptr->size();
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;
91 //pop_heap functionality:
93 std::swap((*Qptr)[heap_last], (*Qptr)[heap_first]);
95 //swap in the location queue
96 std::swap(Qlocation[heap_first], Qlocation[heap_last]);
98 //set drifter, children
99 int drifter = heap_first;
100 int drifter_heap = Qptr->size() - drifter;
102 int right_child_heap = drifter_heap * 2 + 1;
103 int right_child = Qptr->size() - right_child_heap;
105 int left_child_heap = drifter_heap * 2;
106 int left_child = Qptr->size() - left_child_heap;
108 //check that we are staying in the heap
109 bool valid = (right_child < heap_last) ? false : true;
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;
115 while(valid && smallest_child < heap_last && comp((*Qptr)[drifter], (*Qptr)[smallest_child])){
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]);
121 //update the values, run again, as necessary
122 drifter = smallest_child;
123 drifter_heap = Qptr->size() - drifter;
125 right_child_heap = drifter_heap * 2 + 1;
126 right_child = Qptr->size() - right_child_heap;
128 left_child_heap = drifter_heap * 2;
129 left_child = Qptr->size() - left_child_heap;
131 valid = (right_child < heap_last) ? false : true;
133 smallest_child = (valid && get(degree, (*Qptr)[left_child]) > get(degree,(*Qptr)[right_child])) ?
134 right_child : left_child;
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){
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;
151 bool valid = (heap_parent_location != 0 && child_location > index_begin + offset &&
152 parent_location < Qptr->size());
154 while(valid && comp((*Qptr)[child_location], (*Qptr)[parent_location])){
157 std::swap((*Qptr)[child_location], (*Qptr)[parent_location]);
159 //swap in the location queue
160 std::swap(Qlocation[child_location], Qlocation[parent_location]);
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);
170 OutputIterator *permutation;
173 PseudoDegreeMap degree;
175 std::vector<int> Qlocation;
177 VertexIndexMap vertex_map;
181 } // namespace detail
184 template<class Graph, class OutputIterator, class ColorMap, class DegreeMap,
185 typename VertexIndexMap>
187 king_ordering(const Graph& g,
188 std::deque< typename graph_traits<Graph>::vertex_descriptor >
190 OutputIterator permutation,
191 ColorMap color, DegreeMap degree,
192 VertexIndexMap index_map)
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
205 std::vector<ds_type> pseudo_degree_vec(num_vertices(g));
206 PseudoDegreeMap pseudo_degree(pseudo_degree_vec.begin(), index_map);
208 typename graph_traits<Graph>::vertex_iterator ui, ui_end;
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());
217 Compare comp(pseudo_degree);
218 std::vector<int> colors(num_vertices(g));
220 for(vertices_size_type i = 0; i < num_vertices(g); i++)
223 std::vector<int> loc(num_vertices(g));
226 Visitor vis(&permutation, &Q, comp, pseudo_degree, loc, colors, index_map);
228 while( !vertex_queue.empty() ) {
229 Vertex s = vertex_queue.front();
230 vertex_queue.pop_front();
232 //call BFS with visitor
233 breadth_first_visit(g, s, Q, vis, color);
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>
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)
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,
257 template < class Graph, class OutputIterator,
258 class ColorMap, class DegreeMap, class VertexIndexMap>
260 king_ordering(const Graph& G, OutputIterator permutation,
261 ColorMap color, DegreeMap degree, VertexIndexMap index_map)
263 if (has_no_vertices(G))
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;
270 std::deque<Vertex> vertex_queue;
272 // Mark everything white
273 BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());
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);
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);
289 return king_ordering(G, vertex_queue, permutation, color, degree,
293 template<typename Graph, typename OutputIterator, typename VertexIndexMap>
295 king_ordering(const Graph& G, OutputIterator permutation,
296 VertexIndexMap index_map)
298 if (has_no_vertices(G))
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,
305 make_out_degree_map(G), index_map);
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)); }
316 #endif // BOOST_GRAPH_KING_HPP