boost/graph/smallest_last_ordering.hpp

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009
0010 // Revision History:
0011 //   17 March 2006: Fixed a bug: when updating the degree a vertex
0012 //                  could be moved to a wrong bucket. (Roman Dementiev)
0013 //
0014
0015 #ifndef BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
0016 #define BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
0017 /*
0018    The smallest-last ordering is defined for the loopless graph G with
0019    vertices a(j), j = 1,2,...,n where a(j) is the j-th column of A and
0020    with edge (a(i),a(j)) if and only if columns i and j have a
0021    non-zero in the same row position.  The smallest-last ordering is
0022    determined recursively by letting list(k), k = n,...,1 be a column
0023    with least degree in the subgraph spanned by the un-ordered
0024    columns.
0025  */
0026 #include <vector>
0027 #include <algorithm>
0028 #include <boost/config.hpp>
0029 #include <boost/graph/graph_traits.hpp>
0030 #include <boost/graph/properties.hpp>
0031 #include <boost/pending/bucket_sorter.hpp>
0032
0033 namespace boost
0034 {
0035
0036 template < class VertexListGraph, class Order, class Degree, class Marker >
0037 void smallest_last_vertex_ordering(
0038     const VertexListGraph& G, Order order, Degree degree, Marker marker)
0039 {
0040     typedef typename boost::graph_traits< VertexListGraph > GraphTraits;
0041     typedef typename GraphTraits::vertex_descriptor Vertex;
0042     // typedef typename GraphTraits::size_type size_type;
0043     typedef std::size_t size_type;
0044
0045     const size_type num = num_vertices(G);
0046
0047     typedef
0048         typename boost::property_map< VertexListGraph, vertex_index_t >::type
0049             ID;
0050     typedef bucket_sorter< size_type, Vertex, Degree, ID > BucketSorter;
0051
0052     BucketSorter degree_bucket_sorter(num, num, degree, get(vertex_index, G));
0053
0054     smallest_last_vertex_ordering(
0055         G, order, degree, marker, degree_bucket_sorter);
0056 }
0057
0058 template < class VertexListGraph, class Order, class Degree, class Marker,
0059     class BucketSorter >
0060 void smallest_last_vertex_ordering(const VertexListGraph& G, Order order,
0061     Degree degree, Marker marker, BucketSorter& degree_buckets)
0062 {
0063     typedef typename boost::graph_traits< VertexListGraph > GraphTraits;
0064     typedef typename GraphTraits::vertex_descriptor Vertex;
0065     // typedef typename GraphTraits::size_type size_type;
0066     typedef std::size_t size_type;
0067
0068     const size_type num = num_vertices(G);
0069
0070     typename GraphTraits::vertex_iterator v, vend;
0071     for (boost::tie(v, vend) = vertices(G); v != vend; ++v)
0072     {
0073         put(marker, *v, num);
0074         put(degree, *v, out_degree(*v, G));
0075         degree_buckets.push(*v);
0076     }
0077
0078     size_type minimum_degree = 0;
0079     size_type current_order = num - 1;
0080
0081     while (1)
0082     {
0083         typedef typename BucketSorter::stack MDStack;
0084         MDStack minimum_degree_stack = degree_buckets[minimum_degree];
0085         while (minimum_degree_stack.empty())
0086             minimum_degree_stack = degree_buckets[++minimum_degree];
0087
0088         Vertex node = minimum_degree_stack.top();
0089         put(order, current_order, node);
0090
0091         if (current_order == 0) // find all vertices
0092             break;
0093
0094         minimum_degree_stack.pop();
0095         put(marker, node, 0); // node has been ordered.
0096
0097         typename GraphTraits::adjacency_iterator v, vend;
0098         for (boost::tie(v, vend) = adjacent_vertices(node, G); v != vend; ++v)
0099
0100             if (get(marker, *v) > current_order)
0101             { //*v is unordered vertex
0102                 put(marker, *v,
0103                     current_order); // mark the columns adjacent to node
0104
0105                 // delete *v from the bucket sorter
0106                 degree_buckets.remove(*v);
0107
0108                 // It is possible minimum degree goes down
0109                 // Here we keep tracking it.
0110                 put(degree, *v, get(degree, *v) - 1);
0111                 BOOST_USING_STD_MIN();
0112                 minimum_degree = min BOOST_PREVENT_MACRO_SUBSTITUTION(
0113                     minimum_degree, get(degree, *v));
0114
0115                 // reinsert *v in the bucket sorter with the new degree
0116                 degree_buckets.push(*v);
0117             }
0118
0119         current_order--;
0120     }
0121
0122     // at this point, order[i] = v_i;
0123 }
0124
0125 template < class VertexListGraph, class Order >
0126 void smallest_last_vertex_ordering(const VertexListGraph& G, Order order)
0127 {
0128     typedef typename graph_traits< VertexListGraph >::vertex_descriptor
0129         vertex_descriptor;
0130     typedef typename graph_traits< VertexListGraph >::degree_size_type
0131         degree_size_type;
0132     smallest_last_vertex_ordering(G, order,
0133         make_shared_array_property_map(
0134             num_vertices(G), degree_size_type(0), get(vertex_index, G)),
0135         make_shared_array_property_map(
0136             num_vertices(G), (std::size_t)(0), get(vertex_index, G)));
0137 }
0138
0139 template < class VertexListGraph >
0140 std::vector< typename graph_traits< VertexListGraph >::vertex_descriptor >
0141 smallest_last_vertex_ordering(const VertexListGraph& G)
0142 {
0143     std::vector< typename graph_traits< VertexListGraph >::vertex_descriptor >
0144         o(num_vertices(G));
0145     smallest_last_vertex_ordering(G,
0146         make_iterator_property_map(
0147             o.begin(), typed_identity_property_map< std::size_t >()));
0148     return o;
0149 }
0150 }
0151
0152 #endif