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