boost/graph/smallest_last_ordering.hpp

//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// 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)
//=======================================================================

// Revision History:
//   17 March 2006: Fixed a bug: when updating the degree a vertex 
//                  could be moved to a wrong bucket. (Roman Dementiev) 
//



#ifndef BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
#define BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
/*
   The smallest-last ordering is defined for the loopless graph G with
   vertices a(j), j = 1,2,...,n where a(j) is the j-th column of A and
   with edge (a(i),a(j)) if and only if columns i and j have a
   non-zero in the same row position.  The smallest-last ordering is
   determined recursively by letting list(k), k = n,...,1 be a column
   with least degree in the subgraph spanned by the un-ordered
   columns.
 */
#include <vector>
#include <algorithm>
#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/pending/bucket_sorter.hpp>

namespace boost {

  template <class VertexListGraph, class Order, class Degree, class Marker>
  void 
  smallest_last_vertex_ordering(const VertexListGraph& G, Order order, 
                                Degree degree, Marker marker) {
    typedef typename boost::graph_traits<VertexListGraph> GraphTraits;
    typedef typename GraphTraits::vertex_descriptor Vertex;
    //typedef typename GraphTraits::size_type size_type;
    typedef std::size_t size_type;
    
    const size_type num = num_vertices(G);
    
    typedef typename boost::detail::vertex_property_map<VertexListGraph, vertex_index_t>::type ID;
    typedef bucket_sorter<size_type, Vertex, Degree, ID> BucketSorter;
    
    BucketSorter degree_bucket_sorter(num, num, degree,  
                                      get(vertex_index,G));

    smallest_last_vertex_ordering(G, order, degree, marker, degree_bucket_sorter);
  }

  template <class VertexListGraph, class Order, class Degree, 
            class Marker, class BucketSorter>
  void 
  smallest_last_vertex_ordering(const VertexListGraph& G, Order order, 
                                Degree degree, Marker marker,
                                BucketSorter& degree_buckets) {
    typedef typename boost::graph_traits<VertexListGraph> GraphTraits;
    typedef typename GraphTraits::vertex_descriptor Vertex;
    //typedef typename GraphTraits::size_type size_type;
    typedef std::size_t size_type;

    const size_type num = num_vertices(G);
    
    typename GraphTraits::vertex_iterator v, vend;
    for (boost::tie(v, vend) = vertices(G); v != vend; ++v) {
      put(marker, *v, num);
      put(degree, *v, out_degree(*v, G));
      degree_buckets.push(*v);
    }
 
    size_type minimum_degree = 0;
    size_type current_order = num - 1;
    
    while ( 1 ) {
      typedef typename BucketSorter::stack MDStack;
      MDStack minimum_degree_stack = degree_buckets[minimum_degree];
      while (minimum_degree_stack.empty())
        minimum_degree_stack = degree_buckets[++minimum_degree];
      
      Vertex node = minimum_degree_stack.top();
      put(order, current_order, node);
      
      if ( current_order == 0 ) //find all vertices
        break;
      
      minimum_degree_stack.pop();
      put(marker, node, 0); //node has been ordered.
      
      typename GraphTraits::adjacency_iterator v, vend;
      for (boost::tie(v,vend) = adjacent_vertices(node, G); v != vend; ++v)
        
        if ( get(marker,*v) > current_order ) { //*v is unordered vertex
          put(marker, *v, current_order);  //mark the columns adjacent to node

          //delete *v from the bucket sorter         
          degree_buckets.remove(*v);
 
          //It is possible minimum degree goes down
          //Here we keep tracking it.
          put(degree, *v, get(degree, *v) - 1); 
          BOOST_USING_STD_MIN();
          minimum_degree = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_degree, get(degree, *v)); 
          
          //reinsert *v in the bucket sorter with the new degree
          degree_buckets.push(*v);
        }

      current_order--;
    }
    
    //at this point, order[i] = v_i;
  }
  
}

#endif