1 // 2 //======================================================================= 3 // Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch) 4 // ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st) 5 // 6 // Distributed under the Boost Software License, Version 1.0. (See 7 // accompanying file LICENSE_1_0.txt or copy at 8 // http://www.boost.org/LICENSE_1_0.txt) 9 //======================================================================= 10 // 11 12 #ifndef BOOST_GRAPH_SLOAN_HPP 13 #define BOOST_GRAPH_SLOAN_HPP 14 15 #define WEIGHT1 1 //default weight for the distance in the Sloan algorithm 16 #define WEIGHT2 2 //default weight for the degree in the Sloan algorithm 17 18 #include <boost/config.hpp> 19 #include <vector> 20 #include <queue> 21 #include <algorithm> 22 #include <limits> 23 #include <boost/pending/queue.hpp> 24 #include <boost/graph/graph_traits.hpp> 25 #include <boost/graph/breadth_first_search.hpp> 26 #include <boost/graph/properties.hpp> 27 #include <boost/pending/indirect_cmp.hpp> 28 #include <boost/property_map/property_map.hpp> 29 #include <boost/graph/visitors.hpp> 30 #include <boost/graph/adjacency_list.hpp> 31 #include <boost/graph/cuthill_mckee_ordering.hpp> 32 33 34 //////////////////////////////////////////////////////////// 35 // 36 //Sloan-Algorithm for graph reordering 37 //(optimzes profile and wavefront, not primiraly bandwidth 38 // 39 //////////////////////////////////////////////////////////// 40 41 namespace boost { 42 43 ///////////////////////////////////////////////////////////////////////// 44 // Function that returns the maximum depth of 45 // a rooted level strucutre (RLS) 46 // 47 ///////////////////////////////////////////////////////////////////////// 48 template<class Distance> RLS_depth(Distance & d)49 typename Distance::value_type RLS_depth(Distance& d) 50 { 51 typename Distance::value_type h_s = 0; 52 typename Distance::iterator iter; 53 54 for (iter = d.begin(); iter != d.end(); ++iter) 55 { 56 if(*iter > h_s) 57 { 58 h_s = *iter; 59 } 60 } 61 62 return h_s; 63 } 64 65 66 67 ///////////////////////////////////////////////////////////////////////// 68 // Function that returns the width of the largest level of 69 // a rooted level strucutre (RLS) 70 // 71 ///////////////////////////////////////////////////////////////////////// 72 template<class Distance, class my_int> RLS_max_width(Distance & d,my_int depth)73 typename Distance::value_type RLS_max_width(Distance& d, my_int depth) 74 { 75 76 typedef typename Distance::value_type Degree; 77 78 //Searching for the maximum width of a level 79 std::vector<Degree> dummy_width(depth+1, 0); 80 typename std::vector<Degree>::iterator my_it; 81 typename Distance::iterator iter; 82 Degree w_max = 0; 83 84 for (iter = d.begin(); iter != d.end(); ++iter) 85 { 86 dummy_width[*iter]++; 87 } 88 89 for(my_it = dummy_width.begin(); my_it != dummy_width.end(); ++my_it) 90 { 91 if(*my_it > w_max) w_max = *my_it; 92 } 93 94 return w_max; 95 96 } 97 98 99 ///////////////////////////////////////////////////////////////////////// 100 // Function for finding a good starting node for Sloan algorithm 101 // 102 // This is to find a good starting node. "good" is in the sense 103 // of the ordering generated. 104 ///////////////////////////////////////////////////////////////////////// 105 template <class Graph, class ColorMap, class DegreeMap> 106 typename graph_traits<Graph>::vertex_descriptor sloan_start_end_vertices(Graph & G,typename graph_traits<Graph>::vertex_descriptor & s,ColorMap color,DegreeMap degree)107 sloan_start_end_vertices(Graph& G, 108 typename graph_traits<Graph>::vertex_descriptor &s, 109 ColorMap color, 110 DegreeMap degree) 111 { 112 typedef typename property_traits<DegreeMap>::value_type Degree; 113 typedef typename graph_traits<Graph>::vertex_descriptor Vertex; 114 typedef typename std::vector< typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter; 115 typedef typename graph_traits<Graph>::vertices_size_type size_type; 116 117 typedef typename property_map<Graph, vertex_index_t>::const_type VertexID; 118 119 s = *(vertices(G).first); 120 Vertex e = s; 121 Vertex i; 122 Degree my_degree = get(degree, s ); 123 Degree dummy, h_i, h_s, w_i, w_e; 124 bool new_start = true; 125 Degree maximum_degree = 0; 126 127 //Creating a std-vector for storing the distance from the start vertex in dist 128 std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(G), 0); 129 130 //Wrap a property_map_iterator around the std::iterator 131 boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, G)); 132 133 //Creating a property_map for the indices of a vertex 134 typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, G); 135 136 //Creating a priority queue 137 typedef indirect_cmp<DegreeMap, std::greater<Degree> > Compare; 138 Compare comp(degree); 139 std::priority_queue<Vertex, std::vector<Vertex>, Compare> degree_queue(comp); 140 141 //step 1 142 //Scan for the vertex with the smallest degree and the maximum degree 143 typename graph_traits<Graph>::vertex_iterator ui, ui_end; 144 for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) 145 { 146 dummy = get(degree, *ui); 147 148 if(dummy < my_degree) 149 { 150 my_degree = dummy; 151 s = *ui; 152 } 153 154 if(dummy > maximum_degree) 155 { 156 maximum_degree = dummy; 157 } 158 } 159 //end 1 160 161 do{ 162 new_start = false; //Setting the loop repetition status to false 163 164 //step 2 165 //initialize the the disance std-vector with 0 166 for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0; 167 168 //generating the RLS (rooted level structure) 169 breadth_first_search 170 (G, s, visitor 171 ( 172 make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) ) 173 ) 174 ); 175 176 //end 2 177 178 //step 3 179 //calculating the depth of the RLS 180 h_s = RLS_depth(dist); 181 182 //step 4 183 //pushing one node of each degree in an ascending manner into degree_queue 184 std::vector<bool> shrink_trace(maximum_degree, false); 185 for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) 186 { 187 dummy = get(degree, *ui); 188 189 if( (dist[index_map[*ui]] == h_s ) && ( !shrink_trace[ dummy ] ) ) 190 { 191 degree_queue.push(*ui); 192 shrink_trace[ dummy ] = true; 193 } 194 } 195 196 //end 3 & 4 197 198 199 // step 5 200 // Initializing w 201 w_e = (std::numeric_limits<Degree>::max)(); 202 //end 5 203 204 205 //step 6 206 //Testing for termination 207 while( !degree_queue.empty() ) 208 { 209 i = degree_queue.top(); //getting the node with the lowest degree from the degree queue 210 degree_queue.pop(); //ereasing the node with the lowest degree from the degree queue 211 212 //generating a RLS 213 for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0; 214 215 breadth_first_search 216 (G, i, boost::visitor 217 ( 218 make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) ) 219 ) 220 ); 221 222 //Calculating depth and width of the rooted level 223 h_i = RLS_depth(dist); 224 w_i = RLS_max_width(dist, h_i); 225 226 //Testing for termination 227 if( (h_i > h_s) && (w_i < w_e) ) 228 { 229 h_s = h_i; 230 s = i; 231 while(!degree_queue.empty()) degree_queue.pop(); 232 new_start = true; 233 } 234 else if(w_i < w_e) 235 { 236 w_e = w_i; 237 e = i; 238 } 239 } 240 //end 6 241 242 }while(new_start); 243 244 return e; 245 } 246 247 ////////////////////////////////////////////////////////////////////////// 248 // Sloan algorithm with a given starting Vertex. 249 // 250 // This algorithm requires user to provide a starting vertex to 251 // compute Sloan ordering. 252 ////////////////////////////////////////////////////////////////////////// 253 template <class Graph, class OutputIterator, 254 class ColorMap, class DegreeMap, 255 class PriorityMap, class Weight> 256 OutputIterator 257 sloan_ordering(Graph& g, 258 typename graph_traits<Graph>::vertex_descriptor s, 259 typename graph_traits<Graph>::vertex_descriptor e, 260 OutputIterator permutation, 261 ColorMap color, 262 DegreeMap degree, 263 PriorityMap priority, 264 Weight W1, 265 Weight W2) 266 { 267 //typedef typename property_traits<DegreeMap>::value_type Degree; 268 typedef typename property_traits<PriorityMap>::value_type Degree; 269 typedef typename property_traits<ColorMap>::value_type ColorValue; 270 typedef color_traits<ColorValue> Color; 271 typedef typename graph_traits<Graph>::vertex_descriptor Vertex; 272 typedef typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter; 273 typedef typename graph_traits<Graph>::vertices_size_type size_type; 274 275 typedef typename property_map<Graph, vertex_index_t>::const_type VertexID; 276 277 278 //Creating a std-vector for storing the distance from the end vertex in it 279 typename std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(g), 0); 280 281 //Wrap a property_map_iterator around the std::iterator 282 boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, g)); 283 284 breadth_first_search 285 (g, e, visitor 286 ( 287 make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) ) 288 ) 289 ); 290 291 //Creating a property_map for the indices of a vertex 292 typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, g); 293 294 //Sets the color and priority to their initial status 295 Degree cdeg; 296 typename graph_traits<Graph>::vertex_iterator ui, ui_end; 297 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) 298 { 299 put(color, *ui, Color::white()); 300 cdeg=get(degree, *ui)+1; 301 put(priority, *ui, W1*dist[index_map[*ui]]-W2*cdeg ); 302 } 303 304 //Priority list 305 typedef indirect_cmp<PriorityMap, std::greater<Degree> > Compare; 306 Compare comp(priority); 307 std::list<Vertex> priority_list; 308 309 //Some more declarations 310 typename graph_traits<Graph>::out_edge_iterator ei, ei_end, ei2, ei2_end; 311 Vertex u, v, w; 312 313 put(color, s, Color::green()); //Sets the color of the starting vertex to gray 314 priority_list.push_front(s); //Puts s into the priority_list 315 316 while ( !priority_list.empty() ) 317 { 318 priority_list.sort(comp); //Orders the elements in the priority list in an ascending manner 319 320 u = priority_list.front(); //Accesses the last element in the priority list 321 priority_list.pop_front(); //Removes the last element in the priority list 322 323 if(get(color, u) == Color::green() ) 324 { 325 //for-loop over all out-edges of vertex u 326 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) 327 { 328 v = target(*ei, g); 329 330 put( priority, v, get(priority, v) + W2 ); //updates the priority 331 332 if (get(color, v) == Color::white() ) //test if the vertex is inactive 333 { 334 put(color, v, Color::green() ); //giving the vertex a preactive status 335 priority_list.push_front(v); //writing the vertex in the priority_queue 336 } 337 } 338 } 339 340 //Here starts step 8 341 *permutation++ = u; //Puts u to the first position in the permutation-vector 342 put(color, u, Color::black() ); //Gives u an inactive status 343 344 //for loop over all the adjacent vertices of u 345 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { 346 347 v = target(*ei, g); 348 349 if (get(color, v) == Color::green() ) { //tests if the vertex is inactive 350 351 put(color, v, Color::red() ); //giving the vertex an active status 352 put(priority, v, get(priority, v)+W2); //updates the priority 353 354 //for loop over alll adjacent vertices of v 355 for (boost::tie(ei2, ei2_end) = out_edges(v, g); ei2 != ei2_end; ++ei2) { 356 w = target(*ei2, g); 357 358 if(get(color, w) != Color::black() ) { //tests if vertex is postactive 359 360 put(priority, w, get(priority, w)+W2); //updates the priority 361 362 if(get(color, w) == Color::white() ){ 363 364 put(color, w, Color::green() ); // gives the vertex a preactive status 365 priority_list.push_front(w); // puts the vertex into the priority queue 366 367 } //end if 368 369 } //end if 370 371 } //end for 372 373 } //end if 374 375 } //end for 376 377 } //end while 378 379 380 return permutation; 381 } 382 383 ///////////////////////////////////////////////////////////////////////////////////////// 384 // Same algorithm as before, but without the weights given (taking default weights 385 template <class Graph, class OutputIterator, 386 class ColorMap, class DegreeMap, 387 class PriorityMap> 388 OutputIterator 389 sloan_ordering(Graph& g, 390 typename graph_traits<Graph>::vertex_descriptor s, 391 typename graph_traits<Graph>::vertex_descriptor e, 392 OutputIterator permutation, 393 ColorMap color, 394 DegreeMap degree, 395 PriorityMap priority) 396 { 397 return sloan_ordering(g, s, e, permutation, color, degree, priority, WEIGHT1, WEIGHT2); 398 } 399 400 401 ////////////////////////////////////////////////////////////////////////// 402 // Sloan algorithm without a given starting Vertex. 403 // 404 // This algorithm finds a good starting vertex itself to 405 // compute Sloan-ordering. 406 ////////////////////////////////////////////////////////////////////////// 407 408 409 410 template < class Graph, class OutputIterator, 411 class Color, class Degree, 412 class Priority, class Weight> 413 inline OutputIterator sloan_ordering(Graph & G,OutputIterator permutation,Color color,Degree degree,Priority priority,Weight W1,Weight W2)414 sloan_ordering(Graph& G, 415 OutputIterator permutation, 416 Color color, 417 Degree degree, 418 Priority priority, 419 Weight W1, 420 Weight W2 ) 421 { 422 typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex; 423 424 Vertex s, e; 425 e = sloan_start_end_vertices(G, s, color, degree); 426 427 return sloan_ordering(G, s, e, permutation, color, degree, priority, W1, W2); 428 } 429 430 ///////////////////////////////////////////////////////////////////////////////////////// 431 // Same as before, but without given weights (default weights are taken instead) 432 template < class Graph, class OutputIterator, 433 class Color, class Degree, 434 class Priority > 435 inline OutputIterator sloan_ordering(Graph & G,OutputIterator permutation,Color color,Degree degree,Priority priority)436 sloan_ordering(Graph& G, 437 OutputIterator permutation, 438 Color color, 439 Degree degree, 440 Priority priority) 441 { 442 return sloan_ordering(G, permutation, color, degree, priority, WEIGHT1, WEIGHT2); 443 } 444 445 446 } // namespace boost 447 448 449 #endif // BOOST_GRAPH_SLOAN_HPP 450