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