kpeter@758
|
1 |
/* -*- C++ -*-
|
kpeter@758
|
2 |
*
|
kpeter@758
|
3 |
* This file is a part of LEMON, a generic C++ optimization library
|
kpeter@758
|
4 |
*
|
kpeter@758
|
5 |
* Copyright (C) 2003-2008
|
kpeter@758
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
kpeter@758
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
kpeter@758
|
8 |
*
|
kpeter@758
|
9 |
* Permission to use, modify and distribute this software is granted
|
kpeter@758
|
10 |
* provided that this copyright notice appears in all copies. For
|
kpeter@758
|
11 |
* precise terms see the accompanying LICENSE file.
|
kpeter@758
|
12 |
*
|
kpeter@758
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
kpeter@758
|
14 |
* express or implied, and with no claim as to its suitability for any
|
kpeter@758
|
15 |
* purpose.
|
kpeter@758
|
16 |
*
|
kpeter@758
|
17 |
*/
|
kpeter@758
|
18 |
|
kpeter@758
|
19 |
#ifndef LEMON_MIN_MEAN_CYCLE_H
|
kpeter@758
|
20 |
#define LEMON_MIN_MEAN_CYCLE_H
|
kpeter@758
|
21 |
|
kpeter@758
|
22 |
/// \ingroup shortest_path
|
kpeter@758
|
23 |
///
|
kpeter@758
|
24 |
/// \file
|
kpeter@758
|
25 |
/// \brief Howard's algorithm for finding a minimum mean cycle.
|
kpeter@758
|
26 |
|
kpeter@758
|
27 |
#include <vector>
|
kpeter@758
|
28 |
#include <lemon/core.h>
|
kpeter@758
|
29 |
#include <lemon/path.h>
|
kpeter@758
|
30 |
#include <lemon/tolerance.h>
|
kpeter@758
|
31 |
#include <lemon/connectivity.h>
|
kpeter@758
|
32 |
|
kpeter@758
|
33 |
namespace lemon {
|
kpeter@758
|
34 |
|
kpeter@758
|
35 |
/// \addtogroup shortest_path
|
kpeter@758
|
36 |
/// @{
|
kpeter@758
|
37 |
|
kpeter@758
|
38 |
/// \brief Implementation of Howard's algorithm for finding a minimum
|
kpeter@758
|
39 |
/// mean cycle.
|
kpeter@758
|
40 |
///
|
kpeter@758
|
41 |
/// \ref MinMeanCycle implements Howard's algorithm for finding a
|
kpeter@758
|
42 |
/// directed cycle of minimum mean length (cost) in a digraph.
|
kpeter@758
|
43 |
///
|
kpeter@758
|
44 |
/// \tparam GR The type of the digraph the algorithm runs on.
|
kpeter@758
|
45 |
/// \tparam LEN The type of the length map. The default
|
kpeter@758
|
46 |
/// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
|
kpeter@758
|
47 |
///
|
kpeter@758
|
48 |
/// \warning \c LEN::Value must be convertible to \c double.
|
kpeter@758
|
49 |
#ifdef DOXYGEN
|
kpeter@758
|
50 |
template <typename GR, typename LEN>
|
kpeter@758
|
51 |
#else
|
kpeter@758
|
52 |
template < typename GR,
|
kpeter@758
|
53 |
typename LEN = typename GR::template ArcMap<int> >
|
kpeter@758
|
54 |
#endif
|
kpeter@758
|
55 |
class MinMeanCycle
|
kpeter@758
|
56 |
{
|
kpeter@758
|
57 |
public:
|
kpeter@758
|
58 |
|
kpeter@758
|
59 |
/// The type of the digraph the algorithm runs on
|
kpeter@758
|
60 |
typedef GR Digraph;
|
kpeter@758
|
61 |
/// The type of the length map
|
kpeter@758
|
62 |
typedef LEN LengthMap;
|
kpeter@758
|
63 |
/// The type of the arc lengths
|
kpeter@758
|
64 |
typedef typename LengthMap::Value Value;
|
kpeter@758
|
65 |
/// The type of the paths
|
kpeter@758
|
66 |
typedef lemon::Path<Digraph> Path;
|
kpeter@758
|
67 |
|
kpeter@758
|
68 |
private:
|
kpeter@758
|
69 |
|
kpeter@758
|
70 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
|
kpeter@758
|
71 |
|
kpeter@758
|
72 |
// The digraph the algorithm runs on
|
kpeter@758
|
73 |
const Digraph &_gr;
|
kpeter@758
|
74 |
// The length of the arcs
|
kpeter@758
|
75 |
const LengthMap &_length;
|
kpeter@758
|
76 |
|
kpeter@760
|
77 |
// Data for the found cycles
|
kpeter@760
|
78 |
bool _curr_found, _best_found;
|
kpeter@760
|
79 |
Value _curr_length, _best_length;
|
kpeter@760
|
80 |
int _curr_size, _best_size;
|
kpeter@760
|
81 |
Node _curr_node, _best_node;
|
kpeter@760
|
82 |
|
kpeter@758
|
83 |
Path *_cycle_path;
|
kpeter@760
|
84 |
bool _local_path;
|
kpeter@758
|
85 |
|
kpeter@760
|
86 |
// Internal data used by the algorithm
|
kpeter@760
|
87 |
typename Digraph::template NodeMap<Arc> _policy;
|
kpeter@760
|
88 |
typename Digraph::template NodeMap<bool> _reached;
|
kpeter@760
|
89 |
typename Digraph::template NodeMap<int> _level;
|
kpeter@760
|
90 |
typename Digraph::template NodeMap<double> _dist;
|
kpeter@758
|
91 |
|
kpeter@760
|
92 |
// Data for storing the strongly connected components
|
kpeter@760
|
93 |
int _comp_num;
|
kpeter@758
|
94 |
typename Digraph::template NodeMap<int> _comp;
|
kpeter@760
|
95 |
std::vector<std::vector<Node> > _comp_nodes;
|
kpeter@760
|
96 |
std::vector<Node>* _nodes;
|
kpeter@760
|
97 |
typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
|
kpeter@760
|
98 |
|
kpeter@760
|
99 |
// Queue used for BFS search
|
kpeter@760
|
100 |
std::vector<Node> _queue;
|
kpeter@760
|
101 |
int _qfront, _qback;
|
kpeter@760
|
102 |
|
kpeter@758
|
103 |
Tolerance<double> _tol;
|
kpeter@758
|
104 |
|
kpeter@758
|
105 |
public:
|
kpeter@758
|
106 |
|
kpeter@758
|
107 |
/// \brief Constructor.
|
kpeter@758
|
108 |
///
|
kpeter@758
|
109 |
/// The constructor of the class.
|
kpeter@758
|
110 |
///
|
kpeter@758
|
111 |
/// \param digraph The digraph the algorithm runs on.
|
kpeter@758
|
112 |
/// \param length The lengths (costs) of the arcs.
|
kpeter@758
|
113 |
MinMeanCycle( const Digraph &digraph,
|
kpeter@758
|
114 |
const LengthMap &length ) :
|
kpeter@760
|
115 |
_gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),
|
kpeter@760
|
116 |
_policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
|
kpeter@760
|
117 |
_comp(digraph), _in_arcs(digraph)
|
kpeter@758
|
118 |
{}
|
kpeter@758
|
119 |
|
kpeter@758
|
120 |
/// Destructor.
|
kpeter@758
|
121 |
~MinMeanCycle() {
|
kpeter@758
|
122 |
if (_local_path) delete _cycle_path;
|
kpeter@758
|
123 |
}
|
kpeter@758
|
124 |
|
kpeter@758
|
125 |
/// \brief Set the path structure for storing the found cycle.
|
kpeter@758
|
126 |
///
|
kpeter@758
|
127 |
/// This function sets an external path structure for storing the
|
kpeter@758
|
128 |
/// found cycle.
|
kpeter@758
|
129 |
///
|
kpeter@758
|
130 |
/// If you don't call this function before calling \ref run() or
|
kpeter@759
|
131 |
/// \ref findMinMean(), it will allocate a local \ref Path "path"
|
kpeter@758
|
132 |
/// structure. The destuctor deallocates this automatically
|
kpeter@758
|
133 |
/// allocated object, of course.
|
kpeter@758
|
134 |
///
|
kpeter@758
|
135 |
/// \note The algorithm calls only the \ref lemon::Path::addBack()
|
kpeter@758
|
136 |
/// "addBack()" function of the given path structure.
|
kpeter@758
|
137 |
///
|
kpeter@758
|
138 |
/// \return <tt>(*this)</tt>
|
kpeter@758
|
139 |
///
|
kpeter@758
|
140 |
/// \sa cycle()
|
kpeter@758
|
141 |
MinMeanCycle& cyclePath(Path &path) {
|
kpeter@758
|
142 |
if (_local_path) {
|
kpeter@758
|
143 |
delete _cycle_path;
|
kpeter@758
|
144 |
_local_path = false;
|
kpeter@758
|
145 |
}
|
kpeter@758
|
146 |
_cycle_path = &path;
|
kpeter@758
|
147 |
return *this;
|
kpeter@758
|
148 |
}
|
kpeter@758
|
149 |
|
kpeter@758
|
150 |
/// \name Execution control
|
kpeter@758
|
151 |
/// The simplest way to execute the algorithm is to call the \ref run()
|
kpeter@758
|
152 |
/// function.\n
|
kpeter@759
|
153 |
/// If you only need the minimum mean length, you may call
|
kpeter@759
|
154 |
/// \ref findMinMean().
|
kpeter@758
|
155 |
|
kpeter@758
|
156 |
/// @{
|
kpeter@758
|
157 |
|
kpeter@758
|
158 |
/// \brief Run the algorithm.
|
kpeter@758
|
159 |
///
|
kpeter@758
|
160 |
/// This function runs the algorithm.
|
kpeter@759
|
161 |
/// It can be called more than once (e.g. if the underlying digraph
|
kpeter@759
|
162 |
/// and/or the arc lengths have been modified).
|
kpeter@758
|
163 |
///
|
kpeter@758
|
164 |
/// \return \c true if a directed cycle exists in the digraph.
|
kpeter@758
|
165 |
///
|
kpeter@759
|
166 |
/// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
|
kpeter@758
|
167 |
/// \code
|
kpeter@759
|
168 |
/// return mmc.findMinMean() && mmc.findCycle();
|
kpeter@758
|
169 |
/// \endcode
|
kpeter@758
|
170 |
bool run() {
|
kpeter@758
|
171 |
return findMinMean() && findCycle();
|
kpeter@758
|
172 |
}
|
kpeter@758
|
173 |
|
kpeter@759
|
174 |
/// \brief Find the minimum cycle mean.
|
kpeter@758
|
175 |
///
|
kpeter@759
|
176 |
/// This function finds the minimum mean length of the directed
|
kpeter@759
|
177 |
/// cycles in the digraph.
|
kpeter@758
|
178 |
///
|
kpeter@759
|
179 |
/// \return \c true if a directed cycle exists in the digraph.
|
kpeter@759
|
180 |
bool findMinMean() {
|
kpeter@760
|
181 |
// Initialize and find strongly connected components
|
kpeter@760
|
182 |
init();
|
kpeter@760
|
183 |
findComponents();
|
kpeter@760
|
184 |
|
kpeter@759
|
185 |
// Find the minimum cycle mean in the components
|
kpeter@758
|
186 |
for (int comp = 0; comp < _comp_num; ++comp) {
|
kpeter@760
|
187 |
// Find the minimum mean cycle in the current component
|
kpeter@760
|
188 |
if (!buildPolicyGraph(comp)) continue;
|
kpeter@758
|
189 |
while (true) {
|
kpeter@760
|
190 |
findPolicyCycle();
|
kpeter@758
|
191 |
if (!computeNodeDistances()) break;
|
kpeter@758
|
192 |
}
|
kpeter@760
|
193 |
// Update the best cycle (global minimum mean cycle)
|
kpeter@760
|
194 |
if ( !_best_found || (_curr_found &&
|
kpeter@760
|
195 |
_curr_length * _best_size < _best_length * _curr_size) ) {
|
kpeter@760
|
196 |
_best_found = true;
|
kpeter@760
|
197 |
_best_length = _curr_length;
|
kpeter@760
|
198 |
_best_size = _curr_size;
|
kpeter@760
|
199 |
_best_node = _curr_node;
|
kpeter@760
|
200 |
}
|
kpeter@758
|
201 |
}
|
kpeter@760
|
202 |
return _best_found;
|
kpeter@758
|
203 |
}
|
kpeter@758
|
204 |
|
kpeter@758
|
205 |
/// \brief Find a minimum mean directed cycle.
|
kpeter@758
|
206 |
///
|
kpeter@758
|
207 |
/// This function finds a directed cycle of minimum mean length
|
kpeter@758
|
208 |
/// in the digraph using the data computed by findMinMean().
|
kpeter@758
|
209 |
///
|
kpeter@758
|
210 |
/// \return \c true if a directed cycle exists in the digraph.
|
kpeter@758
|
211 |
///
|
kpeter@759
|
212 |
/// \pre \ref findMinMean() must be called before using this function.
|
kpeter@758
|
213 |
bool findCycle() {
|
kpeter@760
|
214 |
if (!_best_found) return false;
|
kpeter@760
|
215 |
_cycle_path->addBack(_policy[_best_node]);
|
kpeter@760
|
216 |
for ( Node v = _best_node;
|
kpeter@760
|
217 |
(v = _gr.target(_policy[v])) != _best_node; ) {
|
kpeter@758
|
218 |
_cycle_path->addBack(_policy[v]);
|
kpeter@758
|
219 |
}
|
kpeter@758
|
220 |
return true;
|
kpeter@758
|
221 |
}
|
kpeter@758
|
222 |
|
kpeter@758
|
223 |
/// @}
|
kpeter@758
|
224 |
|
kpeter@758
|
225 |
/// \name Query Functions
|
kpeter@759
|
226 |
/// The results of the algorithm can be obtained using these
|
kpeter@758
|
227 |
/// functions.\n
|
kpeter@758
|
228 |
/// The algorithm should be executed before using them.
|
kpeter@758
|
229 |
|
kpeter@758
|
230 |
/// @{
|
kpeter@758
|
231 |
|
kpeter@758
|
232 |
/// \brief Return the total length of the found cycle.
|
kpeter@758
|
233 |
///
|
kpeter@758
|
234 |
/// This function returns the total length of the found cycle.
|
kpeter@758
|
235 |
///
|
kpeter@760
|
236 |
/// \pre \ref run() or \ref findMinMean() must be called before
|
kpeter@758
|
237 |
/// using this function.
|
kpeter@758
|
238 |
Value cycleLength() const {
|
kpeter@760
|
239 |
return _best_length;
|
kpeter@758
|
240 |
}
|
kpeter@758
|
241 |
|
kpeter@758
|
242 |
/// \brief Return the number of arcs on the found cycle.
|
kpeter@758
|
243 |
///
|
kpeter@758
|
244 |
/// This function returns the number of arcs on the found cycle.
|
kpeter@758
|
245 |
///
|
kpeter@760
|
246 |
/// \pre \ref run() or \ref findMinMean() must be called before
|
kpeter@758
|
247 |
/// using this function.
|
kpeter@758
|
248 |
int cycleArcNum() const {
|
kpeter@760
|
249 |
return _best_size;
|
kpeter@758
|
250 |
}
|
kpeter@758
|
251 |
|
kpeter@758
|
252 |
/// \brief Return the mean length of the found cycle.
|
kpeter@758
|
253 |
///
|
kpeter@758
|
254 |
/// This function returns the mean length of the found cycle.
|
kpeter@758
|
255 |
///
|
kpeter@760
|
256 |
/// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
|
kpeter@758
|
257 |
/// following code.
|
kpeter@758
|
258 |
/// \code
|
kpeter@760
|
259 |
/// return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
|
kpeter@758
|
260 |
/// \endcode
|
kpeter@758
|
261 |
///
|
kpeter@758
|
262 |
/// \pre \ref run() or \ref findMinMean() must be called before
|
kpeter@758
|
263 |
/// using this function.
|
kpeter@758
|
264 |
double cycleMean() const {
|
kpeter@760
|
265 |
return static_cast<double>(_best_length) / _best_size;
|
kpeter@758
|
266 |
}
|
kpeter@758
|
267 |
|
kpeter@758
|
268 |
/// \brief Return the found cycle.
|
kpeter@758
|
269 |
///
|
kpeter@758
|
270 |
/// This function returns a const reference to the path structure
|
kpeter@758
|
271 |
/// storing the found cycle.
|
kpeter@758
|
272 |
///
|
kpeter@758
|
273 |
/// \pre \ref run() or \ref findCycle() must be called before using
|
kpeter@758
|
274 |
/// this function.
|
kpeter@758
|
275 |
///
|
kpeter@758
|
276 |
/// \sa cyclePath()
|
kpeter@758
|
277 |
const Path& cycle() const {
|
kpeter@758
|
278 |
return *_cycle_path;
|
kpeter@758
|
279 |
}
|
kpeter@758
|
280 |
|
kpeter@758
|
281 |
///@}
|
kpeter@758
|
282 |
|
kpeter@758
|
283 |
private:
|
kpeter@758
|
284 |
|
kpeter@760
|
285 |
// Initialize
|
kpeter@760
|
286 |
void init() {
|
kpeter@760
|
287 |
_tol.epsilon(1e-6);
|
kpeter@760
|
288 |
if (!_cycle_path) {
|
kpeter@760
|
289 |
_local_path = true;
|
kpeter@760
|
290 |
_cycle_path = new Path;
|
kpeter@758
|
291 |
}
|
kpeter@760
|
292 |
_queue.resize(countNodes(_gr));
|
kpeter@760
|
293 |
_best_found = false;
|
kpeter@760
|
294 |
_best_length = 0;
|
kpeter@760
|
295 |
_best_size = 1;
|
kpeter@760
|
296 |
_cycle_path->clear();
|
kpeter@760
|
297 |
}
|
kpeter@760
|
298 |
|
kpeter@760
|
299 |
// Find strongly connected components and initialize _comp_nodes
|
kpeter@760
|
300 |
// and _in_arcs
|
kpeter@760
|
301 |
void findComponents() {
|
kpeter@760
|
302 |
_comp_num = stronglyConnectedComponents(_gr, _comp);
|
kpeter@760
|
303 |
_comp_nodes.resize(_comp_num);
|
kpeter@760
|
304 |
if (_comp_num == 1) {
|
kpeter@760
|
305 |
_comp_nodes[0].clear();
|
kpeter@760
|
306 |
for (NodeIt n(_gr); n != INVALID; ++n) {
|
kpeter@760
|
307 |
_comp_nodes[0].push_back(n);
|
kpeter@760
|
308 |
_in_arcs[n].clear();
|
kpeter@760
|
309 |
for (InArcIt a(_gr, n); a != INVALID; ++a) {
|
kpeter@760
|
310 |
_in_arcs[n].push_back(a);
|
kpeter@760
|
311 |
}
|
kpeter@760
|
312 |
}
|
kpeter@760
|
313 |
} else {
|
kpeter@760
|
314 |
for (int i = 0; i < _comp_num; ++i)
|
kpeter@760
|
315 |
_comp_nodes[i].clear();
|
kpeter@760
|
316 |
for (NodeIt n(_gr); n != INVALID; ++n) {
|
kpeter@760
|
317 |
int k = _comp[n];
|
kpeter@760
|
318 |
_comp_nodes[k].push_back(n);
|
kpeter@760
|
319 |
_in_arcs[n].clear();
|
kpeter@760
|
320 |
for (InArcIt a(_gr, n); a != INVALID; ++a) {
|
kpeter@760
|
321 |
if (_comp[_gr.source(a)] == k) _in_arcs[n].push_back(a);
|
kpeter@760
|
322 |
}
|
kpeter@760
|
323 |
}
|
kpeter@758
|
324 |
}
|
kpeter@760
|
325 |
}
|
kpeter@760
|
326 |
|
kpeter@760
|
327 |
// Build the policy graph in the given strongly connected component
|
kpeter@760
|
328 |
// (the out-degree of every node is 1)
|
kpeter@760
|
329 |
bool buildPolicyGraph(int comp) {
|
kpeter@760
|
330 |
_nodes = &(_comp_nodes[comp]);
|
kpeter@760
|
331 |
if (_nodes->size() < 1 ||
|
kpeter@760
|
332 |
(_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) {
|
kpeter@760
|
333 |
return false;
|
kpeter@758
|
334 |
}
|
kpeter@760
|
335 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
kpeter@760
|
336 |
_dist[(*_nodes)[i]] = std::numeric_limits<double>::max();
|
kpeter@760
|
337 |
}
|
kpeter@760
|
338 |
Node u, v;
|
kpeter@760
|
339 |
Arc e;
|
kpeter@760
|
340 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
kpeter@760
|
341 |
v = (*_nodes)[i];
|
kpeter@760
|
342 |
for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
|
kpeter@760
|
343 |
e = _in_arcs[v][j];
|
kpeter@760
|
344 |
u = _gr.source(e);
|
kpeter@760
|
345 |
if (_length[e] < _dist[u]) {
|
kpeter@760
|
346 |
_dist[u] = _length[e];
|
kpeter@760
|
347 |
_policy[u] = e;
|
kpeter@760
|
348 |
}
|
kpeter@758
|
349 |
}
|
kpeter@758
|
350 |
}
|
kpeter@758
|
351 |
return true;
|
kpeter@758
|
352 |
}
|
kpeter@758
|
353 |
|
kpeter@760
|
354 |
// Find the minimum mean cycle in the policy graph
|
kpeter@760
|
355 |
void findPolicyCycle() {
|
kpeter@760
|
356 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
kpeter@760
|
357 |
_level[(*_nodes)[i]] = -1;
|
kpeter@760
|
358 |
}
|
kpeter@758
|
359 |
Value clength;
|
kpeter@758
|
360 |
int csize;
|
kpeter@758
|
361 |
Node u, v;
|
kpeter@760
|
362 |
_curr_found = false;
|
kpeter@760
|
363 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
kpeter@760
|
364 |
u = (*_nodes)[i];
|
kpeter@760
|
365 |
if (_level[u] >= 0) continue;
|
kpeter@760
|
366 |
for (; _level[u] < 0; u = _gr.target(_policy[u])) {
|
kpeter@760
|
367 |
_level[u] = i;
|
kpeter@760
|
368 |
}
|
kpeter@760
|
369 |
if (_level[u] == i) {
|
kpeter@760
|
370 |
// A cycle is found
|
kpeter@760
|
371 |
clength = _length[_policy[u]];
|
kpeter@760
|
372 |
csize = 1;
|
kpeter@760
|
373 |
for (v = u; (v = _gr.target(_policy[v])) != u; ) {
|
kpeter@760
|
374 |
clength += _length[_policy[v]];
|
kpeter@760
|
375 |
++csize;
|
kpeter@758
|
376 |
}
|
kpeter@760
|
377 |
if ( !_curr_found ||
|
kpeter@760
|
378 |
(clength * _curr_size < _curr_length * csize) ) {
|
kpeter@760
|
379 |
_curr_found = true;
|
kpeter@760
|
380 |
_curr_length = clength;
|
kpeter@760
|
381 |
_curr_size = csize;
|
kpeter@760
|
382 |
_curr_node = u;
|
kpeter@758
|
383 |
}
|
kpeter@758
|
384 |
}
|
kpeter@758
|
385 |
}
|
kpeter@758
|
386 |
}
|
kpeter@758
|
387 |
|
kpeter@760
|
388 |
// Contract the policy graph and compute node distances
|
kpeter@758
|
389 |
bool computeNodeDistances() {
|
kpeter@760
|
390 |
// Find the component of the main cycle and compute node distances
|
kpeter@760
|
391 |
// using reverse BFS
|
kpeter@760
|
392 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
kpeter@760
|
393 |
_reached[(*_nodes)[i]] = false;
|
kpeter@760
|
394 |
}
|
kpeter@760
|
395 |
double curr_mean = double(_curr_length) / _curr_size;
|
kpeter@760
|
396 |
_qfront = _qback = 0;
|
kpeter@760
|
397 |
_queue[0] = _curr_node;
|
kpeter@760
|
398 |
_reached[_curr_node] = true;
|
kpeter@760
|
399 |
_dist[_curr_node] = 0;
|
kpeter@758
|
400 |
Node u, v;
|
kpeter@760
|
401 |
Arc e;
|
kpeter@760
|
402 |
while (_qfront <= _qback) {
|
kpeter@760
|
403 |
v = _queue[_qfront++];
|
kpeter@760
|
404 |
for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
|
kpeter@760
|
405 |
e = _in_arcs[v][j];
|
kpeter@758
|
406 |
u = _gr.source(e);
|
kpeter@760
|
407 |
if (_policy[u] == e && !_reached[u]) {
|
kpeter@760
|
408 |
_reached[u] = true;
|
kpeter@760
|
409 |
_dist[u] = _dist[v] + _length[e] - curr_mean;
|
kpeter@760
|
410 |
_queue[++_qback] = u;
|
kpeter@758
|
411 |
}
|
kpeter@758
|
412 |
}
|
kpeter@758
|
413 |
}
|
kpeter@760
|
414 |
|
kpeter@760
|
415 |
// Connect all other nodes to this component and compute node
|
kpeter@760
|
416 |
// distances using reverse BFS
|
kpeter@760
|
417 |
_qfront = 0;
|
kpeter@760
|
418 |
while (_qback < int(_nodes->size())-1) {
|
kpeter@760
|
419 |
v = _queue[_qfront++];
|
kpeter@760
|
420 |
for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
|
kpeter@760
|
421 |
e = _in_arcs[v][j];
|
kpeter@760
|
422 |
u = _gr.source(e);
|
kpeter@760
|
423 |
if (!_reached[u]) {
|
kpeter@760
|
424 |
_reached[u] = true;
|
kpeter@760
|
425 |
_policy[u] = e;
|
kpeter@760
|
426 |
_dist[u] = _dist[v] + _length[e] - curr_mean;
|
kpeter@760
|
427 |
_queue[++_qback] = u;
|
kpeter@760
|
428 |
}
|
kpeter@760
|
429 |
}
|
kpeter@760
|
430 |
}
|
kpeter@760
|
431 |
|
kpeter@760
|
432 |
// Improve node distances
|
kpeter@758
|
433 |
bool improved = false;
|
kpeter@760
|
434 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
kpeter@760
|
435 |
v = (*_nodes)[i];
|
kpeter@760
|
436 |
for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
|
kpeter@760
|
437 |
e = _in_arcs[v][j];
|
kpeter@760
|
438 |
u = _gr.source(e);
|
kpeter@760
|
439 |
double delta = _dist[v] + _length[e] - curr_mean;
|
kpeter@760
|
440 |
if (_tol.less(delta, _dist[u])) {
|
kpeter@760
|
441 |
_dist[u] = delta;
|
kpeter@760
|
442 |
_policy[u] = e;
|
kpeter@760
|
443 |
improved = true;
|
kpeter@760
|
444 |
}
|
kpeter@758
|
445 |
}
|
kpeter@758
|
446 |
}
|
kpeter@758
|
447 |
return improved;
|
kpeter@758
|
448 |
}
|
kpeter@758
|
449 |
|
kpeter@758
|
450 |
}; //class MinMeanCycle
|
kpeter@758
|
451 |
|
kpeter@758
|
452 |
///@}
|
kpeter@758
|
453 |
|
kpeter@758
|
454 |
} //namespace lemon
|
kpeter@758
|
455 |
|
kpeter@758
|
456 |
#endif //LEMON_MIN_MEAN_CYCLE_H
|