... |
... |
@@ -17,6 +17,6 @@
|
17 |
17 |
*/
|
18 |
18 |
|
19 |
|
#ifndef LEMON_MIN_MEAN_CYCLE_H
|
20 |
|
#define LEMON_MIN_MEAN_CYCLE_H
|
|
19 |
#ifndef LEMON_HOWARD_H
|
|
20 |
#define LEMON_HOWARD_H
|
21 |
21 |
|
22 |
22 |
/// \ingroup shortest_path
|
... |
... |
@@ -34,7 +34,7 @@
|
34 |
34 |
namespace lemon {
|
35 |
35 |
|
36 |
|
/// \brief Default traits class of MinMeanCycle class.
|
|
36 |
/// \brief Default traits class of Howard class.
|
37 |
37 |
///
|
38 |
|
/// Default traits class of MinMeanCycle class.
|
|
38 |
/// Default traits class of Howard class.
|
39 |
39 |
/// \tparam GR The type of the digraph.
|
40 |
40 |
/// \tparam LEN The type of the length map.
|
... |
... |
@@ -46,5 +46,5 @@
|
46 |
46 |
bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
|
47 |
47 |
#endif
|
48 |
|
struct MinMeanCycleDefaultTraits
|
|
48 |
struct HowardDefaultTraits
|
49 |
49 |
{
|
50 |
50 |
/// The type of the digraph
|
... |
... |
@@ -76,5 +76,5 @@
|
76 |
76 |
// Default traits class for integer value types
|
77 |
77 |
template <typename GR, typename LEN>
|
78 |
|
struct MinMeanCycleDefaultTraits<GR, LEN, true>
|
|
78 |
struct HowardDefaultTraits<GR, LEN, true>
|
79 |
79 |
{
|
80 |
80 |
typedef GR Digraph;
|
... |
... |
@@ -97,6 +97,6 @@
|
97 |
97 |
/// mean cycle.
|
98 |
98 |
///
|
99 |
|
/// \ref MinMeanCycle implements Howard's algorithm for finding a
|
100 |
|
/// directed cycle of minimum mean length (cost) in a digraph.
|
|
99 |
/// This class implements Howard's policy iteration algorithm for finding
|
|
100 |
/// a directed cycle of minimum mean length (cost) in a digraph.
|
101 |
101 |
///
|
102 |
102 |
/// \tparam GR The type of the digraph the algorithm runs on.
|
... |
... |
@@ -108,7 +108,7 @@
|
108 |
108 |
template < typename GR,
|
109 |
109 |
typename LEN = typename GR::template ArcMap<int>,
|
110 |
|
typename TR = MinMeanCycleDefaultTraits<GR, LEN> >
|
|
110 |
typename TR = HowardDefaultTraits<GR, LEN> >
|
111 |
111 |
#endif
|
112 |
|
class MinMeanCycle
|
|
112 |
class Howard
|
113 |
113 |
{
|
114 |
114 |
public:
|
... |
... |
@@ -124,5 +124,5 @@
|
124 |
124 |
///
|
125 |
125 |
/// The large value type used for internal computations.
|
126 |
|
/// Using the \ref MinMeanCycleDefaultTraits "default traits class",
|
|
126 |
/// Using the \ref HowardDefaultTraits "default traits class",
|
127 |
127 |
/// it is \c long \c long if the \c Value type is integer,
|
128 |
128 |
/// otherwise it is \c double.
|
... |
... |
@@ -135,9 +135,9 @@
|
135 |
135 |
///
|
136 |
136 |
/// The path type of the found cycles.
|
137 |
|
/// Using the \ref MinMeanCycleDefaultTraits "default traits class",
|
|
137 |
/// Using the \ref HowardDefaultTraits "default traits class",
|
138 |
138 |
/// it is \ref lemon::Path "Path<Digraph>".
|
139 |
139 |
typedef typename TR::Path Path;
|
140 |
140 |
|
141 |
|
/// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm
|
|
141 |
/// The \ref HowardDefaultTraits "traits class" of the algorithm
|
142 |
142 |
typedef TR Traits;
|
143 |
143 |
|
... |
... |
@@ -197,6 +197,6 @@
|
197 |
197 |
template <typename T>
|
198 |
198 |
struct SetLargeValue
|
199 |
|
: public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {
|
200 |
|
typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;
|
|
199 |
: public Howard<GR, LEN, SetLargeValueTraits<T> > {
|
|
200 |
typedef Howard<GR, LEN, SetLargeValueTraits<T> > Create;
|
201 |
201 |
};
|
202 |
202 |
|
... |
... |
@@ -215,6 +215,6 @@
|
215 |
215 |
template <typename T>
|
216 |
216 |
struct SetPath
|
217 |
|
: public MinMeanCycle<GR, LEN, SetPathTraits<T> > {
|
218 |
|
typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;
|
|
217 |
: public Howard<GR, LEN, SetPathTraits<T> > {
|
|
218 |
typedef Howard<GR, LEN, SetPathTraits<T> > Create;
|
219 |
219 |
};
|
220 |
220 |
|
... |
... |
@@ -229,6 +229,6 @@
|
229 |
229 |
/// \param digraph The digraph the algorithm runs on.
|
230 |
230 |
/// \param length The lengths (costs) of the arcs.
|
231 |
|
MinMeanCycle( const Digraph &digraph,
|
232 |
|
const LengthMap &length ) :
|
|
231 |
Howard( const Digraph &digraph,
|
|
232 |
const LengthMap &length ) :
|
233 |
233 |
_gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),
|
234 |
234 |
_policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
|
... |
... |
@@ -237,5 +237,5 @@
|
237 |
237 |
|
238 |
238 |
/// Destructor.
|
239 |
|
~MinMeanCycle() {
|
|
239 |
~Howard() {
|
240 |
240 |
if (_local_path) delete _cycle_path;
|
241 |
241 |
}
|
... |
... |
@@ -255,5 +255,5 @@
|
255 |
255 |
///
|
256 |
256 |
/// \return <tt>(*this)</tt>
|
257 |
|
MinMeanCycle& cycle(Path &path) {
|
|
257 |
Howard& cycle(Path &path) {
|
258 |
258 |
if (_local_path) {
|
259 |
259 |
delete _cycle_path;
|
... |
... |
@@ -560,5 +560,5 @@
|
560 |
560 |
}
|
561 |
561 |
|
562 |
|
}; //class MinMeanCycle
|
|
562 |
}; //class Howard
|
563 |
563 |
|
564 |
564 |
///@}
|
... |
... |
@@ -566,3 +566,3 @@
|
566 |
566 |
} //namespace lemon
|
567 |
567 |
|
568 |
|
#endif //LEMON_MIN_MEAN_CYCLE_H
|
|
568 |
#endif //LEMON_HOWARD_H
|