LEMON/LEMON-official Changeset - r808:5795860737f5

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r808:5795860737f5

« 807:83ce7c

809:03887b »

r808:5795860737f5

Thu, 06 Aug 2009 20:28:28

[Not Reviewed]

0 comments (0 inline)

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

↑ Collapse diff ↑

lemon/min_mean_cycle.h

Show inline comments

@@ -29,81 +29,198 @@
 		#include <lemon/path.h>
 		#include <lemon/tolerance.h>
 		#include <lemon/connectivity.h>
 		namespace lemon {
 		  /// \brief Default traits class of MinMeanCycle class.
 		  ///
 		  /// Default traits class of MinMeanCycle class.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN>
 		#else
 		  template <typename GR, typename LEN,
 		    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
 		#endif
 		  struct MinMeanCycleDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the length map
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename LengthMap::Value Value;
 		    /// \brief The large value type used for internal computations
 		    ///
 		    /// The large value type used for internal computations.
 		    /// It is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Value must be convertible to \c LargeValue.
 		    typedef double LargeValue;
 		    /// The tolerance type used for internal computations
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addBack() function.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  // Default traits class for integer value types
 		  template <typename GR, typename LEN>
 		  struct MinMeanCycleDefaultTraits<GR, LEN, true>
+		  {
 		    typedef GR Digraph;
 		    typedef LEN LengthMap;
 		    typedef typename LengthMap::Value Value;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeValue;
 		#else
 		    typedef long LargeValue;
 		#endif
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// \addtogroup shortest_path
 		  /// @{
 		  /// \brief Implementation of Howard's algorithm for finding a minimum
 		  /// mean cycle.
 		  ///
 		  /// \ref MinMeanCycle implements Howard's algorithm for finding a
 		  /// directed cycle of minimum mean length (cost) in a digraph.
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam LEN The type of the length map. The default
 		  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  ///
 		  /// \warning \c LEN::Value must be convertible to \c double.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN>
+		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template < typename GR,
-		             typename LEN = typename GR::template ArcMap<int> >
+		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = MinMeanCycleDefaultTraits<GR, LEN> >
 		#endif
 		  class MinMeanCycle
+		  {
 		  public:
 		    /// The type of the digraph the algorithm runs on
 		    typedef GR Digraph;
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the length map
-		    typedef LEN LengthMap;
+		    typedef typename TR::LengthMap LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename LengthMap::Value Value;
 		    /// The type of the paths
-		    typedef lemon::Path<Digraph> Path;
+		    typedef typename TR::Value Value;
 		    /// \brief The large value type
 		    ///
 		    /// The large value type used for internal computations.
 		    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
 		    /// it is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    typedef typename TR::LargeValue LargeValue;
 		    /// The tolerance type
 		    typedef typename TR::Tolerance Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
 		    /// it is \ref lemon::Path "Path<Digraph>".
 		    typedef typename TR::Path Path;
 		    /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    // The digraph the algorithm runs on
 		    const Digraph &_gr;
 		    // The length of the arcs
 		    const LengthMap &_length;
 		    // Data for the found cycles
 		    bool _curr_found, _best_found;
-		    Value _curr_length, _best_length;
+		    LargeValue _curr_length, _best_length;
 		    int _curr_size, _best_size;
 		    Node _curr_node, _best_node;
 		    Path *_cycle_path;
 		    bool _local_path;
 		    // Internal data used by the algorithm
 		    typename Digraph::template NodeMap<Arc> _policy;
 		    typename Digraph::template NodeMap<bool> _reached;
 		    typename Digraph::template NodeMap<int> _level;
-		    typename Digraph::template NodeMap<double> _dist;
+		    typename Digraph::template NodeMap<LargeValue> _dist;
 		    // Data for storing the strongly connected components
 		    int _comp_num;
 		    typename Digraph::template NodeMap<int> _comp;
 		    std::vector<std::vector<Node> > _comp_nodes;
 		    std::vector<Node>* _nodes;
 		    typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
 		    // Queue used for BFS search
 		    std::vector<Node> _queue;
 		    int _qfront, _qback;
 		    Tolerance _tolerance;
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetLargeValueTraits : public Traits {
 		      typedef T LargeValue;
 		      typedef lemon::Tolerance<T> Tolerance;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c LargeValue type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
 		    /// type. It is used for internal computations in the algorithm.
 		    template <typename T>
 		    struct SetLargeValue
 		      : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {
 		      typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetPathTraits : public Traits {
 		      typedef T Path;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c %Path type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting the \c %Path
 		    /// type of the found cycles.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addBack() function.
 		    template <typename T>
 		    struct SetPath
 		      : public MinMeanCycle<GR, LEN, SetPathTraits<T> > {
 		      typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;
 		    };
-		    Tolerance<double> _tol;
+		    /// @}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
@@ -232,13 +349,13 @@
 		    /// \brief Return the total length of the found cycle.
 		    ///
 		    /// This function returns the total length of the found cycle.
 		    ///
 		    /// \pre \ref run() or \ref findMinMean() must be called before
 		    /// using this function.
-		    Value cycleLength() const {
+		    LargeValue cycleLength() const {
 		      return _best_length;
+		    }
 		    /// \brief Return the number of arcs on the found cycle.
 		    ///
 		    /// This function returns the number of arcs on the found cycle.
@@ -281,13 +398,12 @@
 		    ///@}
 		  private:
 		    // Initialize
 		    void init() {
 		      _tol.epsilon(1e-6);
 		      if (!_cycle_path) {
 		        _local_path = true;
 		        _cycle_path = new Path;
+		      }
 		      _queue.resize(countNodes(_gr));
 		      _best_found = false;
@@ -330,13 +446,13 @@
 		      _nodes = &(_comp_nodes[comp]);
 		      if (_nodes->size() < 1 ||
 		          (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) {
 		        return false;
+		      }
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
-		        _dist[(*_nodes)[i]] = std::numeric_limits<double>::max();
+		        _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
+		      }
 		      Node u, v;
 		      Arc e;
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
 		        v = (*_nodes)[i];
 		        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
@@ -353,13 +469,13 @@
 		    // Find the minimum mean cycle in the policy graph
 		    void findPolicyCycle() {
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
 		        _level[(*_nodes)[i]] = -1;
+		      }
-		      Value clength;
+		      LargeValue clength;
 		      int csize;
 		      Node u, v;
 		      _curr_found = false;
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
 		        u = (*_nodes)[i];
 		        if (_level[u] >= 0) continue;
@@ -389,13 +505,12 @@
 		    bool computeNodeDistances() {
 		      // Find the component of the main cycle and compute node distances
 		      // using reverse BFS
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
 		        _reached[(*_nodes)[i]] = false;
+		      }
 		      double curr_mean = double(_curr_length) / _curr_size;
 		      _qfront = _qback = 0;
 		      _queue[0] = _curr_node;
 		      _reached[_curr_node] = true;
 		      _dist[_curr_node] = 0;
 		      Node u, v;
 		      Arc e;
@@ -403,13 +518,13 @@
 		        v = _queue[_qfront++];
 		        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
 		          e = _in_arcs[v][j];
 		          u = _gr.source(e);
 		          if (_policy[u] == e && !_reached[u]) {
 		            _reached[u] = true;
-		            _dist[u] = _dist[v] + _length[e] - curr_mean;
+		            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
 		            _queue[++_qback] = u;
+		          }
+		        }
+		      }
 		      // Connect all other nodes to this component and compute node
@@ -420,27 +535,27 @@
 		        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
 		          e = _in_arcs[v][j];
 		          u = _gr.source(e);
 		          if (!_reached[u]) {
 		            _reached[u] = true;
 		            _policy[u] = e;
-		            _dist[u] = _dist[v] + _length[e] - curr_mean;
+		            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
 		            _queue[++_qback] = u;
+		          }
+		        }
+		      }
 		      // Improve node distances
 		      bool improved = false;
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
 		        v = (*_nodes)[i];
 		        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
 		          e = _in_arcs[v][j];
 		          u = _gr.source(e);
 		          double delta = _dist[v] + _length[e] - curr_mean;
 		          if (_tol.less(delta, _dist[u])) {
 		          LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
 		          if (_tolerance.less(delta, _dist[u])) {
 		            _dist[u] = delta;
 		            _policy[u] = e;
 		            improved = true;
+		          }
+		        }
+		      }

0 comments (0 inline)

RhodeCode

Login to your account