sloan_ordering.hpp

support vector clustering for vc++

//
//=======================================================================
// Copyright 2002 Marc Wintermantel ([e-mail])
// 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
#define MAXINT 2147483647       //Maximum value for a 32bit integer

#include <boost/config.hpp>
#include <vector>
#include <queue>
#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.hpp>
#include <algorithm>
#include <utility>
#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 (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 (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 = MAXINT;
      //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