1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Copyright 2004, 2005 Trustees of Indiana University
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
// Doug Gregor, D. Kevin McGrath
//
// 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)
//=======================================================================//
#ifndef BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
#define BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
#include <boost/config.hpp>
#include <vector>
#include <queue>
#include <boost/pending/queue.hpp>
#include <boost/pending/mutable_queue.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/properties.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/bind.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/depth_first_search.hpp>
namespace boost {
namespace sparse {
// rcm_queue
//
// This is a custom queue type used in the
// *_ordering algorithms.
// In addition to the normal queue operations, the
// rcm_queue provides:
//
// int eccentricity() const;
// value_type spouse() const;
//
// yes, it's a bad name...but it works, so use it
template < class Vertex, class DegreeMap,
class Container = std::deque<Vertex> >
class rcm_queue : public std::queue<Vertex, Container> {
typedef std::queue<Vertex> base;
public:
typedef typename base::value_type value_type;
typedef typename base::size_type size_type;
/* SGI queue has not had a contructor queue(const Container&) */
inline rcm_queue(DegreeMap deg)
: _size(0), Qsize(1), eccen(-1), degree(deg) { }
inline void pop() {
if ( !_size )
Qsize = base::size();
base::pop();
if ( _size == Qsize-1 ) {
_size = 0;
++eccen;
} else
++_size;
}
inline value_type& front() {
value_type& u = base::front();
if ( _size == 0 )
w = u;
else if (get(degree,u) < get(degree,w) )
w = u;
return u;
}
inline const value_type& front() const {
const value_type& u = base::front();
if ( _size == 0 )
w = u;
else if (get(degree,u) < get(degree,w) )
w = u;
return u;
}
inline value_type& top() { return front(); }
inline const value_type& top() const { return front(); }
inline size_type size() const { return base::size(); }
inline size_type eccentricity() const { return eccen; }
inline value_type spouse() const { return w; }
protected:
size_type _size;
size_type Qsize;
int eccen;
mutable value_type w;
DegreeMap degree;
};
template <typename Tp, typename Sequence = std::deque<Tp> >
class sparse_ordering_queue : public boost::queue<Tp, Sequence>{
public:
typedef typename Sequence::iterator iterator;
typedef typename Sequence::reverse_iterator reverse_iterator;
typedef queue<Tp,Sequence> base;
typedef typename Sequence::size_type size_type;
inline iterator begin() { return this->c.begin(); }
inline reverse_iterator rbegin() { return this->c.rbegin(); }
inline iterator end() { return this->c.end(); }
inline reverse_iterator rend() { return this->c.rend(); }
inline Tp &operator[](int n) { return this->c[n]; }
inline size_type size() {return this->c.size(); }
protected:
//nothing
};
} // namespace sparse
// Compute Pseudo peripheral
//
// To compute an approximated peripheral for a given vertex.
// Used in <tt>king_ordering</tt> algorithm.
//
template <class Graph, class Vertex, class ColorMap, class DegreeMap>
Vertex
pseudo_peripheral_pair(Graph const& G, const Vertex& u, int& ecc,
ColorMap color, DegreeMap degree)
{
typedef typename property_traits<ColorMap>::value_type ColorValue;
typedef color_traits<ColorValue> Color;
sparse::rcm_queue<Vertex, DegreeMap> Q(degree);
typename boost::graph_traits<Graph>::vertex_iterator ui, ui_end;
for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
if (get(color, *ui) != Color::red()) put(color, *ui, Color::white());
breadth_first_visit(G, u, buffer(Q).color_map(color));
ecc = Q.eccentricity();
return Q.spouse();
}
// Find a good starting node
//
// This is to find a good starting node for the
// king_ordering algorithm. "good" is in the sense
// of the ordering generated by RCM.
//
template <class Graph, class Vertex, class Color, class Degree>
Vertex find_starting_node(Graph const& G, Vertex r, Color color, Degree degree)
{
Vertex x, y;
int eccen_r, eccen_x;
x = pseudo_peripheral_pair(G, r, eccen_r, color, degree);
y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
while (eccen_x > eccen_r) {
r = x;
eccen_r = eccen_x;
x = y;
y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
}
return x;
}
template <typename Graph>
class out_degree_property_map
: public put_get_helper<typename graph_traits<Graph>::degree_size_type,
out_degree_property_map<Graph> >
{
public:
typedef typename graph_traits<Graph>::vertex_descriptor key_type;
typedef typename graph_traits<Graph>::degree_size_type value_type;
typedef value_type reference;
typedef readable_property_map_tag category;
out_degree_property_map(const Graph& g) : m_g(g) { }
value_type operator[](const key_type& v) const {
return out_degree(v, m_g);
}
private:
const Graph& m_g;
};
template <typename Graph>
inline out_degree_property_map<Graph>
make_out_degree_map(const Graph& g) {
return out_degree_property_map<Graph>(g);
}
} // namespace boost
#endif // BOOST_GRAPH_KING_HPP
|
