ceph/src/boost/boost/graph/smallest_last_ordering.hpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9
  10 // Revision History:
  11 //   17 March 2006: Fixed a bug: when updating the degree a vertex
  12 //                  could be moved to a wrong bucket. (Roman Dementiev)
  13 //
  14
  15
  16
  17 #ifndef BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
  18 #define BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
  19 /*
  20    The smallest-last ordering is defined for the loopless graph G with
  21    vertices a(j), j = 1,2,...,n where a(j) is the j-th column of A and
  22    with edge (a(i),a(j)) if and only if columns i and j have a
  23    non-zero in the same row position.  The smallest-last ordering is
  24    determined recursively by letting list(k), k = n,...,1 be a column
  25    with least degree in the subgraph spanned by the un-ordered
  26    columns.
  27  */
  28 #include <vector>
  29 #include <algorithm>
  30 #include <boost/config.hpp>
  31 #include <boost/graph/graph_traits.hpp>
  32 #include <boost/graph/properties.hpp>
  33 #include <boost/pending/bucket_sorter.hpp>
  34
  35 namespace boost {
  36
  37   template <class VertexListGraph, class Order, class Degree, class Marker>
  38   void
  39   smallest_last_vertex_ordering(const VertexListGraph& G, Order order,
  40                                 Degree degree, Marker marker) {
  41     typedef typename boost::graph_traits<VertexListGraph> GraphTraits;
  42     typedef typename GraphTraits::vertex_descriptor Vertex;
  43     //typedef typename GraphTraits::size_type size_type;
  44     typedef std::size_t size_type;
  45
  46     const size_type num = num_vertices(G);
  47
  48     typedef typename boost::property_map<VertexListGraph, vertex_index_t>::type ID;
  49     typedef bucket_sorter<size_type, Vertex, Degree, ID> BucketSorter;
  50
  51     BucketSorter degree_bucket_sorter(num, num, degree,
  52                                       get(vertex_index,G));
  53
  54     smallest_last_vertex_ordering(G, order, degree, marker, degree_bucket_sorter);
  55   }
  56
  57   template <class VertexListGraph, class Order, class Degree,
  58             class Marker, class BucketSorter>
  59   void
  60   smallest_last_vertex_ordering(const VertexListGraph& G, Order order,
  61                                 Degree degree, Marker marker,
  62                                 BucketSorter& degree_buckets) {
  63     typedef typename boost::graph_traits<VertexListGraph> GraphTraits;
  64     typedef typename GraphTraits::vertex_descriptor Vertex;
  65     //typedef typename GraphTraits::size_type size_type;
  66     typedef std::size_t size_type;
  67
  68     const size_type num = num_vertices(G);
  69
  70     typename GraphTraits::vertex_iterator v, vend;
  71     for (boost::tie(v, vend) = vertices(G); v != vend; ++v) {
  72       put(marker, *v, num);
  73       put(degree, *v, out_degree(*v, G));
  74       degree_buckets.push(*v);
  75     }
  76
  77     size_type minimum_degree = 0;
  78     size_type current_order = num - 1;
  79
  80     while ( 1 ) {
  81       typedef typename BucketSorter::stack MDStack;
  82       MDStack minimum_degree_stack = degree_buckets[minimum_degree];
  83       while (minimum_degree_stack.empty())
  84         minimum_degree_stack = degree_buckets[++minimum_degree];
  85
  86       Vertex node = minimum_degree_stack.top();
  87       put(order, current_order, node);
  88
  89       if ( current_order == 0 ) //find all vertices
  90         break;
  91
  92       minimum_degree_stack.pop();
  93       put(marker, node, 0); //node has been ordered.
  94
  95       typename GraphTraits::adjacency_iterator v, vend;
  96       for (boost::tie(v,vend) = adjacent_vertices(node, G); v != vend; ++v)
  97
  98         if ( get(marker,*v) > current_order ) { //*v is unordered vertex
  99           put(marker, *v, current_order);  //mark the columns adjacent to node
 100
 101           //delete *v from the bucket sorter
 102           degree_buckets.remove(*v);
 103
 104           //It is possible minimum degree goes down
 105           //Here we keep tracking it.
 106           put(degree, *v, get(degree, *v) - 1);
 107           BOOST_USING_STD_MIN();
 108           minimum_degree = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_degree, get(degree, *v));
 109
 110           //reinsert *v in the bucket sorter with the new degree
 111           degree_buckets.push(*v);
 112         }
 113
 114       current_order--;
 115     }
 116
 117     //at this point, order[i] = v_i;
 118   }
 119
 120   template <class VertexListGraph, class Order>
 121   void
 122   smallest_last_vertex_ordering(const VertexListGraph& G, Order order) {
 123     typedef typename graph_traits<VertexListGraph>::vertex_descriptor vertex_descriptor;
 124     typedef typename graph_traits<VertexListGraph>::degree_size_type degree_size_type;
 125     smallest_last_vertex_ordering(G, order,
 126                                   make_shared_array_property_map(num_vertices(G), degree_size_type(0), get(vertex_index, G)),
 127                                   make_shared_array_property_map(num_vertices(G), (std::size_t)(0), get(vertex_index, G)));
 128   }
 129
 130   template <class VertexListGraph>
 131   std::vector<typename graph_traits<VertexListGraph>::vertex_descriptor>
 132   smallest_last_vertex_ordering(const VertexListGraph& G) {
 133     std::vector<typename graph_traits<VertexListGraph>::vertex_descriptor> o(num_vertices(G));
 134     smallest_last_vertex_ordering(G, make_iterator_property_map(o.begin(), typed_identity_property_map<std::size_t>()));
 135     return o;
 136   }
 137 }
 138
 139 #endif
 140