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