path: root/boost/graph/sloan_ordering.hpp

//
//=======================================================================
// Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch)
// ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st)
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
//

#ifndef BOOST_GRAPH_SLOAN_HPP
#define BOOST_GRAPH_SLOAN_HPP

#define WEIGHT1 1               //default weight for the distance in the Sloan algorithm
#define WEIGHT2 2               //default weight for the degree in the Sloan algorithm

#include <boost/config.hpp>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
#include <boost/pending/queue.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/properties.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/cuthill_mckee_ordering.hpp>


////////////////////////////////////////////////////////////
//
//Sloan-Algorithm for graph reordering
//(optimzes profile and wavefront, not primiraly bandwidth
//
////////////////////////////////////////////////////////////

namespace boost {
        
  /////////////////////////////////////////////////////////////////////////
  // Function that returns the maximum depth of 
  // a rooted level strucutre (RLS)
  //
  /////////////////////////////////////////////////////////////////////////
  template<class Distance>
  unsigned RLS_depth(Distance& d)
  {
    unsigned h_s = 0;
    typename Distance::iterator iter;
    
    for (iter = d.begin(); iter != d.end(); ++iter)
      {
        if(*iter > h_s)
          {
            h_s = *iter;
          }
      }
    
    return h_s;
  }


    
  /////////////////////////////////////////////////////////////////////////
  // Function that returns the width of the largest level of 
  // a rooted level strucutre (RLS)
  //
  /////////////////////////////////////////////////////////////////////////
  template<class Distance, class my_int>
  unsigned RLS_max_width(Distance& d, my_int depth)
  {
    
      //Searching for the maximum width of a level
      std::vector<unsigned> dummy_width(depth+1, 0);
      std::vector<unsigned>::iterator my_it;
      typename Distance::iterator iter;
      unsigned w_max = 0;
      
      for (iter = d.begin(); iter != d.end(); ++iter)
      {
          dummy_width[*iter]++;
      }
      
      for(my_it = dummy_width.begin(); my_it != dummy_width.end(); ++my_it)
      {
          if(*my_it > w_max) w_max = *my_it;
      }
      
      return w_max;
      
  }
    

  /////////////////////////////////////////////////////////////////////////
  // Function for finding a good starting node for Sloan algorithm
  //
  // This is to find a good starting node. "good" is in the sense
  // of the ordering generated. 
  /////////////////////////////////////////////////////////////////////////
  template <class Graph, class ColorMap, class DegreeMap> 
  typename graph_traits<Graph>::vertex_descriptor 
  sloan_start_end_vertices(Graph& G, 
                           typename graph_traits<Graph>::vertex_descriptor &s, 
                           ColorMap color, 
                           DegreeMap degree)
  {
    typedef typename property_traits<DegreeMap>::value_type Degree;
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    typedef typename std::vector< typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;
    typedef typename graph_traits<Graph>::vertices_size_type size_type;
    
    typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;
    
    s = *(vertices(G).first);
    Vertex e = s;
    Vertex i;
    unsigned my_degree = get(degree, s ); 
    unsigned dummy, h_i, h_s, w_i, w_e;
    bool new_start = true;
    unsigned maximum_degree = 0;
    
    //Creating a std-vector for storing the distance from the start vertex in dist
    std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(G), 0);

    //Wrap a property_map_iterator around the std::iterator
    boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, G));
    
    //Creating a property_map for the indices of a vertex
    typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, G);
    
    //Creating a priority queue
    typedef indirect_cmp<DegreeMap, std::greater<Degree> > Compare;
    Compare comp(degree);
    std::priority_queue<Vertex, std::vector<Vertex>, Compare> degree_queue(comp);
    
    //step 1
    //Scan for the vertex with the smallest degree and the maximum degree
    typename graph_traits<Graph>::vertex_iterator ui, ui_end;
    for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
    {
      dummy = get(degree, *ui);
      
      if(dummy < my_degree)
      {
        my_degree = dummy;
        s = *ui;
      }
      
      if(dummy > maximum_degree)
      {
        maximum_degree = dummy;
      }
    }
    //end 1
    
    do{  
      new_start = false;     //Setting the loop repetition status to false
      
      //step 2
      //initialize the the disance std-vector with 0
      for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;
      
      //generating the RLS (rooted level structure)
      breadth_first_search
        (G, s, visitor
         (
           make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
           )
          );
      
      //end 2
      
      //step 3
      //calculating the depth of the RLS
      h_s = RLS_depth(dist);
      
      //step 4
      //pushing one node of each degree in an ascending manner into degree_queue
      std::vector<bool> shrink_trace(maximum_degree, false);
      for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
      {
        dummy = get(degree, *ui);
        
        if( (dist[index_map[*ui]] == h_s ) && ( !shrink_trace[ dummy ] ) )
        {
          degree_queue.push(*ui);
          shrink_trace[ dummy ] = true;
        }
      }
      
      //end 3 & 4

      
      // step 5
      // Initializing w
      w_e = (std::numeric_limits<unsigned>::max)();
      //end 5
      
      
      //step 6
      //Testing for termination
      while( !degree_queue.empty() )
      {
        i = degree_queue.top();       //getting the node with the lowest degree from the degree queue
        degree_queue.pop();           //ereasing the node with the lowest degree from the degree queue
        
        //generating a RLS          
        for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;
        
        breadth_first_search
          (G, i, boost::visitor
           (
             make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
             )
            );
        
        //Calculating depth and width of the rooted level
        h_i = RLS_depth(dist);
        w_i = RLS_max_width(dist, h_i);
        
        //Testing for termination
        if( (h_i > h_s) && (w_i < w_e) ) 
        {
          h_s = h_i;
          s = i;
          while(!degree_queue.empty()) degree_queue.pop();
          new_start = true;         
        }
        else if(w_i < w_e)
        { 
          w_e = w_i;
          e = i;
        }
      }
      //end 6
        
    }while(new_start);
    
    return e;
  }

  //////////////////////////////////////////////////////////////////////////
  // Sloan algorithm with a given starting Vertex.
  //
  // This algorithm requires user to provide a starting vertex to
  // compute Sloan ordering.
  //////////////////////////////////////////////////////////////////////////
  template <class Graph, class OutputIterator,
            class ColorMap, class DegreeMap,
            class PriorityMap, class Weight>
  OutputIterator
  sloan_ordering(Graph& g,
                 typename graph_traits<Graph>::vertex_descriptor s,
                 typename graph_traits<Graph>::vertex_descriptor e,
                 OutputIterator permutation, 
                 ColorMap color, 
                 DegreeMap degree, 
                 PriorityMap priority, 
                 Weight W1, 
                 Weight W2)
  {
    //typedef typename property_traits<DegreeMap>::value_type Degree;
    typedef typename property_traits<PriorityMap>::value_type Degree;
    typedef typename property_traits<ColorMap>::value_type ColorValue;
    typedef color_traits<ColorValue> Color;
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    typedef typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;
    typedef typename graph_traits<Graph>::vertices_size_type size_type;

    typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;

    
    //Creating a std-vector for storing the distance from the end vertex in it
    typename std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(g), 0);
    
    //Wrap a property_map_iterator around the std::iterator
    boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, g)); 
    
    breadth_first_search
      (g, e, visitor
       (
           make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
        )
       );
    
    //Creating a property_map for the indices of a vertex
    typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, g);
    
    //Sets the color and priority to their initial status
    unsigned cdeg;    
    typename graph_traits<Graph>::vertex_iterator ui, ui_end;
    for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
    {
        put(color, *ui, Color::white());
        cdeg=get(degree, *ui)+1;
        put(priority, *ui, W1*dist[index_map[*ui]]-W2*cdeg );  
    }
    
    //Priority list
    typedef indirect_cmp<PriorityMap, std::greater<Degree> > Compare;
    Compare comp(priority);
    std::list<Vertex> priority_list;

    //Some more declarations
    typename graph_traits<Graph>::out_edge_iterator ei, ei_end, ei2, ei2_end;
    Vertex u, v, w;

    put(color, s, Color::green());      //Sets the color of the starting vertex to gray
    priority_list.push_front(s);                 //Puts s into the priority_list
    
    while ( !priority_list.empty() ) 
    {  
      priority_list.sort(comp);         //Orders the elements in the priority list in an ascending manner
      
      u = priority_list.front();           //Accesses the last element in the priority list
      priority_list.pop_front();               //Removes the last element in the priority list
      
      if(get(color, u) == Color::green() )
      {
        //for-loop over all out-edges of vertex u
        for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) 
        {
          v = target(*ei, g);
          
          put( priority, v, get(priority, v) + W2 ); //updates the priority
          
          if (get(color, v) == Color::white() )      //test if the vertex is inactive
          {
            put(color, v, Color::green() );        //giving the vertex a preactive status
            priority_list.push_front(v);                     //writing the vertex in the priority_queue
          }           
        }
      }
      
      //Here starts step 8
      *permutation++ = u;                      //Puts u to the first position in the permutation-vector
      put(color, u, Color::black() );          //Gives u an inactive status
      
      //for loop over all the adjacent vertices of u
      for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
        
        v = target(*ei, g);     
        
        if (get(color, v) == Color::green() ) {      //tests if the vertex is inactive
          
          put(color, v, Color::red() );        //giving the vertex an active status
          put(priority, v, get(priority, v)+W2);  //updates the priority        
          
          //for loop over alll adjacent vertices of v
          for (boost::tie(ei2, ei2_end) = out_edges(v, g); ei2 != ei2_end; ++ei2) {
            w = target(*ei2, g);
            
            if(get(color, w) != Color::black() ) {     //tests if vertex is postactive
              
              put(priority, w, get(priority, w)+W2);  //updates the priority
              
              if(get(color, w) == Color::white() ){
                
                put(color, w, Color::green() );   // gives the vertex a preactive status
                priority_list.push_front(w);           // puts the vertex into the priority queue
                
              } //end if
              
            } //end if
            
          } //end for
          
        } //end if
        
      } //end for
      
    } //end while
    
    
    return permutation;
  }  
  
  /////////////////////////////////////////////////////////////////////////////////////////
  // Same algorithm as before, but without the weights given (taking default weights
  template <class Graph, class OutputIterator,
            class ColorMap, class DegreeMap,
            class PriorityMap>
  OutputIterator
  sloan_ordering(Graph& g,
                 typename graph_traits<Graph>::vertex_descriptor s,
                 typename graph_traits<Graph>::vertex_descriptor e,
                 OutputIterator permutation, 
                 ColorMap color, 
                 DegreeMap degree, 
                 PriorityMap priority)
  {
    return sloan_ordering(g, s, e, permutation, color, degree, priority, WEIGHT1, WEIGHT2); 
  }


  //////////////////////////////////////////////////////////////////////////
  // Sloan algorithm without a given starting Vertex.
  //
  // This algorithm finds a good starting vertex itself to
  // compute Sloan-ordering.
  //////////////////////////////////////////////////////////////////////////
 


  template < class Graph, class OutputIterator, 
             class Color, class Degree,
             class Priority, class Weight>
  inline OutputIterator
  sloan_ordering(Graph& G, 
                 OutputIterator permutation, 
                 Color color, 
                 Degree degree, 
                 Priority priority, 
                 Weight W1, 
                 Weight W2 )
  {
    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
    
    Vertex s, e;
    e = sloan_start_end_vertices(G, s, color, degree);
    
    return sloan_ordering(G, s, e, permutation, color, degree, priority, W1, W2);
  }

  /////////////////////////////////////////////////////////////////////////////////////////
  // Same as before, but without given weights (default weights are taken instead)
  template < class Graph, class OutputIterator, 
             class Color, class Degree,
             class Priority >
  inline OutputIterator
  sloan_ordering(Graph& G, 
                 OutputIterator permutation, 
                 Color color, 
                 Degree degree, 
                 Priority priority)
  { 
    return sloan_ordering(G, permutation, color, degree, priority, WEIGHT1, WEIGHT2);
  }
  
  
} // namespace boost


#endif // BOOST_GRAPH_SLOAN_HPP