alpar@877
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
kpeter@758
|
2 |
*
|
alpar@877
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
kpeter@758
|
4 |
*
|
alpar@1092
|
5 |
* Copyright (C) 2003-2013
|
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@864
|
19 |
#ifndef LEMON_HOWARD_MMC_H
|
kpeter@864
|
20 |
#define LEMON_HOWARD_MMC_H
|
kpeter@758
|
21 |
|
kpeter@768
|
22 |
/// \ingroup min_mean_cycle
|
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@763
|
28 |
#include <limits>
|
kpeter@758
|
29 |
#include <lemon/core.h>
|
kpeter@758
|
30 |
#include <lemon/path.h>
|
kpeter@758
|
31 |
#include <lemon/tolerance.h>
|
kpeter@758
|
32 |
#include <lemon/connectivity.h>
|
kpeter@758
|
33 |
|
kpeter@758
|
34 |
namespace lemon {
|
kpeter@758
|
35 |
|
kpeter@864
|
36 |
/// \brief Default traits class of HowardMmc class.
|
kpeter@761
|
37 |
///
|
kpeter@864
|
38 |
/// Default traits class of HowardMmc class.
|
kpeter@761
|
39 |
/// \tparam GR The type of the digraph.
|
kpeter@864
|
40 |
/// \tparam CM The type of the cost map.
|
kpeter@761
|
41 |
/// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
|
kpeter@761
|
42 |
#ifdef DOXYGEN
|
kpeter@864
|
43 |
template <typename GR, typename CM>
|
kpeter@761
|
44 |
#else
|
kpeter@864
|
45 |
template <typename GR, typename CM,
|
kpeter@864
|
46 |
bool integer = std::numeric_limits<typename CM::Value>::is_integer>
|
kpeter@761
|
47 |
#endif
|
kpeter@864
|
48 |
struct HowardMmcDefaultTraits
|
kpeter@761
|
49 |
{
|
kpeter@761
|
50 |
/// The type of the digraph
|
kpeter@761
|
51 |
typedef GR Digraph;
|
kpeter@864
|
52 |
/// The type of the cost map
|
kpeter@864
|
53 |
typedef CM CostMap;
|
kpeter@864
|
54 |
/// The type of the arc costs
|
kpeter@864
|
55 |
typedef typename CostMap::Value Cost;
|
kpeter@761
|
56 |
|
kpeter@864
|
57 |
/// \brief The large cost type used for internal computations
|
kpeter@761
|
58 |
///
|
kpeter@864
|
59 |
/// The large cost type used for internal computations.
|
kpeter@864
|
60 |
/// It is \c long \c long if the \c Cost type is integer,
|
kpeter@761
|
61 |
/// otherwise it is \c double.
|
kpeter@864
|
62 |
/// \c Cost must be convertible to \c LargeCost.
|
kpeter@864
|
63 |
typedef double LargeCost;
|
kpeter@761
|
64 |
|
kpeter@761
|
65 |
/// The tolerance type used for internal computations
|
kpeter@864
|
66 |
typedef lemon::Tolerance<LargeCost> Tolerance;
|
kpeter@761
|
67 |
|
kpeter@761
|
68 |
/// \brief The path type of the found cycles
|
kpeter@761
|
69 |
///
|
kpeter@761
|
70 |
/// The path type of the found cycles.
|
kpeter@761
|
71 |
/// It must conform to the \ref lemon::concepts::Path "Path" concept
|
kpeter@761
|
72 |
/// and it must have an \c addBack() function.
|
kpeter@761
|
73 |
typedef lemon::Path<Digraph> Path;
|
kpeter@761
|
74 |
};
|
kpeter@761
|
75 |
|
kpeter@864
|
76 |
// Default traits class for integer cost types
|
kpeter@864
|
77 |
template <typename GR, typename CM>
|
kpeter@864
|
78 |
struct HowardMmcDefaultTraits<GR, CM, true>
|
kpeter@761
|
79 |
{
|
kpeter@761
|
80 |
typedef GR Digraph;
|
kpeter@864
|
81 |
typedef CM CostMap;
|
kpeter@864
|
82 |
typedef typename CostMap::Value Cost;
|
kpeter@761
|
83 |
#ifdef LEMON_HAVE_LONG_LONG
|
kpeter@864
|
84 |
typedef long long LargeCost;
|
kpeter@761
|
85 |
#else
|
kpeter@864
|
86 |
typedef long LargeCost;
|
kpeter@761
|
87 |
#endif
|
kpeter@864
|
88 |
typedef lemon::Tolerance<LargeCost> Tolerance;
|
kpeter@761
|
89 |
typedef lemon::Path<Digraph> Path;
|
kpeter@761
|
90 |
};
|
kpeter@761
|
91 |
|
kpeter@761
|
92 |
|
kpeter@768
|
93 |
/// \addtogroup min_mean_cycle
|
kpeter@758
|
94 |
/// @{
|
kpeter@758
|
95 |
|
kpeter@758
|
96 |
/// \brief Implementation of Howard's algorithm for finding a minimum
|
kpeter@758
|
97 |
/// mean cycle.
|
kpeter@758
|
98 |
///
|
kpeter@764
|
99 |
/// This class implements Howard's policy iteration algorithm for finding
|
kpeter@864
|
100 |
/// a directed cycle of minimum mean cost in a digraph
|
alpar@1053
|
101 |
/// \cite dasdan98minmeancycle, \cite dasdan04experimental.
|
kpeter@768
|
102 |
/// This class provides the most efficient algorithm for the
|
kpeter@768
|
103 |
/// minimum mean cycle problem, though the best known theoretical
|
kpeter@768
|
104 |
/// bound on its running time is exponential.
|
kpeter@758
|
105 |
///
|
kpeter@758
|
106 |
/// \tparam GR The type of the digraph the algorithm runs on.
|
kpeter@864
|
107 |
/// \tparam CM The type of the cost map. The default
|
kpeter@758
|
108 |
/// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
|
kpeter@825
|
109 |
/// \tparam TR The traits class that defines various types used by the
|
kpeter@864
|
110 |
/// algorithm. By default, it is \ref HowardMmcDefaultTraits
|
kpeter@864
|
111 |
/// "HowardMmcDefaultTraits<GR, CM>".
|
kpeter@825
|
112 |
/// In most cases, this parameter should not be set directly,
|
kpeter@825
|
113 |
/// consider to use the named template parameters instead.
|
kpeter@758
|
114 |
#ifdef DOXYGEN
|
kpeter@864
|
115 |
template <typename GR, typename CM, typename TR>
|
kpeter@758
|
116 |
#else
|
kpeter@758
|
117 |
template < typename GR,
|
kpeter@864
|
118 |
typename CM = typename GR::template ArcMap<int>,
|
kpeter@864
|
119 |
typename TR = HowardMmcDefaultTraits<GR, CM> >
|
kpeter@758
|
120 |
#endif
|
kpeter@864
|
121 |
class HowardMmc
|
kpeter@758
|
122 |
{
|
kpeter@758
|
123 |
public:
|
alpar@877
|
124 |
|
kpeter@761
|
125 |
/// The type of the digraph
|
kpeter@761
|
126 |
typedef typename TR::Digraph Digraph;
|
kpeter@864
|
127 |
/// The type of the cost map
|
kpeter@864
|
128 |
typedef typename TR::CostMap CostMap;
|
kpeter@864
|
129 |
/// The type of the arc costs
|
kpeter@864
|
130 |
typedef typename TR::Cost Cost;
|
kpeter@761
|
131 |
|
kpeter@864
|
132 |
/// \brief The large cost type
|
kpeter@761
|
133 |
///
|
kpeter@864
|
134 |
/// The large cost type used for internal computations.
|
kpeter@864
|
135 |
/// By default, it is \c long \c long if the \c Cost type is integer,
|
kpeter@761
|
136 |
/// otherwise it is \c double.
|
kpeter@864
|
137 |
typedef typename TR::LargeCost LargeCost;
|
kpeter@761
|
138 |
|
kpeter@761
|
139 |
/// The tolerance type
|
kpeter@761
|
140 |
typedef typename TR::Tolerance Tolerance;
|
kpeter@761
|
141 |
|
kpeter@761
|
142 |
/// \brief The path type of the found cycles
|
kpeter@761
|
143 |
///
|
kpeter@761
|
144 |
/// The path type of the found cycles.
|
alpar@1076
|
145 |
/// Using the \ref lemon::HowardMmcDefaultTraits "default traits class",
|
kpeter@761
|
146 |
/// it is \ref lemon::Path "Path<Digraph>".
|
kpeter@761
|
147 |
typedef typename TR::Path Path;
|
kpeter@761
|
148 |
|
alpar@1076
|
149 |
/// The \ref lemon::HowardMmcDefaultTraits "traits class" of the algorithm
|
kpeter@761
|
150 |
typedef TR Traits;
|
kpeter@758
|
151 |
|
kpeter@1012
|
152 |
/// \brief Constants for the causes of search termination.
|
kpeter@1012
|
153 |
///
|
kpeter@1012
|
154 |
/// Enum type containing constants for the different causes of search
|
kpeter@1012
|
155 |
/// termination. The \ref findCycleMean() function returns one of
|
kpeter@1012
|
156 |
/// these values.
|
kpeter@1012
|
157 |
enum TerminationCause {
|
alpar@1092
|
158 |
|
kpeter@1012
|
159 |
/// No directed cycle can be found in the digraph.
|
kpeter@1012
|
160 |
NO_CYCLE = 0,
|
alpar@1092
|
161 |
|
kpeter@1012
|
162 |
/// Optimal solution (minimum cycle mean) is found.
|
kpeter@1012
|
163 |
OPTIMAL = 1,
|
kpeter@1012
|
164 |
|
kpeter@1012
|
165 |
/// The iteration count limit is reached.
|
kpeter@1012
|
166 |
ITERATION_LIMIT
|
kpeter@1012
|
167 |
};
|
kpeter@1012
|
168 |
|
kpeter@758
|
169 |
private:
|
kpeter@758
|
170 |
|
kpeter@758
|
171 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
|
alpar@877
|
172 |
|
kpeter@758
|
173 |
// The digraph the algorithm runs on
|
kpeter@758
|
174 |
const Digraph &_gr;
|
kpeter@864
|
175 |
// The cost of the arcs
|
kpeter@864
|
176 |
const CostMap &_cost;
|
kpeter@758
|
177 |
|
kpeter@760
|
178 |
// Data for the found cycles
|
kpeter@760
|
179 |
bool _curr_found, _best_found;
|
kpeter@864
|
180 |
LargeCost _curr_cost, _best_cost;
|
kpeter@760
|
181 |
int _curr_size, _best_size;
|
kpeter@760
|
182 |
Node _curr_node, _best_node;
|
kpeter@760
|
183 |
|
kpeter@758
|
184 |
Path *_cycle_path;
|
kpeter@760
|
185 |
bool _local_path;
|
kpeter@758
|
186 |
|
kpeter@760
|
187 |
// Internal data used by the algorithm
|
kpeter@760
|
188 |
typename Digraph::template NodeMap<Arc> _policy;
|
kpeter@760
|
189 |
typename Digraph::template NodeMap<bool> _reached;
|
kpeter@760
|
190 |
typename Digraph::template NodeMap<int> _level;
|
kpeter@864
|
191 |
typename Digraph::template NodeMap<LargeCost> _dist;
|
kpeter@758
|
192 |
|
kpeter@760
|
193 |
// Data for storing the strongly connected components
|
kpeter@760
|
194 |
int _comp_num;
|
kpeter@758
|
195 |
typename Digraph::template NodeMap<int> _comp;
|
kpeter@760
|
196 |
std::vector<std::vector<Node> > _comp_nodes;
|
kpeter@760
|
197 |
std::vector<Node>* _nodes;
|
kpeter@760
|
198 |
typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
|
alpar@877
|
199 |
|
kpeter@760
|
200 |
// Queue used for BFS search
|
kpeter@760
|
201 |
std::vector<Node> _queue;
|
kpeter@760
|
202 |
int _qfront, _qback;
|
kpeter@761
|
203 |
|
kpeter@761
|
204 |
Tolerance _tolerance;
|
alpar@877
|
205 |
|
kpeter@767
|
206 |
// Infinite constant
|
kpeter@864
|
207 |
const LargeCost INF;
|
kpeter@767
|
208 |
|
kpeter@761
|
209 |
public:
|
alpar@877
|
210 |
|
kpeter@761
|
211 |
/// \name Named Template Parameters
|
kpeter@761
|
212 |
/// @{
|
kpeter@761
|
213 |
|
kpeter@761
|
214 |
template <typename T>
|
kpeter@864
|
215 |
struct SetLargeCostTraits : public Traits {
|
kpeter@864
|
216 |
typedef T LargeCost;
|
kpeter@761
|
217 |
typedef lemon::Tolerance<T> Tolerance;
|
kpeter@761
|
218 |
};
|
kpeter@761
|
219 |
|
kpeter@761
|
220 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
kpeter@864
|
221 |
/// \c LargeCost type.
|
kpeter@761
|
222 |
///
|
kpeter@864
|
223 |
/// \ref named-templ-param "Named parameter" for setting \c LargeCost
|
kpeter@761
|
224 |
/// type. It is used for internal computations in the algorithm.
|
kpeter@761
|
225 |
template <typename T>
|
kpeter@864
|
226 |
struct SetLargeCost
|
kpeter@864
|
227 |
: public HowardMmc<GR, CM, SetLargeCostTraits<T> > {
|
kpeter@864
|
228 |
typedef HowardMmc<GR, CM, SetLargeCostTraits<T> > Create;
|
kpeter@761
|
229 |
};
|
kpeter@761
|
230 |
|
kpeter@761
|
231 |
template <typename T>
|
kpeter@761
|
232 |
struct SetPathTraits : public Traits {
|
kpeter@761
|
233 |
typedef T Path;
|
kpeter@761
|
234 |
};
|
kpeter@761
|
235 |
|
kpeter@761
|
236 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
kpeter@761
|
237 |
/// \c %Path type.
|
kpeter@761
|
238 |
///
|
kpeter@761
|
239 |
/// \ref named-templ-param "Named parameter" for setting the \c %Path
|
kpeter@761
|
240 |
/// type of the found cycles.
|
kpeter@761
|
241 |
/// It must conform to the \ref lemon::concepts::Path "Path" concept
|
kpeter@761
|
242 |
/// and it must have an \c addBack() function.
|
kpeter@761
|
243 |
template <typename T>
|
kpeter@761
|
244 |
struct SetPath
|
kpeter@864
|
245 |
: public HowardMmc<GR, CM, SetPathTraits<T> > {
|
kpeter@864
|
246 |
typedef HowardMmc<GR, CM, SetPathTraits<T> > Create;
|
kpeter@761
|
247 |
};
|
alpar@877
|
248 |
|
kpeter@761
|
249 |
/// @}
|
kpeter@758
|
250 |
|
kpeter@863
|
251 |
protected:
|
kpeter@863
|
252 |
|
kpeter@864
|
253 |
HowardMmc() {}
|
kpeter@863
|
254 |
|
kpeter@758
|
255 |
public:
|
kpeter@758
|
256 |
|
kpeter@758
|
257 |
/// \brief Constructor.
|
kpeter@758
|
258 |
///
|
kpeter@758
|
259 |
/// The constructor of the class.
|
kpeter@758
|
260 |
///
|
kpeter@758
|
261 |
/// \param digraph The digraph the algorithm runs on.
|
kpeter@864
|
262 |
/// \param cost The costs of the arcs.
|
kpeter@864
|
263 |
HowardMmc( const Digraph &digraph,
|
kpeter@864
|
264 |
const CostMap &cost ) :
|
kpeter@864
|
265 |
_gr(digraph), _cost(cost), _best_found(false),
|
kpeter@864
|
266 |
_best_cost(0), _best_size(1), _cycle_path(NULL), _local_path(false),
|
kpeter@760
|
267 |
_policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
|
kpeter@767
|
268 |
_comp(digraph), _in_arcs(digraph),
|
kpeter@864
|
269 |
INF(std::numeric_limits<LargeCost>::has_infinity ?
|
kpeter@864
|
270 |
std::numeric_limits<LargeCost>::infinity() :
|
kpeter@864
|
271 |
std::numeric_limits<LargeCost>::max())
|
kpeter@758
|
272 |
{}
|
kpeter@758
|
273 |
|
kpeter@758
|
274 |
/// Destructor.
|
kpeter@864
|
275 |
~HowardMmc() {
|
kpeter@758
|
276 |
if (_local_path) delete _cycle_path;
|
kpeter@758
|
277 |
}
|
kpeter@758
|
278 |
|
kpeter@758
|
279 |
/// \brief Set the path structure for storing the found cycle.
|
kpeter@758
|
280 |
///
|
kpeter@758
|
281 |
/// This function sets an external path structure for storing the
|
kpeter@758
|
282 |
/// found cycle.
|
kpeter@758
|
283 |
///
|
kpeter@758
|
284 |
/// If you don't call this function before calling \ref run() or
|
kpeter@1049
|
285 |
/// \ref findCycleMean(), a local \ref Path "path" structure
|
kpeter@1049
|
286 |
/// will be allocated. The destuctor deallocates this automatically
|
kpeter@758
|
287 |
/// allocated object, of course.
|
kpeter@758
|
288 |
///
|
kpeter@758
|
289 |
/// \note The algorithm calls only the \ref lemon::Path::addBack()
|
kpeter@758
|
290 |
/// "addBack()" function of the given path structure.
|
kpeter@758
|
291 |
///
|
kpeter@758
|
292 |
/// \return <tt>(*this)</tt>
|
kpeter@864
|
293 |
HowardMmc& cycle(Path &path) {
|
kpeter@758
|
294 |
if (_local_path) {
|
kpeter@758
|
295 |
delete _cycle_path;
|
kpeter@758
|
296 |
_local_path = false;
|
kpeter@758
|
297 |
}
|
kpeter@758
|
298 |
_cycle_path = &path;
|
kpeter@758
|
299 |
return *this;
|
kpeter@758
|
300 |
}
|
kpeter@758
|
301 |
|
kpeter@769
|
302 |
/// \brief Set the tolerance used by the algorithm.
|
kpeter@769
|
303 |
///
|
kpeter@769
|
304 |
/// This function sets the tolerance object used by the algorithm.
|
kpeter@769
|
305 |
///
|
kpeter@769
|
306 |
/// \return <tt>(*this)</tt>
|
kpeter@864
|
307 |
HowardMmc& tolerance(const Tolerance& tolerance) {
|
kpeter@769
|
308 |
_tolerance = tolerance;
|
kpeter@769
|
309 |
return *this;
|
kpeter@769
|
310 |
}
|
kpeter@769
|
311 |
|
kpeter@769
|
312 |
/// \brief Return a const reference to the tolerance.
|
kpeter@769
|
313 |
///
|
kpeter@769
|
314 |
/// This function returns a const reference to the tolerance object
|
kpeter@769
|
315 |
/// used by the algorithm.
|
kpeter@769
|
316 |
const Tolerance& tolerance() const {
|
kpeter@769
|
317 |
return _tolerance;
|
kpeter@769
|
318 |
}
|
kpeter@769
|
319 |
|
kpeter@758
|
320 |
/// \name Execution control
|
kpeter@758
|
321 |
/// The simplest way to execute the algorithm is to call the \ref run()
|
kpeter@758
|
322 |
/// function.\n
|
kpeter@864
|
323 |
/// If you only need the minimum mean cost, you may call
|
kpeter@864
|
324 |
/// \ref findCycleMean().
|
kpeter@758
|
325 |
|
kpeter@758
|
326 |
/// @{
|
kpeter@758
|
327 |
|
kpeter@758
|
328 |
/// \brief Run the algorithm.
|
kpeter@758
|
329 |
///
|
kpeter@758
|
330 |
/// This function runs the algorithm.
|
kpeter@759
|
331 |
/// It can be called more than once (e.g. if the underlying digraph
|
kpeter@864
|
332 |
/// and/or the arc costs have been modified).
|
kpeter@758
|
333 |
///
|
kpeter@758
|
334 |
/// \return \c true if a directed cycle exists in the digraph.
|
kpeter@758
|
335 |
///
|
kpeter@759
|
336 |
/// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
|
kpeter@758
|
337 |
/// \code
|
kpeter@864
|
338 |
/// return mmc.findCycleMean() && mmc.findCycle();
|
kpeter@758
|
339 |
/// \endcode
|
kpeter@758
|
340 |
bool run() {
|
kpeter@864
|
341 |
return findCycleMean() && findCycle();
|
kpeter@758
|
342 |
}
|
kpeter@758
|
343 |
|
kpeter@1012
|
344 |
/// \brief Find the minimum cycle mean (or an upper bound).
|
kpeter@758
|
345 |
///
|
kpeter@864
|
346 |
/// This function finds the minimum mean cost of the directed
|
kpeter@1012
|
347 |
/// cycles in the digraph (or an upper bound for it).
|
kpeter@758
|
348 |
///
|
kpeter@1012
|
349 |
/// By default, the function finds the exact minimum cycle mean,
|
kpeter@1012
|
350 |
/// but an optional limit can also be specified for the number of
|
kpeter@1012
|
351 |
/// iterations performed during the search process.
|
kpeter@1012
|
352 |
/// The return value indicates if the optimal solution is found
|
kpeter@1012
|
353 |
/// or the iteration limit is reached. In the latter case, an
|
kpeter@1012
|
354 |
/// approximate solution is provided, which corresponds to a directed
|
kpeter@1012
|
355 |
/// cycle whose mean cost is relatively small, but not necessarily
|
kpeter@1012
|
356 |
/// minimal.
|
kpeter@1012
|
357 |
///
|
kpeter@1012
|
358 |
/// \param limit The maximum allowed number of iterations during
|
alpar@1092
|
359 |
/// the search process. Its default value implies that the algorithm
|
kpeter@1012
|
360 |
/// runs until it finds the exact optimal solution.
|
kpeter@1012
|
361 |
///
|
kpeter@1012
|
362 |
/// \return The termination cause of the search process.
|
alpar@1092
|
363 |
/// For more information, see \ref TerminationCause.
|
kpeter@1012
|
364 |
TerminationCause findCycleMean(int limit = std::numeric_limits<int>::max()) {
|
kpeter@760
|
365 |
// Initialize and find strongly connected components
|
kpeter@760
|
366 |
init();
|
kpeter@760
|
367 |
findComponents();
|
alpar@877
|
368 |
|
kpeter@759
|
369 |
// Find the minimum cycle mean in the components
|
kpeter@1012
|
370 |
int iter_count = 0;
|
kpeter@1012
|
371 |
bool iter_limit_reached = false;
|
kpeter@758
|
372 |
for (int comp = 0; comp < _comp_num; ++comp) {
|
kpeter@760
|
373 |
// Find the minimum mean cycle in the current component
|
kpeter@760
|
374 |
if (!buildPolicyGraph(comp)) continue;
|
kpeter@758
|
375 |
while (true) {
|
kpeter@1012
|
376 |
if (++iter_count > limit) {
|
kpeter@1012
|
377 |
iter_limit_reached = true;
|
kpeter@1012
|
378 |
break;
|
kpeter@1012
|
379 |
}
|
kpeter@760
|
380 |
findPolicyCycle();
|
kpeter@758
|
381 |
if (!computeNodeDistances()) break;
|
kpeter@758
|
382 |
}
|
kpeter@1012
|
383 |
|
kpeter@760
|
384 |
// Update the best cycle (global minimum mean cycle)
|
kpeter@767
|
385 |
if ( _curr_found && (!_best_found ||
|
kpeter@864
|
386 |
_curr_cost * _best_size < _best_cost * _curr_size) ) {
|
kpeter@760
|
387 |
_best_found = true;
|
kpeter@864
|
388 |
_best_cost = _curr_cost;
|
kpeter@760
|
389 |
_best_size = _curr_size;
|
kpeter@760
|
390 |
_best_node = _curr_node;
|
kpeter@760
|
391 |
}
|
alpar@1092
|
392 |
|
kpeter@1012
|
393 |
if (iter_limit_reached) break;
|
kpeter@758
|
394 |
}
|
kpeter@1012
|
395 |
|
kpeter@1012
|
396 |
if (iter_limit_reached) {
|
kpeter@1012
|
397 |
return ITERATION_LIMIT;
|
kpeter@1012
|
398 |
} else {
|
kpeter@1012
|
399 |
return _best_found ? OPTIMAL : NO_CYCLE;
|
kpeter@1012
|
400 |
}
|
kpeter@758
|
401 |
}
|
kpeter@758
|
402 |
|
kpeter@758
|
403 |
/// \brief Find a minimum mean directed cycle.
|
kpeter@758
|
404 |
///
|
kpeter@864
|
405 |
/// This function finds a directed cycle of minimum mean cost
|
kpeter@864
|
406 |
/// in the digraph using the data computed by findCycleMean().
|
kpeter@758
|
407 |
///
|
kpeter@758
|
408 |
/// \return \c true if a directed cycle exists in the digraph.
|
kpeter@758
|
409 |
///
|
kpeter@864
|
410 |
/// \pre \ref findCycleMean() must be called before using this function.
|
kpeter@758
|
411 |
bool findCycle() {
|
kpeter@760
|
412 |
if (!_best_found) return false;
|
kpeter@760
|
413 |
_cycle_path->addBack(_policy[_best_node]);
|
kpeter@760
|
414 |
for ( Node v = _best_node;
|
kpeter@760
|
415 |
(v = _gr.target(_policy[v])) != _best_node; ) {
|
kpeter@758
|
416 |
_cycle_path->addBack(_policy[v]);
|
kpeter@758
|
417 |
}
|
kpeter@758
|
418 |
return true;
|
kpeter@758
|
419 |
}
|
kpeter@758
|
420 |
|
kpeter@758
|
421 |
/// @}
|
kpeter@758
|
422 |
|
kpeter@758
|
423 |
/// \name Query Functions
|
kpeter@759
|
424 |
/// The results of the algorithm can be obtained using these
|
kpeter@758
|
425 |
/// functions.\n
|
kpeter@758
|
426 |
/// The algorithm should be executed before using them.
|
kpeter@758
|
427 |
|
kpeter@758
|
428 |
/// @{
|
kpeter@758
|
429 |
|
kpeter@864
|
430 |
/// \brief Return the total cost of the found cycle.
|
kpeter@758
|
431 |
///
|
kpeter@864
|
432 |
/// This function returns the total cost of the found cycle.
|
kpeter@758
|
433 |
///
|
kpeter@864
|
434 |
/// \pre \ref run() or \ref findCycleMean() must be called before
|
kpeter@758
|
435 |
/// using this function.
|
kpeter@864
|
436 |
Cost cycleCost() const {
|
kpeter@864
|
437 |
return static_cast<Cost>(_best_cost);
|
kpeter@758
|
438 |
}
|
kpeter@758
|
439 |
|
kpeter@758
|
440 |
/// \brief Return the number of arcs on the found cycle.
|
kpeter@758
|
441 |
///
|
kpeter@758
|
442 |
/// This function returns the number of arcs on the found cycle.
|
kpeter@758
|
443 |
///
|
kpeter@864
|
444 |
/// \pre \ref run() or \ref findCycleMean() must be called before
|
kpeter@758
|
445 |
/// using this function.
|
kpeter@864
|
446 |
int cycleSize() const {
|
kpeter@760
|
447 |
return _best_size;
|
kpeter@758
|
448 |
}
|
kpeter@758
|
449 |
|
kpeter@864
|
450 |
/// \brief Return the mean cost of the found cycle.
|
kpeter@758
|
451 |
///
|
kpeter@864
|
452 |
/// This function returns the mean cost of the found cycle.
|
kpeter@758
|
453 |
///
|
kpeter@760
|
454 |
/// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
|
kpeter@758
|
455 |
/// following code.
|
kpeter@758
|
456 |
/// \code
|
kpeter@864
|
457 |
/// return static_cast<double>(alg.cycleCost()) / alg.cycleSize();
|
kpeter@758
|
458 |
/// \endcode
|
kpeter@758
|
459 |
///
|
kpeter@864
|
460 |
/// \pre \ref run() or \ref findCycleMean() must be called before
|
kpeter@758
|
461 |
/// using this function.
|
kpeter@758
|
462 |
double cycleMean() const {
|
kpeter@864
|
463 |
return static_cast<double>(_best_cost) / _best_size;
|
kpeter@758
|
464 |
}
|
kpeter@758
|
465 |
|
kpeter@758
|
466 |
/// \brief Return the found cycle.
|
kpeter@758
|
467 |
///
|
kpeter@758
|
468 |
/// This function returns a const reference to the path structure
|
kpeter@758
|
469 |
/// storing the found cycle.
|
kpeter@758
|
470 |
///
|
kpeter@758
|
471 |
/// \pre \ref run() or \ref findCycle() must be called before using
|
kpeter@758
|
472 |
/// this function.
|
kpeter@758
|
473 |
const Path& cycle() const {
|
kpeter@758
|
474 |
return *_cycle_path;
|
kpeter@758
|
475 |
}
|
kpeter@758
|
476 |
|
kpeter@758
|
477 |
///@}
|
kpeter@758
|
478 |
|
kpeter@758
|
479 |
private:
|
kpeter@758
|
480 |
|
kpeter@760
|
481 |
// Initialize
|
kpeter@760
|
482 |
void init() {
|
kpeter@760
|
483 |
if (!_cycle_path) {
|
kpeter@760
|
484 |
_local_path = true;
|
kpeter@760
|
485 |
_cycle_path = new Path;
|
kpeter@758
|
486 |
}
|
kpeter@760
|
487 |
_queue.resize(countNodes(_gr));
|
kpeter@760
|
488 |
_best_found = false;
|
kpeter@864
|
489 |
_best_cost = 0;
|
kpeter@760
|
490 |
_best_size = 1;
|
kpeter@760
|
491 |
_cycle_path->clear();
|
kpeter@760
|
492 |
}
|
alpar@877
|
493 |
|
kpeter@760
|
494 |
// Find strongly connected components and initialize _comp_nodes
|
kpeter@760
|
495 |
// and _in_arcs
|
kpeter@760
|
496 |
void findComponents() {
|
kpeter@760
|
497 |
_comp_num = stronglyConnectedComponents(_gr, _comp);
|
kpeter@760
|
498 |
_comp_nodes.resize(_comp_num);
|
kpeter@760
|
499 |
if (_comp_num == 1) {
|
kpeter@760
|
500 |
_comp_nodes[0].clear();
|
kpeter@760
|
501 |
for (NodeIt n(_gr); n != INVALID; ++n) {
|
kpeter@760
|
502 |
_comp_nodes[0].push_back(n);
|
kpeter@760
|
503 |
_in_arcs[n].clear();
|
kpeter@760
|
504 |
for (InArcIt a(_gr, n); a != INVALID; ++a) {
|
kpeter@760
|
505 |
_in_arcs[n].push_back(a);
|
kpeter@760
|
506 |
}
|
kpeter@760
|
507 |
}
|
kpeter@760
|
508 |
} else {
|
kpeter@760
|
509 |
for (int i = 0; i < _comp_num; ++i)
|
kpeter@760
|
510 |
_comp_nodes[i].clear();
|
kpeter@760
|
511 |
for (NodeIt n(_gr); n != INVALID; ++n) {
|
kpeter@760
|
512 |
int k = _comp[n];
|
kpeter@760
|
513 |
_comp_nodes[k].push_back(n);
|
kpeter@760
|
514 |
_in_arcs[n].clear();
|
kpeter@760
|
515 |
for (InArcIt a(_gr, n); a != INVALID; ++a) {
|
kpeter@760
|
516 |
if (_comp[_gr.source(a)] == k) _in_arcs[n].push_back(a);
|
kpeter@760
|
517 |
}
|
kpeter@760
|
518 |
}
|
kpeter@758
|
519 |
}
|
kpeter@760
|
520 |
}
|
kpeter@760
|
521 |
|
kpeter@760
|
522 |
// Build the policy graph in the given strongly connected component
|
kpeter@760
|
523 |
// (the out-degree of every node is 1)
|
kpeter@760
|
524 |
bool buildPolicyGraph(int comp) {
|
kpeter@760
|
525 |
_nodes = &(_comp_nodes[comp]);
|
kpeter@760
|
526 |
if (_nodes->size() < 1 ||
|
kpeter@760
|
527 |
(_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) {
|
kpeter@760
|
528 |
return false;
|
kpeter@758
|
529 |
}
|
kpeter@760
|
530 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
kpeter@767
|
531 |
_dist[(*_nodes)[i]] = INF;
|
kpeter@760
|
532 |
}
|
kpeter@760
|
533 |
Node u, v;
|
kpeter@760
|
534 |
Arc e;
|
kpeter@760
|
535 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
kpeter@760
|
536 |
v = (*_nodes)[i];
|
kpeter@760
|
537 |
for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
|
kpeter@760
|
538 |
e = _in_arcs[v][j];
|
kpeter@760
|
539 |
u = _gr.source(e);
|
kpeter@864
|
540 |
if (_cost[e] < _dist[u]) {
|
kpeter@864
|
541 |
_dist[u] = _cost[e];
|
kpeter@760
|
542 |
_policy[u] = e;
|
kpeter@760
|
543 |
}
|
kpeter@758
|
544 |
}
|
kpeter@758
|
545 |
}
|
kpeter@758
|
546 |
return true;
|
kpeter@758
|
547 |
}
|
kpeter@758
|
548 |
|
kpeter@760
|
549 |
// Find the minimum mean cycle in the policy graph
|
kpeter@760
|
550 |
void findPolicyCycle() {
|
kpeter@760
|
551 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
kpeter@760
|
552 |
_level[(*_nodes)[i]] = -1;
|
kpeter@760
|
553 |
}
|
kpeter@864
|
554 |
LargeCost ccost;
|
kpeter@758
|
555 |
int csize;
|
kpeter@758
|
556 |
Node u, v;
|
kpeter@760
|
557 |
_curr_found = false;
|
kpeter@760
|
558 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
kpeter@760
|
559 |
u = (*_nodes)[i];
|
kpeter@760
|
560 |
if (_level[u] >= 0) continue;
|
kpeter@760
|
561 |
for (; _level[u] < 0; u = _gr.target(_policy[u])) {
|
kpeter@760
|
562 |
_level[u] = i;
|
kpeter@760
|
563 |
}
|
kpeter@760
|
564 |
if (_level[u] == i) {
|
kpeter@760
|
565 |
// A cycle is found
|
kpeter@864
|
566 |
ccost = _cost[_policy[u]];
|
kpeter@760
|
567 |
csize = 1;
|
kpeter@760
|
568 |
for (v = u; (v = _gr.target(_policy[v])) != u; ) {
|
kpeter@864
|
569 |
ccost += _cost[_policy[v]];
|
kpeter@760
|
570 |
++csize;
|
kpeter@758
|
571 |
}
|
kpeter@760
|
572 |
if ( !_curr_found ||
|
kpeter@864
|
573 |
(ccost * _curr_size < _curr_cost * csize) ) {
|
kpeter@760
|
574 |
_curr_found = true;
|
kpeter@864
|
575 |
_curr_cost = ccost;
|
kpeter@760
|
576 |
_curr_size = csize;
|
kpeter@760
|
577 |
_curr_node = u;
|
kpeter@758
|
578 |
}
|
kpeter@758
|
579 |
}
|
kpeter@758
|
580 |
}
|
kpeter@758
|
581 |
}
|
kpeter@758
|
582 |
|
kpeter@760
|
583 |
// Contract the policy graph and compute node distances
|
kpeter@758
|
584 |
bool computeNodeDistances() {
|
kpeter@760
|
585 |
// Find the component of the main cycle and compute node distances
|
kpeter@760
|
586 |
// using reverse BFS
|
kpeter@760
|
587 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
kpeter@760
|
588 |
_reached[(*_nodes)[i]] = false;
|
kpeter@760
|
589 |
}
|
kpeter@760
|
590 |
_qfront = _qback = 0;
|
kpeter@760
|
591 |
_queue[0] = _curr_node;
|
kpeter@760
|
592 |
_reached[_curr_node] = true;
|
kpeter@760
|
593 |
_dist[_curr_node] = 0;
|
kpeter@758
|
594 |
Node u, v;
|
kpeter@760
|
595 |
Arc e;
|
kpeter@760
|
596 |
while (_qfront <= _qback) {
|
kpeter@760
|
597 |
v = _queue[_qfront++];
|
kpeter@760
|
598 |
for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
|
kpeter@760
|
599 |
e = _in_arcs[v][j];
|
kpeter@758
|
600 |
u = _gr.source(e);
|
kpeter@760
|
601 |
if (_policy[u] == e && !_reached[u]) {
|
kpeter@760
|
602 |
_reached[u] = true;
|
kpeter@864
|
603 |
_dist[u] = _dist[v] + _cost[e] * _curr_size - _curr_cost;
|
kpeter@760
|
604 |
_queue[++_qback] = u;
|
kpeter@758
|
605 |
}
|
kpeter@758
|
606 |
}
|
kpeter@758
|
607 |
}
|
kpeter@760
|
608 |
|
kpeter@760
|
609 |
// Connect all other nodes to this component and compute node
|
kpeter@760
|
610 |
// distances using reverse BFS
|
kpeter@760
|
611 |
_qfront = 0;
|
kpeter@760
|
612 |
while (_qback < int(_nodes->size())-1) {
|
kpeter@760
|
613 |
v = _queue[_qfront++];
|
kpeter@760
|
614 |
for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
|
kpeter@760
|
615 |
e = _in_arcs[v][j];
|
kpeter@760
|
616 |
u = _gr.source(e);
|
kpeter@760
|
617 |
if (!_reached[u]) {
|
kpeter@760
|
618 |
_reached[u] = true;
|
kpeter@760
|
619 |
_policy[u] = e;
|
kpeter@864
|
620 |
_dist[u] = _dist[v] + _cost[e] * _curr_size - _curr_cost;
|
kpeter@760
|
621 |
_queue[++_qback] = u;
|
kpeter@760
|
622 |
}
|
kpeter@760
|
623 |
}
|
kpeter@760
|
624 |
}
|
kpeter@760
|
625 |
|
kpeter@760
|
626 |
// Improve node distances
|
kpeter@758
|
627 |
bool improved = false;
|
kpeter@760
|
628 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
kpeter@760
|
629 |
v = (*_nodes)[i];
|
kpeter@760
|
630 |
for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
|
kpeter@760
|
631 |
e = _in_arcs[v][j];
|
kpeter@760
|
632 |
u = _gr.source(e);
|
kpeter@864
|
633 |
LargeCost delta = _dist[v] + _cost[e] * _curr_size - _curr_cost;
|
kpeter@761
|
634 |
if (_tolerance.less(delta, _dist[u])) {
|
kpeter@760
|
635 |
_dist[u] = delta;
|
kpeter@760
|
636 |
_policy[u] = e;
|
kpeter@760
|
637 |
improved = true;
|
kpeter@760
|
638 |
}
|
kpeter@758
|
639 |
}
|
kpeter@758
|
640 |
}
|
kpeter@758
|
641 |
return improved;
|
kpeter@758
|
642 |
}
|
kpeter@758
|
643 |
|
kpeter@864
|
644 |
}; //class HowardMmc
|
kpeter@758
|
645 |
|
kpeter@758
|
646 |
///@}
|
kpeter@758
|
647 |
|
kpeter@758
|
648 |
} //namespace lemon
|
kpeter@758
|
649 |
|
kpeter@864
|
650 |
#endif //LEMON_HOWARD_MMC_H
|