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