boost/graph/sloan_ordering.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch)
0004 // ETH Zurich, Center of Structure Technologies
0005 // (https://web.archive.org/web/20050307090307/http://www.structures.ethz.ch/)
0006 //
0007 // Distributed under the Boost Software License, Version 1.0. (See
0008 // accompanying file LICENSE_1_0.txt or copy at
0009 // http://www.boost.org/LICENSE_1_0.txt)
0010 //=======================================================================
0011 //
0012
0013 #ifndef BOOST_GRAPH_SLOAN_HPP
0014 #define BOOST_GRAPH_SLOAN_HPP
0015
0016 #define WEIGHT1 1 // default weight for the distance in the Sloan algorithm
0017 #define WEIGHT2 2 // default weight for the degree in the Sloan algorithm
0018
0019 #include <boost/config.hpp>
0020 #include <vector>
0021 #include <queue>
0022 #include <algorithm>
0023 #include <limits>
0024 #include <boost/pending/queue.hpp>
0025 #include <boost/graph/graph_traits.hpp>
0026 #include <boost/graph/breadth_first_search.hpp>
0027 #include <boost/graph/properties.hpp>
0028 #include <boost/pending/indirect_cmp.hpp>
0029 #include <boost/property_map/property_map.hpp>
0030 #include <boost/graph/visitors.hpp>
0031 #include <boost/graph/adjacency_list.hpp>
0032 #include <boost/graph/cuthill_mckee_ordering.hpp>
0033
0034 ////////////////////////////////////////////////////////////
0035 //
0036 // Sloan-Algorithm for graph reordering
0037 //(optimzes profile and wavefront, not primiraly bandwidth
0038 //
0039 ////////////////////////////////////////////////////////////
0040
0041 namespace boost
0042 {
0043
0044 /////////////////////////////////////////////////////////////////////////
0045 // Function that returns the maximum depth of
0046 // a rooted level strucutre (RLS)
0047 //
0048 /////////////////////////////////////////////////////////////////////////
0049 template < class Distance > typename Distance::value_type RLS_depth(Distance& d)
0050 {
0051     typename Distance::value_type h_s = 0;
0052     typename Distance::iterator iter;
0053
0054     for (iter = d.begin(); iter != d.end(); ++iter)
0055     {
0056         if (*iter > h_s)
0057         {
0058             h_s = *iter;
0059         }
0060     }
0061
0062     return h_s;
0063 }
0064
0065 /////////////////////////////////////////////////////////////////////////
0066 // Function that returns the width of the largest level of
0067 // a rooted level strucutre (RLS)
0068 //
0069 /////////////////////////////////////////////////////////////////////////
0070 template < class Distance, class my_int >
0071 typename Distance::value_type RLS_max_width(Distance& d, my_int depth)
0072 {
0073
0074     typedef typename Distance::value_type Degree;
0075
0076     // Searching for the maximum width of a level
0077     std::vector< Degree > dummy_width(depth + 1, 0);
0078     typename std::vector< Degree >::iterator my_it;
0079     typename Distance::iterator iter;
0080     Degree w_max = 0;
0081
0082     for (iter = d.begin(); iter != d.end(); ++iter)
0083     {
0084         dummy_width[*iter]++;
0085     }
0086
0087     for (my_it = dummy_width.begin(); my_it != dummy_width.end(); ++my_it)
0088     {
0089         if (*my_it > w_max)
0090             w_max = *my_it;
0091     }
0092
0093     return w_max;
0094 }
0095
0096 /////////////////////////////////////////////////////////////////////////
0097 // Function for finding a good starting node for Sloan algorithm
0098 //
0099 // This is to find a good starting node. "good" is in the sense
0100 // of the ordering generated.
0101 /////////////////////////////////////////////////////////////////////////
0102 template < class Graph, class ColorMap, class DegreeMap >
0103 typename graph_traits< Graph >::vertex_descriptor sloan_start_end_vertices(
0104     Graph& G, typename graph_traits< Graph >::vertex_descriptor& s,
0105     ColorMap color, DegreeMap degree)
0106 {
0107     typedef typename property_traits< DegreeMap >::value_type Degree;
0108     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0109     typedef typename std::vector<
0110         typename graph_traits< Graph >::vertices_size_type >::iterator vec_iter;
0111     typedef typename graph_traits< Graph >::vertices_size_type size_type;
0112
0113     typedef typename property_map< Graph, vertex_index_t >::const_type VertexID;
0114
0115     s = *(vertices(G).first);
0116     Vertex e = s;
0117     Vertex i;
0118     Degree my_degree = get(degree, s);
0119     Degree dummy, h_i, h_s, w_i, w_e;
0120     bool new_start = true;
0121     Degree maximum_degree = 0;
0122
0123     // Creating a std-vector for storing the distance from the start vertex in
0124     // dist
0125     std::vector< typename graph_traits< Graph >::vertices_size_type > dist(
0126         num_vertices(G), 0);
0127
0128     // Wrap a property_map_iterator around the std::iterator
0129     boost::iterator_property_map< vec_iter, VertexID, size_type, size_type& >
0130         dist_pmap(dist.begin(), get(vertex_index, G));
0131
0132     // Creating a property_map for the indices of a vertex
0133     typename property_map< Graph, vertex_index_t >::type index_map
0134         = get(vertex_index, G);
0135
0136     // Creating a priority queue
0137     typedef indirect_cmp< DegreeMap, std::greater< Degree > > Compare;
0138     Compare comp(degree);
0139     std::priority_queue< Vertex, std::vector< Vertex >, Compare > degree_queue(
0140         comp);
0141
0142     // step 1
0143     // Scan for the vertex with the smallest degree and the maximum degree
0144     typename graph_traits< Graph >::vertex_iterator ui, ui_end;
0145     for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
0146     {
0147         dummy = get(degree, *ui);
0148
0149         if (dummy < my_degree)
0150         {
0151             my_degree = dummy;
0152             s = *ui;
0153         }
0154
0155         if (dummy > maximum_degree)
0156         {
0157             maximum_degree = dummy;
0158         }
0159     }
0160     // end 1
0161
0162     do
0163     {
0164         new_start = false; // Setting the loop repetition status to false
0165
0166         // step 2
0167         // initialize the the disance std-vector with 0
0168         for (typename std::vector< typename graph_traits<
0169                  Graph >::vertices_size_type >::iterator iter
0170              = dist.begin();
0171              iter != dist.end(); ++iter)
0172             *iter = 0;
0173
0174         // generating the RLS (rooted level structure)
0175         breadth_first_search(G, s,
0176             visitor(
0177                 make_bfs_visitor(record_distances(dist_pmap, on_tree_edge()))));
0178
0179         // end 2
0180
0181         // step 3
0182         // calculating the depth of the RLS
0183         h_s = RLS_depth(dist);
0184
0185         // step 4
0186         // pushing one node of each degree in an ascending manner into
0187         // degree_queue
0188         std::vector< bool > shrink_trace(maximum_degree, false);
0189         for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
0190         {
0191             dummy = get(degree, *ui);
0192
0193             if ((dist[index_map[*ui]] == h_s) && (!shrink_trace[dummy]))
0194             {
0195                 degree_queue.push(*ui);
0196                 shrink_trace[dummy] = true;
0197             }
0198         }
0199
0200         // end 3 & 4
0201
0202         // step 5
0203         // Initializing w
0204         w_e = (std::numeric_limits< Degree >::max)();
0205         // end 5
0206
0207         // step 6
0208         // Testing for termination
0209         while (!degree_queue.empty())
0210         {
0211             i = degree_queue.top(); // getting the node with the lowest degree
0212                                     // from the degree queue
0213             degree_queue.pop(); // ereasing the node with the lowest degree from
0214                                 // the degree queue
0215
0216             // generating a RLS
0217             for (typename std::vector< typename graph_traits<
0218                      Graph >::vertices_size_type >::iterator iter
0219                  = dist.begin();
0220                  iter != dist.end(); ++iter)
0221                 *iter = 0;
0222
0223             breadth_first_search(G, i,
0224                 boost::visitor(make_bfs_visitor(
0225                     record_distances(dist_pmap, on_tree_edge()))));
0226
0227             // Calculating depth and width of the rooted level
0228             h_i = RLS_depth(dist);
0229             w_i = RLS_max_width(dist, h_i);
0230
0231             // Testing for termination
0232             if ((h_i > h_s) && (w_i < w_e))
0233             {
0234                 h_s = h_i;
0235                 s = i;
0236                 while (!degree_queue.empty())
0237                     degree_queue.pop();
0238                 new_start = true;
0239             }
0240             else if (w_i < w_e)
0241             {
0242                 w_e = w_i;
0243                 e = i;
0244             }
0245         }
0246         // end 6
0247
0248     } while (new_start);
0249
0250     return e;
0251 }
0252
0253 //////////////////////////////////////////////////////////////////////////
0254 // Sloan algorithm with a given starting Vertex.
0255 //
0256 // This algorithm requires user to provide a starting vertex to
0257 // compute Sloan ordering.
0258 //////////////////////////////////////////////////////////////////////////
0259 template < class Graph, class OutputIterator, class ColorMap, class DegreeMap,
0260     class PriorityMap, class Weight >
0261 OutputIterator sloan_ordering(Graph& g,
0262     typename graph_traits< Graph >::vertex_descriptor s,
0263     typename graph_traits< Graph >::vertex_descriptor e,
0264     OutputIterator permutation, ColorMap color, DegreeMap degree,
0265     PriorityMap priority, Weight W1, Weight W2)
0266 {
0267     // typedef typename property_traits<DegreeMap>::value_type Degree;
0268     typedef typename property_traits< PriorityMap >::value_type Degree;
0269     typedef typename property_traits< ColorMap >::value_type ColorValue;
0270     typedef color_traits< ColorValue > Color;
0271     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0272     typedef typename std::vector<
0273         typename graph_traits< Graph >::vertices_size_type >::iterator vec_iter;
0274     typedef typename graph_traits< Graph >::vertices_size_type size_type;
0275
0276     typedef typename property_map< Graph, vertex_index_t >::const_type VertexID;
0277
0278     // Creating a std-vector for storing the distance from the end vertex in it
0279     typename std::vector< typename graph_traits< Graph >::vertices_size_type >
0280         dist(num_vertices(g), 0);
0281
0282     // Wrap a property_map_iterator around the std::iterator
0283     boost::iterator_property_map< vec_iter, VertexID, size_type, size_type& >
0284         dist_pmap(dist.begin(), get(vertex_index, g));
0285
0286     breadth_first_search(g, e,
0287         visitor(make_bfs_visitor(record_distances(dist_pmap, on_tree_edge()))));
0288
0289     // Creating a property_map for the indices of a vertex
0290     typename property_map< Graph, vertex_index_t >::type index_map
0291         = get(vertex_index, g);
0292
0293     // Sets the color and priority to their initial status
0294     Degree cdeg;
0295     typename graph_traits< Graph >::vertex_iterator ui, ui_end;
0296     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
0297     {
0298         put(color, *ui, Color::white());
0299         cdeg = get(degree, *ui) + 1;
0300         put(priority, *ui, W1 * dist[index_map[*ui]] - W2 * cdeg);
0301     }
0302
0303     // Priority list
0304     typedef indirect_cmp< PriorityMap, std::greater< Degree > > Compare;
0305     Compare comp(priority);
0306     std::list< Vertex > priority_list;
0307
0308     // Some more declarations
0309     typename graph_traits< Graph >::out_edge_iterator ei, ei_end, ei2, ei2_end;
0310     Vertex u, v, w;
0311
0312     put(color, s,
0313         Color::green()); // Sets the color of the starting vertex to gray
0314     priority_list.push_front(s); // Puts s into the priority_list
0315
0316     while (!priority_list.empty())
0317     {
0318         priority_list.sort(comp); // Orders the elements in the priority list in
0319                                   // an ascending manner
0320
0321         u = priority_list
0322                 .front(); // Accesses the last element in the priority list
0323         priority_list
0324             .pop_front(); // Removes the last element in the priority list
0325
0326         if (get(color, u) == Color::green())
0327         {
0328             // for-loop over all out-edges of vertex u
0329             for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
0330             {
0331                 v = target(*ei, g);
0332
0333                 put(priority, v, get(priority, v) + W2); // updates the priority
0334
0335                 if (get(color, v)
0336                     == Color::white()) // test if the vertex is inactive
0337                 {
0338                     put(color, v,
0339                         Color::green()); // giving the vertex a preactive status
0340                     priority_list.push_front(
0341                         v); // writing the vertex in the priority_queue
0342                 }
0343             }
0344         }
0345
0346         // Here starts step 8
0347         *permutation++
0348             = u; // Puts u to the first position in the permutation-vector
0349         put(color, u, Color::black()); // Gives u an inactive status
0350
0351         // for loop over all the adjacent vertices of u
0352         for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
0353         {
0354
0355             v = target(*ei, g);
0356
0357             if (get(color, v) == Color::green())
0358             { // tests if the vertex is inactive
0359
0360                 put(color, v,
0361                     Color::red()); // giving the vertex an active status
0362                 put(priority, v, get(priority, v) + W2); // updates the priority
0363
0364                 // for loop over alll adjacent vertices of v
0365                 for (boost::tie(ei2, ei2_end) = out_edges(v, g); ei2 != ei2_end;
0366                      ++ei2)
0367                 {
0368                     w = target(*ei2, g);
0369
0370                     if (get(color, w) != Color::black())
0371                     { // tests if vertex is postactive
0372
0373                         put(priority, w,
0374                             get(priority, w) + W2); // updates the priority
0375
0376                         if (get(color, w) == Color::white())
0377                         {
0378
0379                             put(color, w, Color::green()); // gives the vertex a
0380                                                            // preactive status
0381                             priority_list.push_front(
0382                                 w); // puts the vertex into the priority queue
0383
0384                         } // end if
0385
0386                     } // end if
0387
0388                 } // end for
0389
0390             } // end if
0391
0392         } // end for
0393
0394     } // end while
0395
0396     return permutation;
0397 }
0398
0399 /////////////////////////////////////////////////////////////////////////////////////////
0400 // Same algorithm as before, but without the weights given (taking default
0401 // weights
0402 template < class Graph, class OutputIterator, class ColorMap, class DegreeMap,
0403     class PriorityMap >
0404 OutputIterator sloan_ordering(Graph& g,
0405     typename graph_traits< Graph >::vertex_descriptor s,
0406     typename graph_traits< Graph >::vertex_descriptor e,
0407     OutputIterator permutation, ColorMap color, DegreeMap degree,
0408     PriorityMap priority)
0409 {
0410     return sloan_ordering(
0411         g, s, e, permutation, color, degree, priority, WEIGHT1, WEIGHT2);
0412 }
0413
0414 //////////////////////////////////////////////////////////////////////////
0415 // Sloan algorithm without a given starting Vertex.
0416 //
0417 // This algorithm finds a good starting vertex itself to
0418 // compute Sloan-ordering.
0419 //////////////////////////////////////////////////////////////////////////
0420
0421 template < class Graph, class OutputIterator, class Color, class Degree,
0422     class Priority, class Weight >
0423 inline OutputIterator sloan_ordering(Graph& G, OutputIterator permutation,
0424     Color color, Degree degree, Priority priority, Weight W1, Weight W2)
0425 {
0426     typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
0427
0428     Vertex s, e;
0429     e = sloan_start_end_vertices(G, s, color, degree);
0430
0431     return sloan_ordering(
0432         G, s, e, permutation, color, degree, priority, W1, W2);
0433 }
0434
0435 /////////////////////////////////////////////////////////////////////////////////////////
0436 // Same as before, but without given weights (default weights are taken instead)
0437 template < class Graph, class OutputIterator, class Color, class Degree,
0438     class Priority >
0439 inline OutputIterator sloan_ordering(Graph& G, OutputIterator permutation,
0440     Color color, Degree degree, Priority priority)
0441 {
0442     return sloan_ordering(
0443         G, permutation, color, degree, priority, WEIGHT1, WEIGHT2);
0444 }
0445
0446 } // namespace boost
0447
0448 #endif // BOOST_GRAPH_SLOAN_HPP