//=======================================================================

 // 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