ceph/src/boost/libs/graph/include/boost/graph/sloan_ordering.hpp

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