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 #ifndef BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
16 #define BOOST_SMALLEST_LAST_VERTEX_ORDERING_HPP
17 /*
18 The smallest-last ordering is defined for the loopless graph G with
19 vertices a(j), j = 1,2,...,n where a(j) is the j-th column of A and
20 with edge (a(i),a(j)) if and only if columns i and j have a
21 non-zero in the same row position. The smallest-last ordering is
22 determined recursively by letting list(k), k = n,...,1 be a column
23 with least degree in the subgraph spanned by the un-ordered
24 columns.
25 */
26 #include <vector>
27 #include <algorithm>
28 #include <boost/config.hpp>
29 #include <boost/graph/graph_traits.hpp>
30 #include <boost/graph/properties.hpp>
31 #include <boost/pending/bucket_sorter.hpp>
32
33 namespace boost
34 {
35
36 template < class VertexListGraph, class Order, class Degree, class Marker >
smallest_last_vertex_ordering(const VertexListGraph & G,Order order,Degree degree,Marker marker)37 void smallest_last_vertex_ordering(
38 const VertexListGraph& G, Order order, Degree degree, Marker marker)
39 {
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
48 typename boost::property_map< VertexListGraph, vertex_index_t >::type
49 ID;
50 typedef bucket_sorter< size_type, Vertex, Degree, ID > BucketSorter;
51
52 BucketSorter degree_bucket_sorter(num, num, degree, get(vertex_index, G));
53
54 smallest_last_vertex_ordering(
55 G, order, degree, marker, degree_bucket_sorter);
56 }
57
58 template < class VertexListGraph, class Order, class Degree, class Marker,
59 class BucketSorter >
smallest_last_vertex_ordering(const VertexListGraph & G,Order order,Degree degree,Marker marker,BucketSorter & degree_buckets)60 void smallest_last_vertex_ordering(const VertexListGraph& G, Order order,
61 Degree degree, Marker marker, BucketSorter& degree_buckets)
62 {
63 typedef typename boost::graph_traits< VertexListGraph > GraphTraits;
64 typedef typename GraphTraits::vertex_descriptor Vertex;
65 // typedef typename GraphTraits::size_type size_type;
66 typedef std::size_t size_type;
67
68 const size_type num = num_vertices(G);
69
70 typename GraphTraits::vertex_iterator v, vend;
71 for (boost::tie(v, vend) = vertices(G); v != vend; ++v)
72 {
73 put(marker, *v, num);
74 put(degree, *v, out_degree(*v, G));
75 degree_buckets.push(*v);
76 }
77
78 size_type minimum_degree = 0;
79 size_type current_order = num - 1;
80
81 while (1)
82 {
83 typedef typename BucketSorter::stack MDStack;
84 MDStack minimum_degree_stack = degree_buckets[minimum_degree];
85 while (minimum_degree_stack.empty())
86 minimum_degree_stack = degree_buckets[++minimum_degree];
87
88 Vertex node = minimum_degree_stack.top();
89 put(order, current_order, node);
90
91 if (current_order == 0) // find all vertices
92 break;
93
94 minimum_degree_stack.pop();
95 put(marker, node, 0); // node has been ordered.
96
97 typename GraphTraits::adjacency_iterator v, vend;
98 for (boost::tie(v, vend) = adjacent_vertices(node, G); v != vend; ++v)
99
100 if (get(marker, *v) > current_order)
101 { //*v is unordered vertex
102 put(marker, *v,
103 current_order); // mark the columns adjacent to node
104
105 // delete *v from the bucket sorter
106 degree_buckets.remove(*v);
107
108 // It is possible minimum degree goes down
109 // Here we keep tracking it.
110 put(degree, *v, get(degree, *v) - 1);
111 BOOST_USING_STD_MIN();
112 minimum_degree = min BOOST_PREVENT_MACRO_SUBSTITUTION(
113 minimum_degree, get(degree, *v));
114
115 // reinsert *v in the bucket sorter with the new degree
116 degree_buckets.push(*v);
117 }
118
119 current_order--;
120 }
121
122 // at this point, order[i] = v_i;
123 }
124
125 template < class VertexListGraph, class Order >
smallest_last_vertex_ordering(const VertexListGraph & G,Order order)126 void smallest_last_vertex_ordering(const VertexListGraph& G, Order order)
127 {
128 typedef typename graph_traits< VertexListGraph >::vertex_descriptor
129 vertex_descriptor;
130 typedef typename graph_traits< VertexListGraph >::degree_size_type
131 degree_size_type;
132 smallest_last_vertex_ordering(G, order,
133 make_shared_array_property_map(
134 num_vertices(G), degree_size_type(0), get(vertex_index, G)),
135 make_shared_array_property_map(
136 num_vertices(G), (std::size_t)(0), get(vertex_index, G)));
137 }
138
139 template < class VertexListGraph >
140 std::vector< typename graph_traits< VertexListGraph >::vertex_descriptor >
smallest_last_vertex_ordering(const VertexListGraph & G)141 smallest_last_vertex_ordering(const VertexListGraph& G)
142 {
143 std::vector< typename graph_traits< VertexListGraph >::vertex_descriptor >
144 o(num_vertices(G));
145 smallest_last_vertex_ordering(G,
146 make_iterator_property_map(
147 o.begin(), typed_identity_property_map< std::size_t >()));
148 return o;
149 }
150 }
151
152 #endif
153