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: bfs_king_visitor(OutputIterator * iter,Buffer * b,Compare compare,PseudoDegreeMap deg,std::vector<int> loc,VecMap color,VertexIndexMap vertices)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> finish_vertex(Vertex,Graph & g)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> examine_vertex(Vertex u,const 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> percolate_down(int offset)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> percolate_up(int vertex,int offset)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 king_ordering(const Graph & G,OutputIterator permutation)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