williamr@2: //=======================================================================
williamr@2: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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: // Revision History:
williamr@2: //   17 March 2006: Fixed a bug: when updating the degree a vertex 
williamr@2: //                  could be moved to a wrong bucket. (Roman Dementiev) 
williamr@2: //
williamr@2: 
williamr@2: 
williamr@2: 
williamr@2: #ifndef BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
williamr@2: #define BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
williamr@2: /*
williamr@2:    The smallest-last ordering is defined for the loopless graph G with
williamr@2:    vertices a(j), j = 1,2,...,n where a(j) is the j-th column of A and
williamr@2:    with edge (a(i),a(j)) if and only if columns i and j have a
williamr@2:    non-zero in the same row position.  The smallest-last ordering is
williamr@2:    determined recursively by letting list(k), k = n,...,1 be a column
williamr@2:    with least degree in the subgraph spanned by the un-ordered
williamr@2:    columns.
williamr@2:  */
williamr@2: #include <vector>
williamr@2: #include <algorithm>
williamr@2: #include <boost/config.hpp>
williamr@2: #include <boost/graph/graph_traits.hpp>
williamr@2: #include <boost/pending/bucket_sorter.hpp>
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2:   template <class VertexListGraph, class Order, class Degree, class Marker>
williamr@2:   void 
williamr@2:   smallest_last_vertex_ordering(const VertexListGraph& G, Order order, 
williamr@2:                                 Degree degree, Marker marker) {
williamr@2:     typedef typename boost::graph_traits<VertexListGraph> GraphTraits;
williamr@2:     typedef typename GraphTraits::vertex_descriptor Vertex;
williamr@2:     //typedef typename GraphTraits::size_type size_type;
williamr@2:     typedef std::size_t size_type;
williamr@2:     
williamr@2:     const size_type num = num_vertices(G);
williamr@2:     
williamr@2:     typedef typename boost::detail::vertex_property_map<VertexListGraph, vertex_index_t>::type ID;
williamr@2:     typedef bucket_sorter<size_type, Vertex, Degree, ID> BucketSorter;
williamr@2:     
williamr@2:     BucketSorter degree_bucket_sorter(num, num, degree,  
williamr@2:                                       get(vertex_index,G));
williamr@2: 
williamr@2:     smallest_last_vertex_ordering(G, order, degree, marker, degree_bucket_sorter);
williamr@2:   }
williamr@2: 
williamr@2:   template <class VertexListGraph, class Order, class Degree, 
williamr@2:             class Marker, class BucketSorter>
williamr@2:   void 
williamr@2:   smallest_last_vertex_ordering(const VertexListGraph& G, Order order, 
williamr@2:                                 Degree degree, Marker marker,
williamr@2:                                 BucketSorter& degree_buckets) {
williamr@2:     typedef typename boost::graph_traits<VertexListGraph> GraphTraits;
williamr@2:     typedef typename GraphTraits::vertex_descriptor Vertex;
williamr@2:     //typedef typename GraphTraits::size_type size_type;
williamr@2:     typedef std::size_t size_type;
williamr@2: 
williamr@2:     const size_type num = num_vertices(G);
williamr@2:     
williamr@2:     typename GraphTraits::vertex_iterator v, vend;
williamr@2:     for (boost::tie(v, vend) = vertices(G); v != vend; ++v) {
williamr@2:       put(marker, *v, num);
williamr@2:       put(degree, *v, out_degree(*v, G));
williamr@2:       degree_buckets.push(*v);
williamr@2:     }
williamr@2:  
williamr@2:     size_type minimum_degree = 0;
williamr@2:     size_type current_order = num - 1;
williamr@2:     
williamr@2:     while ( 1 ) {
williamr@2:       typedef typename BucketSorter::stack MDStack;
williamr@2:       MDStack minimum_degree_stack = degree_buckets[minimum_degree];
williamr@2:       while (minimum_degree_stack.empty())
williamr@2:         minimum_degree_stack = degree_buckets[++minimum_degree];
williamr@2:       
williamr@2:       Vertex node = minimum_degree_stack.top();
williamr@2:       put(order, current_order, node);
williamr@2:       
williamr@2:       if ( current_order == 0 ) //find all vertices
williamr@2:         break;
williamr@2:       
williamr@2:       minimum_degree_stack.pop();
williamr@2:       put(marker, node, 0); //node has been ordered.
williamr@2:       
williamr@2:       typename GraphTraits::adjacency_iterator v, vend;
williamr@2:       for (boost::tie(v,vend) = adjacent_vertices(node, G); v != vend; ++v)
williamr@2:         
williamr@2:         if ( get(marker,*v) > current_order ) { //*v is unordered vertex
williamr@2:           put(marker, *v, current_order);  //mark the columns adjacent to node
williamr@2: 
williamr@2:           //delete *v from the bucket sorter         
williamr@2:           degree_buckets.remove(*v);
williamr@2:  
williamr@2:           //It is possible minimum degree goes down
williamr@2:           //Here we keep tracking it.
williamr@2:           put(degree, *v, get(degree, *v) - 1); 
williamr@2:           BOOST_USING_STD_MIN();
williamr@2:           minimum_degree = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_degree, get(degree, *v)); 
williamr@2:           
williamr@2:           //reinsert *v in the bucket sorter with the new degree
williamr@2:           degree_buckets.push(*v);
williamr@2:         }
williamr@2: 
williamr@2:       current_order--;
williamr@2:     }
williamr@2:     
williamr@2:     //at this point, order[i] = v_i;
williamr@2:   }
williamr@2:   
williamr@2: }
williamr@2: 
williamr@2: #endif
williamr@2: