Chris@16: //
Chris@16: //=======================================================================
Chris@16: // Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch)
Chris@16: // ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st)
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: //
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_SLOAN_HPP
Chris@16: #define BOOST_GRAPH_SLOAN_HPP
Chris@16: 
Chris@16: #define WEIGHT1 1               //default weight for the distance in the Sloan algorithm
Chris@16: #define WEIGHT2 2               //default weight for the degree in the Sloan algorithm
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: #include <vector>
Chris@16: #include <queue>
Chris@16: #include <algorithm>
Chris@16: #include <limits>
Chris@16: #include <boost/pending/queue.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/breadth_first_search.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: #include <boost/pending/indirect_cmp.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/graph/visitors.hpp>
Chris@16: #include <boost/graph/adjacency_list.hpp>
Chris@16: #include <boost/graph/cuthill_mckee_ordering.hpp>
Chris@16: 
Chris@16: 
Chris@16: ////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: //Sloan-Algorithm for graph reordering
Chris@16: //(optimzes profile and wavefront, not primiraly bandwidth
Chris@16: //
Chris@16: ////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: namespace boost {
Chris@16:         
Chris@16:   /////////////////////////////////////////////////////////////////////////
Chris@16:   // Function that returns the maximum depth of 
Chris@16:   // a rooted level strucutre (RLS)
Chris@16:   //
Chris@16:   /////////////////////////////////////////////////////////////////////////
Chris@16:   template<class Distance>
Chris@16:   typename Distance::value_type RLS_depth(Distance& d)
Chris@16:   {
Chris@16:     typename Distance::value_type h_s = 0;
Chris@16:     typename Distance::iterator iter;
Chris@16:     
Chris@16:     for (iter = d.begin(); iter != d.end(); ++iter)
Chris@16:       {
Chris@16:         if(*iter > h_s)
Chris@16:           {
Chris@16:             h_s = *iter;
Chris@16:           }
Chris@16:       }
Chris@16:     
Chris@16:     return h_s;
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:     
Chris@16:   /////////////////////////////////////////////////////////////////////////
Chris@16:   // Function that returns the width of the largest level of 
Chris@16:   // a rooted level strucutre (RLS)
Chris@16:   //
Chris@16:   /////////////////////////////////////////////////////////////////////////
Chris@16:   template<class Distance, class my_int>
Chris@16:   typename Distance::value_type RLS_max_width(Distance& d, my_int depth)
Chris@16:   {
Chris@16: 
Chris@16:       typedef typename Distance::value_type Degree;
Chris@16:     
Chris@16:       //Searching for the maximum width of a level
Chris@16:       std::vector<Degree> dummy_width(depth+1, 0);
Chris@16:       typename std::vector<Degree>::iterator my_it;
Chris@16:       typename Distance::iterator iter;
Chris@16:       Degree w_max = 0;
Chris@16:       
Chris@16:       for (iter = d.begin(); iter != d.end(); ++iter)
Chris@16:       {
Chris@16:           dummy_width[*iter]++;
Chris@16:       }
Chris@16:       
Chris@16:       for(my_it = dummy_width.begin(); my_it != dummy_width.end(); ++my_it)
Chris@16:       {
Chris@16:           if(*my_it > w_max) w_max = *my_it;
Chris@16:       }
Chris@16:       
Chris@16:       return w_max;
Chris@16:       
Chris@16:   }
Chris@16:     
Chris@16: 
Chris@16:   /////////////////////////////////////////////////////////////////////////
Chris@16:   // Function for finding a good starting node for Sloan algorithm
Chris@16:   //
Chris@16:   // This is to find a good starting node. "good" is in the sense
Chris@16:   // of the ordering generated. 
Chris@16:   /////////////////////////////////////////////////////////////////////////
Chris@16:   template <class Graph, class ColorMap, class DegreeMap> 
Chris@16:   typename graph_traits<Graph>::vertex_descriptor 
Chris@16:   sloan_start_end_vertices(Graph& G, 
Chris@16:                            typename graph_traits<Graph>::vertex_descriptor &s, 
Chris@16:                            ColorMap color, 
Chris@16:                            DegreeMap degree)
Chris@16:   {
Chris@16:     typedef typename property_traits<DegreeMap>::value_type Degree;
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     typedef typename std::vector< typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type size_type;
Chris@16:     
Chris@16:     typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;
Chris@16:     
Chris@16:     s = *(vertices(G).first);
Chris@16:     Vertex e = s;
Chris@16:     Vertex i;
Chris@16:     Degree my_degree = get(degree, s ); 
Chris@16:     Degree dummy, h_i, h_s, w_i, w_e;
Chris@16:     bool new_start = true;
Chris@16:     Degree maximum_degree = 0;
Chris@16:     
Chris@16:     //Creating a std-vector for storing the distance from the start vertex in dist
Chris@16:     std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(G), 0);
Chris@16: 
Chris@16:     //Wrap a property_map_iterator around the std::iterator
Chris@16:     boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, G));
Chris@16:     
Chris@16:     //Creating a property_map for the indices of a vertex
Chris@16:     typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, G);
Chris@16:     
Chris@16:     //Creating a priority queue
Chris@16:     typedef indirect_cmp<DegreeMap, std::greater<Degree> > Compare;
Chris@16:     Compare comp(degree);
Chris@16:     std::priority_queue<Vertex, std::vector<Vertex>, Compare> degree_queue(comp);
Chris@16:     
Chris@16:     //step 1
Chris@16:     //Scan for the vertex with the smallest degree and the maximum degree
Chris@16:     typename graph_traits<Graph>::vertex_iterator ui, ui_end;
Chris@16:     for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
Chris@16:     {
Chris@16:       dummy = get(degree, *ui);
Chris@16:       
Chris@16:       if(dummy < my_degree)
Chris@16:       {
Chris@16:         my_degree = dummy;
Chris@16:         s = *ui;
Chris@16:       }
Chris@16:       
Chris@16:       if(dummy > maximum_degree)
Chris@16:       {
Chris@16:         maximum_degree = dummy;
Chris@16:       }
Chris@16:     }
Chris@16:     //end 1
Chris@16:     
Chris@16:     do{  
Chris@16:       new_start = false;     //Setting the loop repetition status to false
Chris@16:       
Chris@16:       //step 2
Chris@16:       //initialize the the disance std-vector with 0
Chris@16:       for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;
Chris@16:       
Chris@16:       //generating the RLS (rooted level structure)
Chris@16:       breadth_first_search
Chris@16:         (G, s, visitor
Chris@16:          (
Chris@16:            make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
Chris@16:            )
Chris@16:           );
Chris@16:       
Chris@16:       //end 2
Chris@16:       
Chris@16:       //step 3
Chris@16:       //calculating the depth of the RLS
Chris@16:       h_s = RLS_depth(dist);
Chris@16:       
Chris@16:       //step 4
Chris@16:       //pushing one node of each degree in an ascending manner into degree_queue
Chris@16:       std::vector<bool> shrink_trace(maximum_degree, false);
Chris@16:       for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
Chris@16:       {
Chris@16:         dummy = get(degree, *ui);
Chris@16:         
Chris@16:         if( (dist[index_map[*ui]] == h_s ) && ( !shrink_trace[ dummy ] ) )
Chris@16:         {
Chris@16:           degree_queue.push(*ui);
Chris@16:           shrink_trace[ dummy ] = true;
Chris@16:         }
Chris@16:       }
Chris@16:       
Chris@16:       //end 3 & 4
Chris@16: 
Chris@16:       
Chris@16:       // step 5
Chris@16:       // Initializing w
Chris@16:       w_e = (std::numeric_limits<Degree>::max)();
Chris@16:       //end 5
Chris@16:       
Chris@16:       
Chris@16:       //step 6
Chris@16:       //Testing for termination
Chris@16:       while( !degree_queue.empty() )
Chris@16:       {
Chris@16:         i = degree_queue.top();       //getting the node with the lowest degree from the degree queue
Chris@16:         degree_queue.pop();           //ereasing the node with the lowest degree from the degree queue
Chris@16:         
Chris@16:         //generating a RLS          
Chris@16:         for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;
Chris@16:         
Chris@16:         breadth_first_search
Chris@16:           (G, i, boost::visitor
Chris@16:            (
Chris@16:              make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
Chris@16:              )
Chris@16:             );
Chris@16:         
Chris@16:         //Calculating depth and width of the rooted level
Chris@16:         h_i = RLS_depth(dist);
Chris@16:         w_i = RLS_max_width(dist, h_i);
Chris@16:         
Chris@16:         //Testing for termination
Chris@16:         if( (h_i > h_s) && (w_i < w_e) ) 
Chris@16:         {
Chris@16:           h_s = h_i;
Chris@16:           s = i;
Chris@16:           while(!degree_queue.empty()) degree_queue.pop();
Chris@16:           new_start = true;         
Chris@16:         }
Chris@16:         else if(w_i < w_e)
Chris@16:         { 
Chris@16:           w_e = w_i;
Chris@16:           e = i;
Chris@16:         }
Chris@16:       }
Chris@16:       //end 6
Chris@16:         
Chris@16:     }while(new_start);
Chris@16:     
Chris@16:     return e;
Chris@16:   }
Chris@16: 
Chris@16:   //////////////////////////////////////////////////////////////////////////
Chris@16:   // Sloan algorithm with a given starting Vertex.
Chris@16:   //
Chris@16:   // This algorithm requires user to provide a starting vertex to
Chris@16:   // compute Sloan ordering.
Chris@16:   //////////////////////////////////////////////////////////////////////////
Chris@16:   template <class Graph, class OutputIterator,
Chris@16:             class ColorMap, class DegreeMap,
Chris@16:             class PriorityMap, class Weight>
Chris@16:   OutputIterator
Chris@16:   sloan_ordering(Graph& g,
Chris@16:                  typename graph_traits<Graph>::vertex_descriptor s,
Chris@16:                  typename graph_traits<Graph>::vertex_descriptor e,
Chris@16:                  OutputIterator permutation, 
Chris@16:                  ColorMap color, 
Chris@16:                  DegreeMap degree, 
Chris@16:                  PriorityMap priority, 
Chris@16:                  Weight W1, 
Chris@16:                  Weight W2)
Chris@16:   {
Chris@16:     //typedef typename property_traits<DegreeMap>::value_type Degree;
Chris@16:     typedef typename property_traits<PriorityMap>::value_type Degree;
Chris@16:     typedef typename property_traits<ColorMap>::value_type ColorValue;
Chris@16:     typedef color_traits<ColorValue> Color;
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     typedef typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type size_type;
Chris@16: 
Chris@16:     typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;
Chris@16: 
Chris@16:     
Chris@16:     //Creating a std-vector for storing the distance from the end vertex in it
Chris@16:     typename std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(g), 0);
Chris@16:     
Chris@16:     //Wrap a property_map_iterator around the std::iterator
Chris@16:     boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, g)); 
Chris@16:     
Chris@16:     breadth_first_search
Chris@16:       (g, e, visitor
Chris@16:        (
Chris@16:            make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
Chris@16:         )
Chris@16:        );
Chris@16:     
Chris@16:     //Creating a property_map for the indices of a vertex
Chris@16:     typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, g);
Chris@16:     
Chris@16:     //Sets the color and priority to their initial status
Chris@16:     Degree cdeg;    
Chris@16:     typename graph_traits<Graph>::vertex_iterator ui, ui_end;
Chris@16:     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
Chris@16:     {
Chris@16:         put(color, *ui, Color::white());
Chris@16:         cdeg=get(degree, *ui)+1;
Chris@16:         put(priority, *ui, W1*dist[index_map[*ui]]-W2*cdeg );  
Chris@16:     }
Chris@16:     
Chris@16:     //Priority list
Chris@16:     typedef indirect_cmp<PriorityMap, std::greater<Degree> > Compare;
Chris@16:     Compare comp(priority);
Chris@16:     std::list<Vertex> priority_list;
Chris@16: 
Chris@16:     //Some more declarations
Chris@16:     typename graph_traits<Graph>::out_edge_iterator ei, ei_end, ei2, ei2_end;
Chris@16:     Vertex u, v, w;
Chris@16: 
Chris@16:     put(color, s, Color::green());      //Sets the color of the starting vertex to gray
Chris@16:     priority_list.push_front(s);                 //Puts s into the priority_list
Chris@16:     
Chris@16:     while ( !priority_list.empty() ) 
Chris@16:     {  
Chris@16:       priority_list.sort(comp);         //Orders the elements in the priority list in an ascending manner
Chris@16:       
Chris@16:       u = priority_list.front();           //Accesses the last element in the priority list
Chris@16:       priority_list.pop_front();               //Removes the last element in the priority list
Chris@16:       
Chris@16:       if(get(color, u) == Color::green() )
Chris@16:       {
Chris@16:         //for-loop over all out-edges of vertex u
Chris@16:         for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) 
Chris@16:         {
Chris@16:           v = target(*ei, g);
Chris@16:           
Chris@16:           put( priority, v, get(priority, v) + W2 ); //updates the priority
Chris@16:           
Chris@16:           if (get(color, v) == Color::white() )      //test if the vertex is inactive
Chris@16:           {
Chris@16:             put(color, v, Color::green() );        //giving the vertex a preactive status
Chris@16:             priority_list.push_front(v);                     //writing the vertex in the priority_queue
Chris@16:           }           
Chris@16:         }
Chris@16:       }
Chris@16:       
Chris@16:       //Here starts step 8
Chris@16:       *permutation++ = u;                      //Puts u to the first position in the permutation-vector
Chris@16:       put(color, u, Color::black() );          //Gives u an inactive status
Chris@16:       
Chris@16:       //for loop over all the adjacent vertices of u
Chris@16:       for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
Chris@16:         
Chris@16:         v = target(*ei, g);     
Chris@16:         
Chris@16:         if (get(color, v) == Color::green() ) {      //tests if the vertex is inactive
Chris@16:           
Chris@16:           put(color, v, Color::red() );        //giving the vertex an active status
Chris@16:           put(priority, v, get(priority, v)+W2);  //updates the priority        
Chris@16:           
Chris@16:           //for loop over alll adjacent vertices of v
Chris@16:           for (boost::tie(ei2, ei2_end) = out_edges(v, g); ei2 != ei2_end; ++ei2) {
Chris@16:             w = target(*ei2, g);
Chris@16:             
Chris@16:             if(get(color, w) != Color::black() ) {     //tests if vertex is postactive
Chris@16:               
Chris@16:               put(priority, w, get(priority, w)+W2);  //updates the priority
Chris@16:               
Chris@16:               if(get(color, w) == Color::white() ){
Chris@16:                 
Chris@16:                 put(color, w, Color::green() );   // gives the vertex a preactive status
Chris@16:                 priority_list.push_front(w);           // puts the vertex into the priority queue
Chris@16:                 
Chris@16:               } //end if
Chris@16:               
Chris@16:             } //end if
Chris@16:             
Chris@16:           } //end for
Chris@16:           
Chris@16:         } //end if
Chris@16:         
Chris@16:       } //end for
Chris@16:       
Chris@16:     } //end while
Chris@16:     
Chris@16:     
Chris@16:     return permutation;
Chris@16:   }  
Chris@16:   
Chris@16:   /////////////////////////////////////////////////////////////////////////////////////////
Chris@16:   // Same algorithm as before, but without the weights given (taking default weights
Chris@16:   template <class Graph, class OutputIterator,
Chris@16:             class ColorMap, class DegreeMap,
Chris@16:             class PriorityMap>
Chris@16:   OutputIterator
Chris@16:   sloan_ordering(Graph& g,
Chris@16:                  typename graph_traits<Graph>::vertex_descriptor s,
Chris@16:                  typename graph_traits<Graph>::vertex_descriptor e,
Chris@16:                  OutputIterator permutation, 
Chris@16:                  ColorMap color, 
Chris@16:                  DegreeMap degree, 
Chris@16:                  PriorityMap priority)
Chris@16:   {
Chris@16:     return sloan_ordering(g, s, e, permutation, color, degree, priority, WEIGHT1, WEIGHT2); 
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   //////////////////////////////////////////////////////////////////////////
Chris@16:   // Sloan algorithm without a given starting Vertex.
Chris@16:   //
Chris@16:   // This algorithm finds a good starting vertex itself to
Chris@16:   // compute Sloan-ordering.
Chris@16:   //////////////////////////////////////////////////////////////////////////
Chris@16:  
Chris@16: 
Chris@16: 
Chris@16:   template < class Graph, class OutputIterator, 
Chris@16:              class Color, class Degree,
Chris@16:              class Priority, class Weight>
Chris@16:   inline OutputIterator
Chris@16:   sloan_ordering(Graph& G, 
Chris@16:                  OutputIterator permutation, 
Chris@16:                  Color color, 
Chris@16:                  Degree degree, 
Chris@16:                  Priority priority, 
Chris@16:                  Weight W1, 
Chris@16:                  Weight W2 )
Chris@16:   {
Chris@16:     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     
Chris@16:     Vertex s, e;
Chris@16:     e = sloan_start_end_vertices(G, s, color, degree);
Chris@16:     
Chris@16:     return sloan_ordering(G, s, e, permutation, color, degree, priority, W1, W2);
Chris@16:   }
Chris@16: 
Chris@16:   /////////////////////////////////////////////////////////////////////////////////////////
Chris@16:   // Same as before, but without given weights (default weights are taken instead)
Chris@16:   template < class Graph, class OutputIterator, 
Chris@16:              class Color, class Degree,
Chris@16:              class Priority >
Chris@16:   inline OutputIterator
Chris@16:   sloan_ordering(Graph& G, 
Chris@16:                  OutputIterator permutation, 
Chris@16:                  Color color, 
Chris@16:                  Degree degree, 
Chris@16:                  Priority priority)
Chris@16:   { 
Chris@16:     return sloan_ordering(G, permutation, color, degree, priority, WEIGHT1, WEIGHT2);
Chris@16:   }
Chris@16:   
Chris@16:   
Chris@16: } // namespace boost
Chris@16: 
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_SLOAN_HPP