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 +