epoc32/include/stdapis/boost/graph/smallest_last_ordering.hpp
branchSymbian2
changeset 2 2fe1408b6811
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/smallest_last_ordering.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,122 @@
     1.4 +//=======================================================================
     1.5 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     1.6 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     1.7 +//
     1.8 +// Distributed under the Boost Software License, Version 1.0. (See
     1.9 +// accompanying file LICENSE_1_0.txt or copy at
    1.10 +// http://www.boost.org/LICENSE_1_0.txt)
    1.11 +//=======================================================================
    1.12 +
    1.13 +// Revision History:
    1.14 +//   17 March 2006: Fixed a bug: when updating the degree a vertex 
    1.15 +//                  could be moved to a wrong bucket. (Roman Dementiev) 
    1.16 +//
    1.17 +
    1.18 +
    1.19 +
    1.20 +#ifndef BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
    1.21 +#define BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
    1.22 +/*
    1.23 +   The smallest-last ordering is defined for the loopless graph G with
    1.24 +   vertices a(j), j = 1,2,...,n where a(j) is the j-th column of A and
    1.25 +   with edge (a(i),a(j)) if and only if columns i and j have a
    1.26 +   non-zero in the same row position.  The smallest-last ordering is
    1.27 +   determined recursively by letting list(k), k = n,...,1 be a column
    1.28 +   with least degree in the subgraph spanned by the un-ordered
    1.29 +   columns.
    1.30 + */
    1.31 +#include <vector>
    1.32 +#include <algorithm>
    1.33 +#include <boost/config.hpp>
    1.34 +#include <boost/graph/graph_traits.hpp>
    1.35 +#include <boost/pending/bucket_sorter.hpp>
    1.36 +
    1.37 +namespace boost {
    1.38 +
    1.39 +  template <class VertexListGraph, class Order, class Degree, class Marker>
    1.40 +  void 
    1.41 +  smallest_last_vertex_ordering(const VertexListGraph& G, Order order, 
    1.42 +                                Degree degree, Marker marker) {
    1.43 +    typedef typename boost::graph_traits<VertexListGraph> GraphTraits;
    1.44 +    typedef typename GraphTraits::vertex_descriptor Vertex;
    1.45 +    //typedef typename GraphTraits::size_type size_type;
    1.46 +    typedef std::size_t size_type;
    1.47 +    
    1.48 +    const size_type num = num_vertices(G);
    1.49 +    
    1.50 +    typedef typename boost::detail::vertex_property_map<VertexListGraph, vertex_index_t>::type ID;
    1.51 +    typedef bucket_sorter<size_type, Vertex, Degree, ID> BucketSorter;
    1.52 +    
    1.53 +    BucketSorter degree_bucket_sorter(num, num, degree,  
    1.54 +                                      get(vertex_index,G));
    1.55 +
    1.56 +    smallest_last_vertex_ordering(G, order, degree, marker, degree_bucket_sorter);
    1.57 +  }
    1.58 +
    1.59 +  template <class VertexListGraph, class Order, class Degree, 
    1.60 +            class Marker, class BucketSorter>
    1.61 +  void 
    1.62 +  smallest_last_vertex_ordering(const VertexListGraph& G, Order order, 
    1.63 +                                Degree degree, Marker marker,
    1.64 +                                BucketSorter& degree_buckets) {
    1.65 +    typedef typename boost::graph_traits<VertexListGraph> GraphTraits;
    1.66 +    typedef typename GraphTraits::vertex_descriptor Vertex;
    1.67 +    //typedef typename GraphTraits::size_type size_type;
    1.68 +    typedef std::size_t size_type;
    1.69 +
    1.70 +    const size_type num = num_vertices(G);
    1.71 +    
    1.72 +    typename GraphTraits::vertex_iterator v, vend;
    1.73 +    for (boost::tie(v, vend) = vertices(G); v != vend; ++v) {
    1.74 +      put(marker, *v, num);
    1.75 +      put(degree, *v, out_degree(*v, G));
    1.76 +      degree_buckets.push(*v);
    1.77 +    }
    1.78 + 
    1.79 +    size_type minimum_degree = 0;
    1.80 +    size_type current_order = num - 1;
    1.81 +    
    1.82 +    while ( 1 ) {
    1.83 +      typedef typename BucketSorter::stack MDStack;
    1.84 +      MDStack minimum_degree_stack = degree_buckets[minimum_degree];
    1.85 +      while (minimum_degree_stack.empty())
    1.86 +        minimum_degree_stack = degree_buckets[++minimum_degree];
    1.87 +      
    1.88 +      Vertex node = minimum_degree_stack.top();
    1.89 +      put(order, current_order, node);
    1.90 +      
    1.91 +      if ( current_order == 0 ) //find all vertices
    1.92 +        break;
    1.93 +      
    1.94 +      minimum_degree_stack.pop();
    1.95 +      put(marker, node, 0); //node has been ordered.
    1.96 +      
    1.97 +      typename GraphTraits::adjacency_iterator v, vend;
    1.98 +      for (boost::tie(v,vend) = adjacent_vertices(node, G); v != vend; ++v)
    1.99 +        
   1.100 +        if ( get(marker,*v) > current_order ) { //*v is unordered vertex
   1.101 +          put(marker, *v, current_order);  //mark the columns adjacent to node
   1.102 +
   1.103 +          //delete *v from the bucket sorter         
   1.104 +          degree_buckets.remove(*v);
   1.105 + 
   1.106 +          //It is possible minimum degree goes down
   1.107 +          //Here we keep tracking it.
   1.108 +          put(degree, *v, get(degree, *v) - 1); 
   1.109 +          BOOST_USING_STD_MIN();
   1.110 +          minimum_degree = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_degree, get(degree, *v)); 
   1.111 +          
   1.112 +          //reinsert *v in the bucket sorter with the new degree
   1.113 +          degree_buckets.push(*v);
   1.114 +        }
   1.115 +
   1.116 +      current_order--;
   1.117 +    }
   1.118 +    
   1.119 +    //at this point, order[i] = v_i;
   1.120 +  }
   1.121 +  
   1.122 +}
   1.123 +
   1.124 +#endif
   1.125 +