1.1 --- a/lemon/min_mean_cycle.h Thu Aug 06 20:12:43 2009 +0200
1.2 +++ b/lemon/min_mean_cycle.h Thu Aug 06 20:28:28 2009 +0200
1.3 @@ -32,6 +32,63 @@
1.4
1.5 namespace lemon {
1.6
1.7 + /// \brief Default traits class of MinMeanCycle class.
1.8 + ///
1.9 + /// Default traits class of MinMeanCycle class.
1.10 + /// \tparam GR The type of the digraph.
1.11 + /// \tparam LEN The type of the length map.
1.12 + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.13 +#ifdef DOXYGEN
1.14 + template <typename GR, typename LEN>
1.15 +#else
1.16 + template <typename GR, typename LEN,
1.17 + bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
1.18 +#endif
1.19 + struct MinMeanCycleDefaultTraits
1.20 + {
1.21 + /// The type of the digraph
1.22 + typedef GR Digraph;
1.23 + /// The type of the length map
1.24 + typedef LEN LengthMap;
1.25 + /// The type of the arc lengths
1.26 + typedef typename LengthMap::Value Value;
1.27 +
1.28 + /// \brief The large value type used for internal computations
1.29 + ///
1.30 + /// The large value type used for internal computations.
1.31 + /// It is \c long \c long if the \c Value type is integer,
1.32 + /// otherwise it is \c double.
1.33 + /// \c Value must be convertible to \c LargeValue.
1.34 + typedef double LargeValue;
1.35 +
1.36 + /// The tolerance type used for internal computations
1.37 + typedef lemon::Tolerance<LargeValue> Tolerance;
1.38 +
1.39 + /// \brief The path type of the found cycles
1.40 + ///
1.41 + /// The path type of the found cycles.
1.42 + /// It must conform to the \ref lemon::concepts::Path "Path" concept
1.43 + /// and it must have an \c addBack() function.
1.44 + typedef lemon::Path<Digraph> Path;
1.45 + };
1.46 +
1.47 + // Default traits class for integer value types
1.48 + template <typename GR, typename LEN>
1.49 + struct MinMeanCycleDefaultTraits<GR, LEN, true>
1.50 + {
1.51 + typedef GR Digraph;
1.52 + typedef LEN LengthMap;
1.53 + typedef typename LengthMap::Value Value;
1.54 +#ifdef LEMON_HAVE_LONG_LONG
1.55 + typedef long long LargeValue;
1.56 +#else
1.57 + typedef long LargeValue;
1.58 +#endif
1.59 + typedef lemon::Tolerance<LargeValue> Tolerance;
1.60 + typedef lemon::Path<Digraph> Path;
1.61 + };
1.62 +
1.63 +
1.64 /// \addtogroup shortest_path
1.65 /// @{
1.66
1.67 @@ -44,26 +101,44 @@
1.68 /// \tparam GR The type of the digraph the algorithm runs on.
1.69 /// \tparam LEN The type of the length map. The default
1.70 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.71 - ///
1.72 - /// \warning \c LEN::Value must be convertible to \c double.
1.73 #ifdef DOXYGEN
1.74 - template <typename GR, typename LEN>
1.75 + template <typename GR, typename LEN, typename TR>
1.76 #else
1.77 template < typename GR,
1.78 - typename LEN = typename GR::template ArcMap<int> >
1.79 + typename LEN = typename GR::template ArcMap<int>,
1.80 + typename TR = MinMeanCycleDefaultTraits<GR, LEN> >
1.81 #endif
1.82 class MinMeanCycle
1.83 {
1.84 public:
1.85
1.86 - /// The type of the digraph the algorithm runs on
1.87 - typedef GR Digraph;
1.88 + /// The type of the digraph
1.89 + typedef typename TR::Digraph Digraph;
1.90 /// The type of the length map
1.91 - typedef LEN LengthMap;
1.92 + typedef typename TR::LengthMap LengthMap;
1.93 /// The type of the arc lengths
1.94 - typedef typename LengthMap::Value Value;
1.95 - /// The type of the paths
1.96 - typedef lemon::Path<Digraph> Path;
1.97 + typedef typename TR::Value Value;
1.98 +
1.99 + /// \brief The large value type
1.100 + ///
1.101 + /// The large value type used for internal computations.
1.102 + /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
1.103 + /// it is \c long \c long if the \c Value type is integer,
1.104 + /// otherwise it is \c double.
1.105 + typedef typename TR::LargeValue LargeValue;
1.106 +
1.107 + /// The tolerance type
1.108 + typedef typename TR::Tolerance Tolerance;
1.109 +
1.110 + /// \brief The path type of the found cycles
1.111 + ///
1.112 + /// The path type of the found cycles.
1.113 + /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
1.114 + /// it is \ref lemon::Path "Path<Digraph>".
1.115 + typedef typename TR::Path Path;
1.116 +
1.117 + /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm
1.118 + typedef TR Traits;
1.119
1.120 private:
1.121
1.122 @@ -76,7 +151,7 @@
1.123
1.124 // Data for the found cycles
1.125 bool _curr_found, _best_found;
1.126 - Value _curr_length, _best_length;
1.127 + LargeValue _curr_length, _best_length;
1.128 int _curr_size, _best_size;
1.129 Node _curr_node, _best_node;
1.130
1.131 @@ -87,7 +162,7 @@
1.132 typename Digraph::template NodeMap<Arc> _policy;
1.133 typename Digraph::template NodeMap<bool> _reached;
1.134 typename Digraph::template NodeMap<int> _level;
1.135 - typename Digraph::template NodeMap<double> _dist;
1.136 + typename Digraph::template NodeMap<LargeValue> _dist;
1.137
1.138 // Data for storing the strongly connected components
1.139 int _comp_num;
1.140 @@ -99,8 +174,50 @@
1.141 // Queue used for BFS search
1.142 std::vector<Node> _queue;
1.143 int _qfront, _qback;
1.144 +
1.145 + Tolerance _tolerance;
1.146 +
1.147 + public:
1.148 +
1.149 + /// \name Named Template Parameters
1.150 + /// @{
1.151 +
1.152 + template <typename T>
1.153 + struct SetLargeValueTraits : public Traits {
1.154 + typedef T LargeValue;
1.155 + typedef lemon::Tolerance<T> Tolerance;
1.156 + };
1.157 +
1.158 + /// \brief \ref named-templ-param "Named parameter" for setting
1.159 + /// \c LargeValue type.
1.160 + ///
1.161 + /// \ref named-templ-param "Named parameter" for setting \c LargeValue
1.162 + /// type. It is used for internal computations in the algorithm.
1.163 + template <typename T>
1.164 + struct SetLargeValue
1.165 + : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {
1.166 + typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;
1.167 + };
1.168 +
1.169 + template <typename T>
1.170 + struct SetPathTraits : public Traits {
1.171 + typedef T Path;
1.172 + };
1.173 +
1.174 + /// \brief \ref named-templ-param "Named parameter" for setting
1.175 + /// \c %Path type.
1.176 + ///
1.177 + /// \ref named-templ-param "Named parameter" for setting the \c %Path
1.178 + /// type of the found cycles.
1.179 + /// It must conform to the \ref lemon::concepts::Path "Path" concept
1.180 + /// and it must have an \c addBack() function.
1.181 + template <typename T>
1.182 + struct SetPath
1.183 + : public MinMeanCycle<GR, LEN, SetPathTraits<T> > {
1.184 + typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;
1.185 + };
1.186
1.187 - Tolerance<double> _tol;
1.188 + /// @}
1.189
1.190 public:
1.191
1.192 @@ -235,7 +352,7 @@
1.193 ///
1.194 /// \pre \ref run() or \ref findMinMean() must be called before
1.195 /// using this function.
1.196 - Value cycleLength() const {
1.197 + LargeValue cycleLength() const {
1.198 return _best_length;
1.199 }
1.200
1.201 @@ -284,7 +401,6 @@
1.202
1.203 // Initialize
1.204 void init() {
1.205 - _tol.epsilon(1e-6);
1.206 if (!_cycle_path) {
1.207 _local_path = true;
1.208 _cycle_path = new Path;
1.209 @@ -333,7 +449,7 @@
1.210 return false;
1.211 }
1.212 for (int i = 0; i < int(_nodes->size()); ++i) {
1.213 - _dist[(*_nodes)[i]] = std::numeric_limits<double>::max();
1.214 + _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
1.215 }
1.216 Node u, v;
1.217 Arc e;
1.218 @@ -356,7 +472,7 @@
1.219 for (int i = 0; i < int(_nodes->size()); ++i) {
1.220 _level[(*_nodes)[i]] = -1;
1.221 }
1.222 - Value clength;
1.223 + LargeValue clength;
1.224 int csize;
1.225 Node u, v;
1.226 _curr_found = false;
1.227 @@ -392,7 +508,6 @@
1.228 for (int i = 0; i < int(_nodes->size()); ++i) {
1.229 _reached[(*_nodes)[i]] = false;
1.230 }
1.231 - double curr_mean = double(_curr_length) / _curr_size;
1.232 _qfront = _qback = 0;
1.233 _queue[0] = _curr_node;
1.234 _reached[_curr_node] = true;
1.235 @@ -406,7 +521,7 @@
1.236 u = _gr.source(e);
1.237 if (_policy[u] == e && !_reached[u]) {
1.238 _reached[u] = true;
1.239 - _dist[u] = _dist[v] + _length[e] - curr_mean;
1.240 + _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
1.241 _queue[++_qback] = u;
1.242 }
1.243 }
1.244 @@ -423,7 +538,7 @@
1.245 if (!_reached[u]) {
1.246 _reached[u] = true;
1.247 _policy[u] = e;
1.248 - _dist[u] = _dist[v] + _length[e] - curr_mean;
1.249 + _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
1.250 _queue[++_qback] = u;
1.251 }
1.252 }
1.253 @@ -436,8 +551,8 @@
1.254 for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
1.255 e = _in_arcs[v][j];
1.256 u = _gr.source(e);
1.257 - double delta = _dist[v] + _length[e] - curr_mean;
1.258 - if (_tol.less(delta, _dist[u])) {
1.259 + LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
1.260 + if (_tolerance.less(delta, _dist[u])) {
1.261 _dist[u] = delta;
1.262 _policy[u] = e;
1.263 improved = true;