Changeset - r808:5795860737f5
« 807:83ce7c
809:03887b »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Traits class + named parameters for MinMeanCycle (#179) - Add a Traits class defining LargeValue, Tolerance, Path types. LargeValue is used for internal computations, it is 'long long' if the length type is integer, otherwise it is 'double'. - Add named template parameters for LargeValue and Path types. - Improve numerical stability: remove divisions from the internal computations. If the arc lengths are integers, then all used values are integers (except for the cycleMean() query function, of course).
0 1 0
default
1 file changed with 137 insertions and 22 deletions:
lemon/min_mean_cycle.h
137
22
↑ Collapse diff ↑
lemon/min_mean_cycle.h
Show white space 6 line context
... ... 
@@ -34,2 +34,59 @@
34 34 

			




	
	35
	
		
  /// \brief Default traits class of MinMeanCycle class.


			




	
	36
	
		
  ///


			




	
	37
	
		
  /// Default traits class of MinMeanCycle class.


			




	
	38
	
		
  /// \tparam GR The type of the digraph.


			




	
	39
	
		
  /// \tparam LEN The type of the length map.


			




	
	40
	
		
  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.


			




	
	41
	
		
#ifdef DOXYGEN


			




	
	42
	
		
  template <typename GR, typename LEN>


			




	
	43
	
		
#else


			




	
	44
	
		
  template <typename GR, typename LEN,


			




	
	45
	
		
    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>


			




	
	46
	
		
#endif


			




	
	47
	
		
  struct MinMeanCycleDefaultTraits


			




	
	48
	
		
  {


			




	
	49
	
		
    /// The type of the digraph


			




	
	50
	
		
    typedef GR Digraph;


			




	
	51
	
		
    /// The type of the length map


			




	
	52
	
		
    typedef LEN LengthMap;


			




	
	53
	
		
    /// The type of the arc lengths


			




	
	54
	
		
    typedef typename LengthMap::Value Value;


			




	
	55
	
		

			




	
	56
	
		
    /// \brief The large value type used for internal computations


			




	
	57
	
		
    ///


			




	
	58
	
		
    /// The large value type used for internal computations.


			




	
	59
	
		
    /// It is \c long \c long if the \c Value type is integer,


			




	
	60
	
		
    /// otherwise it is \c double.


			




	
	61
	
		
    /// \c Value must be convertible to \c LargeValue.


			




	
	62
	
		
    typedef double LargeValue;


			




	
	63
	
		

			




	
	64
	
		
    /// The tolerance type used for internal computations


			




	
	65
	
		
    typedef lemon::Tolerance<LargeValue> Tolerance;


			




	
	66
	
		

			




	
	67
	
		
    /// \brief The path type of the found cycles


			




	
	68
	
		
    ///


			




	
	69
	
		
    /// The path type of the found cycles.


			




	
	70
	
		
    /// It must conform to the \ref lemon::concepts::Path "Path" concept


			




	
	71
	
		
    /// and it must have an \c addBack() function.


			




	
	72
	
		
    typedef lemon::Path<Digraph> Path;


			




	
	73
	
		
  };


			




	
	74
	
		

			




	
	75
	
		
  // Default traits class for integer value types


			




	
	76
	
		
  template <typename GR, typename LEN>


			




	
	77
	
		
  struct MinMeanCycleDefaultTraits<GR, LEN, true>


			




	
	78
	
		
  {


			




	
	79
	
		
    typedef GR Digraph;


			




	
	80
	
		
    typedef LEN LengthMap;


			




	
	81
	
		
    typedef typename LengthMap::Value Value;


			




	
	82
	
		
#ifdef LEMON_HAVE_LONG_LONG


			




	
	83
	
		
    typedef long long LargeValue;


			




	
	84
	
		
#else


			




	
	85
	
		
    typedef long LargeValue;


			




	
	86
	
		
#endif


			




	
	87
	
		
    typedef lemon::Tolerance<LargeValue> Tolerance;


			




	
	88
	
		
    typedef lemon::Path<Digraph> Path;


			




	
	89
	
		
  };


			




	
	90
	
		

			




	
	91
	
		

			




	35
	92
	
		
  /// \addtogroup shortest_path


			




	...
	...
	
		
@@ -46,9 +103,8 @@


			




	46
	103
	
		
  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".


			




	47
	
	
		
  ///


			




	48
	
	
		
  /// \warning \c LEN::Value must be convertible to \c double.


			




	49
	104
	
		
#ifdef DOXYGEN


			




	50
	
	
		
  template <typename GR, typename LEN>


			




	
	105
	
		
  template <typename GR, typename LEN, typename TR>


			




	51
	106
	
		
#else


			




	52
	107
	
		
  template < typename GR,


			




	53
	
	
		
             typename LEN = typename GR::template ArcMap<int> >


			




	
	108
	
		
             typename LEN = typename GR::template ArcMap<int>,


			




	
	109
	
		
             typename TR = MinMeanCycleDefaultTraits<GR, LEN> >


			




	54
	110
	
		
#endif


			




	...
	...
	
		
@@ -58,10 +114,29 @@


			




	58
	114
	
		
  


			




	59
	
	
		
    /// The type of the digraph the algorithm runs on


			




	60
	
	
		
    typedef GR Digraph;


			




	
	115
	
		
    /// The type of the digraph


			




	
	116
	
		
    typedef typename TR::Digraph Digraph;


			




	61
	117
	
		
    /// The type of the length map


			




	62
	
	
		
    typedef LEN LengthMap;


			




	
	118
	
		
    typedef typename TR::LengthMap LengthMap;


			




	63
	119
	
		
    /// The type of the arc lengths


			




	64
	
	
		
    typedef typename LengthMap::Value Value;


			




	65
	
	
		
    /// The type of the paths


			




	66
	
	
		
    typedef lemon::Path<Digraph> Path;


			




	
	120
	
		
    typedef typename TR::Value Value;


			




	
	121
	
		

			




	
	122
	
		
    /// \brief The large value type


			




	
	123
	
		
    ///


			




	
	124
	
		
    /// The large value type used for internal computations.


			




	
	125
	
		
    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",


			




	
	126
	
		
    /// it is \c long \c long if the \c Value type is integer,


			




	
	127
	
		
    /// otherwise it is \c double.


			




	
	128
	
		
    typedef typename TR::LargeValue LargeValue;


			




	
	129
	
		

			




	
	130
	
		
    /// The tolerance type


			




	
	131
	
		
    typedef typename TR::Tolerance Tolerance;


			




	
	132
	
		

			




	
	133
	
		
    /// \brief The path type of the found cycles


			




	
	134
	
		
    ///


			




	
	135
	
		
    /// The path type of the found cycles.


			




	
	136
	
		
    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",


			




	
	137
	
		
    /// it is \ref lemon::Path "Path<Digraph>".


			




	
	138
	
		
    typedef typename TR::Path Path;


			




	
	139
	
		

			




	
	140
	
		
    /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm


			




	
	141
	
		
    typedef TR Traits;


			




	67
	142
	
		

			




	...
	...
	
		
@@ -78,3 +153,3 @@


			




	78
	153
	
		
    bool _curr_found, _best_found;


			




	79
	
	
		
    Value _curr_length, _best_length;


			




	
	154
	
		
    LargeValue _curr_length, _best_length;


			




	80
	155
	
		
    int _curr_size, _best_size;


			




	...
	...
	
		
@@ -89,3 +164,3 @@


			




	89
	164
	
		
    typename Digraph::template NodeMap<int> _level;


			




	90
	
	
		
    typename Digraph::template NodeMap<double> _dist;


			




	
	165
	
		
    typename Digraph::template NodeMap<LargeValue> _dist;


			




	91
	166
	
		

			




	...
	...
	
		
@@ -101,4 +176,46 @@


			




	101
	176
	
		
    int _qfront, _qback;


			




	
	177
	
		

			




	
	178
	
		
    Tolerance _tolerance;


			




	
	179
	
		
  


			




	
	180
	
		
  public:


			




	
	181
	
		
  


			




	
	182
	
		
    /// \name Named Template Parameters


			




	
	183
	
		
    /// @{


			




	
	184
	
		

			




	
	185
	
		
    template <typename T>


			




	
	186
	
		
    struct SetLargeValueTraits : public Traits {


			




	
	187
	
		
      typedef T LargeValue;


			




	
	188
	
		
      typedef lemon::Tolerance<T> Tolerance;


			




	
	189
	
		
    };


			




	
	190
	
		

			




	
	191
	
		
    /// \brief \ref named-templ-param "Named parameter" for setting


			




	
	192
	
		
    /// \c LargeValue type.


			




	
	193
	
		
    ///


			




	
	194
	
		
    /// \ref named-templ-param "Named parameter" for setting \c LargeValue


			




	
	195
	
		
    /// type. It is used for internal computations in the algorithm.


			




	
	196
	
		
    template <typename T>


			




	
	197
	
		
    struct SetLargeValue


			




	
	198
	
		
      : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {


			




	
	199
	
		
      typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;


			




	
	200
	
		
    };


			




	
	201
	
		

			




	
	202
	
		
    template <typename T>


			




	
	203
	
		
    struct SetPathTraits : public Traits {


			




	
	204
	
		
      typedef T Path;


			




	
	205
	
		
    };


			




	
	206
	
		

			




	
	207
	
		
    /// \brief \ref named-templ-param "Named parameter" for setting


			




	
	208
	
		
    /// \c %Path type.


			




	
	209
	
		
    ///


			




	
	210
	
		
    /// \ref named-templ-param "Named parameter" for setting the \c %Path


			




	
	211
	
		
    /// type of the found cycles.


			




	
	212
	
		
    /// It must conform to the \ref lemon::concepts::Path "Path" concept


			




	
	213
	
		
    /// and it must have an \c addBack() function.


			




	
	214
	
		
    template <typename T>


			




	
	215
	
		
    struct SetPath


			




	
	216
	
		
      : public MinMeanCycle<GR, LEN, SetPathTraits<T> > {


			




	
	217
	
		
      typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;


			




	
	218
	
		
    };


			




	102
	219
	
		
    


			




	103
	
	
		
    Tolerance<double> _tol;


			




	
	220
	
		
    /// @}


			




	104
	221
	
		

			




	...
	...
	
		
@@ -237,3 +354,3 @@


			




	237
	354
	
		
    /// using this function.


			




	238
	
	
		
    Value cycleLength() const {


			




	
	355
	
		
    LargeValue cycleLength() const {


			




	239
	356
	
		
      return _best_length;


			




	...
	...
	
		
@@ -286,3 +403,2 @@


			




	286
	403
	
		
    void init() {


			




	287
	
	
		
      _tol.epsilon(1e-6);


			




	288
	404
	
		
      if (!_cycle_path) {


			




	...
	...
	
		
@@ -335,3 +451,3 @@


			




	335
	451
	
		
      for (int i = 0; i < int(_nodes->size()); ++i) {


			




	336
	
	
		
        _dist[(*_nodes)[i]] = std::numeric_limits<double>::max();


			




	
	452
	
		
        _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();


			




	337
	453
	
		
      }


			




	...
	...
	
		
@@ -358,3 +474,3 @@


			




	358
	474
	
		
      }


			




	359
	
	
		
      Value clength;


			




	
	475
	
		
      LargeValue clength;


			




	360
	476
	
		
      int csize;


			




	...
	...
	
		
@@ -394,3 +510,2 @@


			




	394
	510
	
		
      }


			




	395
	
	
		
      double curr_mean = double(_curr_length) / _curr_size;


			




	396
	511
	
		
      _qfront = _qback = 0;


			




	...
	...
	
		
@@ -408,3 +523,3 @@


			




	408
	523
	
		
            _reached[u] = true;


			




	409
	
	
		
            _dist[u] = _dist[v] + _length[e] - curr_mean;


			




	
	524
	
		
            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;


			




	410
	525
	
		
            _queue[++_qback] = u;


			




	...
	...
	
		
@@ -425,3 +540,3 @@


			




	425
	540
	
		
            _policy[u] = e;


			




	426
	
	
		
            _dist[u] = _dist[v] + _length[e] - curr_mean;


			




	
	541
	
		
            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;


			




	427
	542
	
		
            _queue[++_qback] = u;


			




	...
	...
	
		
@@ -438,4 +553,4 @@


			




	438
	553
	
		
          u = _gr.source(e);


			




	439
	
	
		
          double delta = _dist[v] + _length[e] - curr_mean;


			




	440
	
	
		
          if (_tol.less(delta, _dist[u])) {


			




	
	554
	
		
          LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;


			




	
	555
	
		
          if (_tolerance.less(delta, _dist[u])) {


			




	441
	556
	
		
            _dist[u] = delta;


			




        

    






    
    



    


    

     
    
0 comments (0 inline)