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