[857] | 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 | #ifndef BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
|
---|
| 10 | #define BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
|
---|
| 11 | /*
|
---|
| 12 | The smallest-last ordering is defined for the loopless graph G with
|
---|
| 13 | vertices a(j), j = 1,2,...,n where a(j) is the j-th column of A and
|
---|
| 14 | with edge (a(i),a(j)) if and only if columns i and j have a
|
---|
| 15 | non-zero in the same row position. The smallest-last ordering is
|
---|
| 16 | determined recursively by letting list(k), k = n,...,1 be a column
|
---|
| 17 | with least degree in the subgraph spanned by the un-ordered
|
---|
| 18 | columns.
|
---|
| 19 | */
|
---|
| 20 | #include <vector>
|
---|
| 21 | #include <algorithm>
|
---|
| 22 | #include <boost/config.hpp>
|
---|
| 23 | #include <boost/graph/graph_traits.hpp>
|
---|
| 24 | #include <boost/pending/bucket_sorter.hpp>
|
---|
| 25 |
|
---|
| 26 | namespace boost {
|
---|
| 27 |
|
---|
| 28 | template <class VertexListGraph, class Order, class Degree, class Marker>
|
---|
| 29 | void
|
---|
| 30 | smallest_last_vertex_ordering(const VertexListGraph& G, Order order,
|
---|
| 31 | Degree degree, Marker marker) {
|
---|
| 32 | typedef typename graph_traits<VertexListGraph> GraphTraits;
|
---|
| 33 | typedef typename GraphTraits::vertex_descriptor Vertex;
|
---|
| 34 | //typedef typename GraphTraits::size_type size_type;
|
---|
| 35 | typedef std::size_t size_type;
|
---|
| 36 |
|
---|
| 37 | const size_type num = num_vertices(G);
|
---|
| 38 |
|
---|
| 39 | typedef typename vertex_property_map<VertexListGraph, vertex_index_t>::type ID;
|
---|
| 40 | typedef bucket_sorter<size_type, Vertex, Degree, ID> BucketSorter;
|
---|
| 41 |
|
---|
| 42 | BucketSorter degree_bucket_sorter(num, num, degree,
|
---|
| 43 | get_vertex_property(G, vertex_index));
|
---|
| 44 |
|
---|
| 45 | smallest_last_vertex_ordering(G, order, degree, marker, degree_bucket_sorter);
|
---|
| 46 | }
|
---|
| 47 |
|
---|
| 48 | template <class VertexListGraph, class Order, class Degree,
|
---|
| 49 | class Marker, class BucketSorter>
|
---|
| 50 | void
|
---|
| 51 | smallest_last_vertex_ordering(const VertexListGraph& G, Order order,
|
---|
| 52 | Degree degree, Marker marker,
|
---|
| 53 | BucketSorter& degree_buckets) {
|
---|
| 54 | typedef typename graph_traits<VertexListGraph> GraphTraits;
|
---|
| 55 | typedef typename GraphTraits::vertex_descriptor Vertex;
|
---|
| 56 | //typedef typename GraphTraits::size_type size_type;
|
---|
| 57 | typedef std::size_t size_type;
|
---|
| 58 |
|
---|
| 59 | const size_type num = num_vertices(G);
|
---|
| 60 |
|
---|
| 61 | typename GraphTraits::vertex_iterator v, vend;
|
---|
| 62 | for (boost::tie(v, vend) = vertices(G); v != vend; ++v) {
|
---|
| 63 | put(marker, *v, num);
|
---|
| 64 | put(degree, *v, out_degree(*v, G));
|
---|
| 65 | degree_buckets.push(*v);
|
---|
| 66 | }
|
---|
| 67 |
|
---|
| 68 | size_type minimum_degree = 1;
|
---|
| 69 | size_type current_order = num - 1;
|
---|
| 70 |
|
---|
| 71 | while ( 1 ) {
|
---|
| 72 | typedef typename BucketSorter::stack MDStack;
|
---|
| 73 | MDStack minimum_degree_stack = degree_buckets[minimum_degree];
|
---|
| 74 | while (minimum_degree_stack.empty())
|
---|
| 75 | minimum_degree_stack = degree_buckets[++minimum_degree];
|
---|
| 76 |
|
---|
| 77 | Vertex node = minimum_degree_stack.top();
|
---|
| 78 | put(order, current_order, node);
|
---|
| 79 |
|
---|
| 80 | if ( current_order == 0 ) //find all vertices
|
---|
| 81 | break;
|
---|
| 82 |
|
---|
| 83 | minimum_degree_stack.pop();
|
---|
| 84 | put(marker, node, 0); //node has been ordered.
|
---|
| 85 |
|
---|
| 86 | typename GraphTraits::adjacency_iterator v, vend;
|
---|
| 87 | for (boost::tie(v,vend) = adjacent_vertices(node, G); v != vend; ++v)
|
---|
| 88 |
|
---|
| 89 | if ( get(marker,*v) > current_order ) { //*v is unordered vertex
|
---|
| 90 | put(marker, *v, current_order); //mark the columns adjacent to node
|
---|
| 91 |
|
---|
| 92 | //It is possible minimum degree goes down
|
---|
| 93 | //Here we keep tracking it.
|
---|
| 94 | put(degree, *v, get(degree, *v) - 1);
|
---|
| 95 | BOOST_USING_STD_MIN();
|
---|
| 96 | minimum_degree = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_degree, get(degree, *v));
|
---|
| 97 |
|
---|
| 98 | //update the position of *v in the bucket sorter
|
---|
| 99 | degree_buckets.update(*v);
|
---|
| 100 | }
|
---|
| 101 |
|
---|
| 102 | current_order--;
|
---|
| 103 | }
|
---|
| 104 |
|
---|
| 105 | //at this point, order[i] = v_i;
|
---|
| 106 | }
|
---|
| 107 |
|
---|
| 108 | }
|
---|
| 109 |
|
---|
| 110 | #endif
|
---|
| 111 |
|
---|