Changeset 1174:7c86f14b3bc5 in lemon-main

Timestamp:

10/17/18 18:55:53 (6 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Parents:

1148:2126945deb6a (diff), 1151:43647f48e971 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge #1.3 related bugfix heads

Files:

• lemon/capacity_scaling.h (modified) (1 diff)
• lemon/capacity_scaling.h (modified) (23 diffs)

lemon/capacity_scaling.h

@@ -28 +28 @@
 #include <limits>
 #include <lemon/core.h>
+#include <lemon/maps.h>
 #include <lemon/bin_heap.h>
 

lemon/capacity_scaling.h

@@ -1 @@
-/* -*- C++ -*-
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
  *
- * This file is a part of LEMON, a generic C++ optimization library
+ * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2013
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -68 +68 @@
   /// \ref CapacityScaling implements the capacity scaling version
   /// of the successive shortest path algorithm for finding a
-  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
-  /// \ref edmondskarp72theoretical. It is an efficient dual
-  /// solution method.
+  /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows,
+  /// \cite edmondskarp72theoretical. It is an efficient dual
+  /// solution method, which runs in polynomial time
+  /// \f$O(m\log U (n+m)\log n)\f$, where <i>U</i> denotes the maximum
+  /// of node supply and arc capacity values.
+  ///
+  /// This algorithm is typically slower than \ref CostScaling and
+  /// \ref NetworkSimplex, but in special cases, it can be more
+  /// efficient than them.
+  /// (For more information, see \ref min_cost_flow_algs "the module page".)
   ///
   /// Most of the parameters of the problem (except for the digraph)
@@ -79 +86 @@
   /// \tparam GR The digraph type the algorithm runs on.
   /// \tparam V The number type used for flow amounts, capacity bounds
-  /// and supply values in the algorithm. By default it is \c int.
+  /// and supply values in the algorithm. By default, it is \c int.
   /// \tparam C The number type used for costs and potentials in the
-  /// algorithm. By default it is the same as \c V.
+  /// algorithm. By default, it is the same as \c V.
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits
+  /// "CapacityScalingDefaultTraits<GR, V, C>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
   ///
-  /// \warning Both number types must be signed and all input data must
-  /// be integer.
-  /// \warning This algorithm does not support negative costs for such
-  /// arcs that have infinite upper bound.
+  /// \warning Both \c V and \c C must be signed number types.
+  /// \warning Capacity bounds and supply values must be integer, but
+  /// arc costs can be arbitrary real numbers.
+  /// \warning This algorithm does not support negative costs for
+  /// arcs having infinite upper bound.
 #ifdef DOXYGEN
   template <typename GR, typename V, typename C, typename TR>
@@ -107 +120 @@
     typedef typename TR::Heap Heap;
 
-    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
+    /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class"
+    /// of the algorithm
     typedef TR Traits;
 
@@ -130 +144 @@
       UNBOUNDED
     };
-  
+
   private:
 
@@ -136 +150 @@
 
     typedef std::vector<int> IntVector;
-    typedef std::vector<char> BoolVector;
     typedef std::vector<Value> ValueVector;
     typedef std::vector<Cost> CostVector;
+    typedef std::vector<char> BoolVector;
+    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 
   private:
@@ -150 +165 @@
 
     // Parameters of the problem
-    bool _have_lower;
+    bool _has_lower;
     Value _sum_supply;
 
@@ -180 +195 @@
 
   public:
-  
+
     /// \brief Constant for infinite upper bounds (capacities).
     ///
@@ -207 +222 @@
       CostVector &_pi;
       IntVector &_pred;
-      
+
       IntVector _proc_nodes;
       CostVector _dist;
-      
+
     public:
 
@@ -297 +312 @@
     /// @}
 
+  protected:
+
+    CapacityScaling() {}
+
   public:
 
@@ -316 +335 @@
         "The cost type of CapacityScaling must be signed");
 
+      // Reset data structures
+      reset();
+    }
+
+    /// \name Parameters
+    /// The parameters of the algorithm can be specified using these
+    /// functions.
+
+    /// @{
+
+    /// \brief Set the lower bounds on the arcs.
+    ///
+    /// This function sets the lower bounds on the arcs.
+    /// If it is not used before calling \ref run(), the lower bounds
+    /// will be set to zero on all arcs.
+    ///
+    /// \param map An arc map storing the lower bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template <typename LowerMap>
+    CapacityScaling& lowerMap(const LowerMap& map) {
+      _has_lower = true;
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _lower[_arc_idf[a]] = map[a];
+      }
+      return *this;
+    }
+
+    /// \brief Set the upper bounds (capacities) on the arcs.
+    ///
+    /// This function sets the upper bounds (capacities) on the arcs.
+    /// If it is not used before calling \ref run(), the upper bounds
+    /// will be set to \ref INF on all arcs (i.e. the flow value will be
+    /// unbounded from above).
+    ///
+    /// \param map An arc map storing the upper bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename UpperMap>
+    CapacityScaling& upperMap(const UpperMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _upper[_arc_idf[a]] = map[a];
+      }
+      return *this;
+    }
+
+    /// \brief Set the costs of the arcs.
+    ///
+    /// This function sets the costs of the arcs.
+    /// If it is not used before calling \ref run(), the costs
+    /// will be set to \c 1 on all arcs.
+    ///
+    /// \param map An arc map storing the costs.
+    /// Its \c Value type must be convertible to the \c Cost type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename CostMap>
+    CapacityScaling& costMap(const CostMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _cost[_arc_idf[a]] =  map[a];
+        _cost[_arc_idb[a]] = -map[a];
+      }
+      return *this;
+    }
+
+    /// \brief Set the supply values of the nodes.
+    ///
+    /// This function sets the supply values of the nodes.
+    /// If neither this function nor \ref stSupply() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// \param map A node map storing the supply values.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename SupplyMap>
+    CapacityScaling& supplyMap(const SupplyMap& map) {
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        _supply[_node_id[n]] = map[n];
+      }
+      return *this;
+    }
+
+    /// \brief Set single source and target nodes and a supply value.
+    ///
+    /// This function sets a single source node and a single target node
+    /// and the required flow value.
+    /// If neither this function nor \ref supplyMap() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// Using this function has the same effect as using \ref supplyMap()
+    /// with a map in which \c k is assigned to \c s, \c -k is
+    /// assigned to \c t and all other nodes have zero supply value.
+    ///
+    /// \param s The source node.
+    /// \param t The target node.
+    /// \param k The required amount of flow from node \c s to node \c t
+    /// (i.e. the supply of \c s and the demand of \c t).
+    ///
+    /// \return <tt>(*this)</tt>
+    CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
+      for (int i = 0; i != _node_num; ++i) {
+        _supply[i] = 0;
+      }
+      _supply[_node_id[s]] =  k;
+      _supply[_node_id[t]] = -k;
+      return *this;
+    }
+
+    /// @}
+
+    /// \name Execution control
+    /// The algorithm can be executed using \ref run().
+
+    /// @{
+
+    /// \brief Run the algorithm.
+    ///
+    /// This function runs the algorithm.
+    /// The paramters can be specified using functions \ref lowerMap(),
+    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+    /// For example,
+    /// \code
+    ///   CapacityScaling<ListDigraph> cs(graph);
+    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// This function can be called more than once. All the given parameters
+    /// are kept for the next call, unless \ref resetParams() or \ref reset()
+    /// is used, thus only the modified parameters have to be set again.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class (or the last \ref reset() call), then the \ref reset()
+    /// function must be called.
+    ///
+    /// \param factor The capacity scaling factor. It must be larger than
+    /// one to use scaling. If it is less or equal to one, then scaling
+    /// will be disabled.
+    ///
+    /// \return \c INFEASIBLE if no feasible flow exists,
+    /// \n \c OPTIMAL if the problem has optimal solution
+    /// (i.e. it is feasible and bounded), and the algorithm has found
+    /// optimal flow and node potentials (primal and dual solutions),
+    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
+    /// and infinite upper bound. It means that the objective function
+    /// is unbounded on that arc, however, note that it could actually be
+    /// bounded over the feasible flows, but this algroithm cannot handle
+    /// these cases.
+    ///
+    /// \see ProblemType
+    /// \see resetParams(), reset()
+    ProblemType run(int factor = 4) {
+      _factor = factor;
+      ProblemType pt = init();
+      if (pt != OPTIMAL) return pt;
+      return start();
+    }
+
+    /// \brief Reset all the parameters that have been given before.
+    ///
+    /// This function resets all the paramaters that have been given
+    /// before using functions \ref lowerMap(), \ref upperMap(),
+    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple \ref run() calls. Basically, all the given
+    /// parameters are kept for the next \ref run() call, unless
+    /// \ref resetParams() or \ref reset() is used.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class or the last \ref reset() call, then the \ref reset()
+    /// function must be used, otherwise \ref resetParams() is sufficient.
+    ///
+    /// For example,
+    /// \code
+    ///   CapacityScaling<ListDigraph> cs(graph);
+    ///
+    ///   // First run
+    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    ///
+    ///   // Run again with modified cost map (resetParams() is not called,
+    ///   // so only the cost map have to be set again)
+    ///   cost[e] += 100;
+    ///   cs.costMap(cost).run();
+    ///
+    ///   // Run again from scratch using resetParams()
+    ///   // (the lower bounds will be set to zero on all arcs)
+    ///   cs.resetParams();
+    ///   cs.upperMap(capacity).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// \return <tt>(*this)</tt>
+    ///
+    /// \see reset(), run()
+    CapacityScaling& resetParams() {
+      for (int i = 0; i != _node_num; ++i) {
+        _supply[i] = 0;
+      }
+      for (int j = 0; j != _res_arc_num; ++j) {
+        _lower[j] = 0;
+        _upper[j] = INF;
+        _cost[j] = _forward[j] ? 1 : -1;
+      }
+      _has_lower = false;
+      return *this;
+    }
+
+    /// \brief Reset the internal data structures and all the parameters
+    /// that have been given before.
+    ///
+    /// This function resets the internal data structures and all the
+    /// paramaters that have been given before using functions \ref lowerMap(),
+    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple \ref run() calls. Basically, all the given
+    /// parameters are kept for the next \ref run() call, unless
+    /// \ref resetParams() or \ref reset() is used.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class or the last \ref reset() call, then the \ref reset()
+    /// function must be used, otherwise \ref resetParams() is sufficient.
+    ///
+    /// See \ref resetParams() for examples.
+    ///
+    /// \return <tt>(*this)</tt>
+    ///
+    /// \see resetParams(), run()
+    CapacityScaling& reset() {
       // Resize vectors
       _node_num = countNodes(_graph);
@@ -333 +585 @@
       _cost.resize(_res_arc_num);
       _supply.resize(_node_num);
-      
+
       _res_cap.resize(_res_arc_num);
       _pi.resize(_node_num);
@@ -377 +629 @@
         _reverse[bi] = fi;
       }
-      
+
       // Reset parameters
-      reset();
-    }
-
-    /// \name Parameters
-    /// The parameters of the algorithm can be specified using these
-    /// functions.
-
-    /// @{
-
-    /// \brief Set the lower bounds on the arcs.
-    ///
-    /// This function sets the lower bounds on the arcs.
-    /// If it is not used before calling \ref run(), the lower bounds
-    /// will be set to zero on all arcs.
-    ///
-    /// \param map An arc map storing the lower bounds.
-    /// Its \c Value type must be convertible to the \c Value type
-    /// of the algorithm.
-    ///
-    /// \return <tt>(*this)</tt>
-    template <typename LowerMap>
-    CapacityScaling& lowerMap(const LowerMap& map) {
-      _have_lower = true;
-      for (ArcIt a(_graph); a != INVALID; ++a) {
-        _lower[_arc_idf[a]] = map[a];
-        _lower[_arc_idb[a]] = map[a];
-      }
-      return *this;
-    }
-
-    /// \brief Set the upper bounds (capacities) on the arcs.
-    ///
-    /// This function sets the upper bounds (capacities) on the arcs.
-    /// If it is not used before calling \ref run(), the upper bounds
-    /// will be set to \ref INF on all arcs (i.e. the flow value will be
-    /// unbounded from above).
-    ///
-    /// \param map An arc map storing the upper bounds.
-    /// Its \c Value type must be convertible to the \c Value type
-    /// of the algorithm.
-    ///
-    /// \return <tt>(*this)</tt>
-    template<typename UpperMap>
-    CapacityScaling& upperMap(const UpperMap& map) {
-      for (ArcIt a(_graph); a != INVALID; ++a) {
-        _upper[_arc_idf[a]] = map[a];
-      }
-      return *this;
-    }
-
-    /// \brief Set the costs of the arcs.
-    ///
-    /// This function sets the costs of the arcs.
-    /// If it is not used before calling \ref run(), the costs
-    /// will be set to \c 1 on all arcs.
-    ///
-    /// \param map An arc map storing the costs.
-    /// Its \c Value type must be convertible to the \c Cost type
-    /// of the algorithm.
-    ///
-    /// \return <tt>(*this)</tt>
-    template<typename CostMap>
-    CapacityScaling& costMap(const CostMap& map) {
-      for (ArcIt a(_graph); a != INVALID; ++a) {
-        _cost[_arc_idf[a]] =  map[a];
-        _cost[_arc_idb[a]] = -map[a];
-      }
-      return *this;
-    }
-
-    /// \brief Set the supply values of the nodes.
-    ///
-    /// This function sets the supply values of the nodes.
-    /// If neither this function nor \ref stSupply() is used before
-    /// calling \ref run(), the supply of each node will be set to zero.
-    ///
-    /// \param map A node map storing the supply values.
-    /// Its \c Value type must be convertible to the \c Value type
-    /// of the algorithm.
-    ///
-    /// \return <tt>(*this)</tt>
-    template<typename SupplyMap>
-    CapacityScaling& supplyMap(const SupplyMap& map) {
-      for (NodeIt n(_graph); n != INVALID; ++n) {
-        _supply[_node_id[n]] = map[n];
-      }
-      return *this;
-    }
-
-    /// \brief Set single source and target nodes and a supply value.
-    ///
-    /// This function sets a single source node and a single target node
-    /// and the required flow value.
-    /// If neither this function nor \ref supplyMap() is used before
-    /// calling \ref run(), the supply of each node will be set to zero.
-    ///
-    /// Using this function has the same effect as using \ref supplyMap()
-    /// with such a map in which \c k is assigned to \c s, \c -k is
-    /// assigned to \c t and all other nodes have zero supply value.
-    ///
-    /// \param s The source node.
-    /// \param t The target node.
-    /// \param k The required amount of flow from node \c s to node \c t
-    /// (i.e. the supply of \c s and the demand of \c t).
-    ///
-    /// \return <tt>(*this)</tt>
-    CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
-      for (int i = 0; i != _node_num; ++i) {
-        _supply[i] = 0;
-      }
-      _supply[_node_id[s]] =  k;
-      _supply[_node_id[t]] = -k;
-      return *this;
-    }
-    
-    /// @}
-
-    /// \name Execution control
-    /// The algorithm can be executed using \ref run().
-
-    /// @{
-
-    /// \brief Run the algorithm.
-    ///
-    /// This function runs the algorithm.
-    /// The paramters can be specified using functions \ref lowerMap(),
-    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
-    /// For example,
-    /// \code
-    ///   CapacityScaling<ListDigraph> cs(graph);
-    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
-    ///     .supplyMap(sup).run();
-    /// \endcode
-    ///
-    /// This function can be called more than once. All the parameters
-    /// that have been given are kept for the next call, unless
-    /// \ref reset() is called, thus only the modified parameters
-    /// have to be set again. See \ref reset() for examples.
-    /// However, the underlying digraph must not be modified after this
-    /// class have been constructed, since it copies and extends the graph.
-    ///
-    /// \param factor The capacity scaling factor. It must be larger than
-    /// one to use scaling. If it is less or equal to one, then scaling
-    /// will be disabled.
-    ///
-    /// \return \c INFEASIBLE if no feasible flow exists,
-    /// \n \c OPTIMAL if the problem has optimal solution
-    /// (i.e. it is feasible and bounded), and the algorithm has found
-    /// optimal flow and node potentials (primal and dual solutions),
-    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
-    /// and infinite upper bound. It means that the objective function
-    /// is unbounded on that arc, however, note that it could actually be
-    /// bounded over the feasible flows, but this algroithm cannot handle
-    /// these cases.
-    ///
-    /// \see ProblemType
-    ProblemType run(int factor = 4) {
-      _factor = factor;
-      ProblemType pt = init();
-      if (pt != OPTIMAL) return pt;
-      return start();
-    }
-
-    /// \brief Reset all the parameters that have been given before.
-    ///
-    /// This function resets all the paramaters that have been given
-    /// before using functions \ref lowerMap(), \ref upperMap(),
-    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
-    ///
-    /// It is useful for multiple run() calls. If this function is not
-    /// used, all the parameters given before are kept for the next
-    /// \ref run() call.
-    /// However, the underlying digraph must not be modified after this
-    /// class have been constructed, since it copies and extends the graph.
-    ///
-    /// For example,
-    /// \code
-    ///   CapacityScaling<ListDigraph> cs(graph);
-    ///
-    ///   // First run
-    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
-    ///     .supplyMap(sup).run();
-    ///
-    ///   // Run again with modified cost map (reset() is not called,
-    ///   // so only the cost map have to be set again)
-    ///   cost[e] += 100;
-    ///   cs.costMap(cost).run();
-    ///
-    ///   // Run again from scratch using reset()
-    ///   // (the lower bounds will be set to zero on all arcs)
-    ///   cs.reset();
-    ///   cs.upperMap(capacity).costMap(cost)
-    ///     .supplyMap(sup).run();
-    /// \endcode
-    ///
-    /// \return <tt>(*this)</tt>
-    CapacityScaling& reset() {
-      for (int i = 0; i != _node_num; ++i) {
-        _supply[i] = 0;
-      }
-      for (int j = 0; j != _res_arc_num; ++j) {
-        _lower[j] = 0;
-        _upper[j] = INF;
-        _cost[j] = _forward[j] ? 1 : -1;
-      }
-      _have_lower = false;
+      resetParams();
       return *this;
     }
@@ -600 +647 @@
     ///
     /// This function returns the total cost of the found flow.
-    /// Its complexity is O(e).
+    /// Its complexity is O(m).
     ///
     /// \note The return type of the function can be specified as a
@@ -638 +685 @@
     }
 
-    /// \brief Return the flow map (the primal solution).
+    /// \brief Copy the flow values (the primal solution) into the
+    /// given map.
     ///
     /// This function copies the flow value on each arc into the given
@@ -662 +710 @@
     }
 
-    /// \brief Return the potential map (the dual solution).
+    /// \brief Copy the potential values (the dual solution) into the
+    /// given map.
     ///
     /// This function copies the potential (dual value) of each node
@@ -691 +740 @@
       }
       if (_sum_supply > 0) return INFEASIBLE;
-      
+
+      // Check lower and upper bounds
+      LEMON_DEBUG(checkBoundMaps(),
+          "Upper bounds must be greater or equal to the lower bounds");
+
+
       // Initialize vectors
       for (int i = 0; i != _root; ++i) {
@@ -701 +755 @@
       const Value MAX = std::numeric_limits<Value>::max();
       int last_out;
-      if (_have_lower) {
+      if (_has_lower) {
         for (int i = 0; i != _root; ++i) {
           last_out = _first_out[i+1];
@@ -739 +793 @@
         }
       }
-      
+
       // Handle GEQ supply type
       if (_sum_supply < 0) {
@@ -766 +820 @@
       if (_factor > 1) {
         // With scaling
-        Value max_sup = 0, max_dem = 0;
-        for (int i = 0; i != _node_num; ++i) {
+        Value max_sup = 0, max_dem = 0, max_cap = 0;
+        for (int i = 0; i != _root; ++i) {
           Value ex = _excess[i];
           if ( ex > max_sup) max_sup =  ex;
           if (-ex > max_dem) max_dem = -ex;
-        }
-        Value max_cap = 0;
-        for (int j = 0; j != _res_arc_num; ++j) {
-          if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
+          int last_out = _first_out[i+1] - 1;
+          for (int j = _first_out[i]; j != last_out; ++j) {
+            if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
+          }
         }
         max_sup = std::min(std::min(max_sup, max_dem), max_cap);
@@ -784 +838 @@
 
       return OPTIMAL;
+    }
+
+    // Check if the upper bound is greater than or equal to the lower bound
+    // on each forward arc.
+    bool checkBoundMaps() {
+      for (int j = 0; j != _res_arc_num; ++j) {
+        if (_forward[j] && _upper[j] < _lower[j]) return false;
+      }
+      return true;
     }
 
@@ -795 +858 @@
 
       // Handle non-zero lower bounds
-      if (_have_lower) {
+      if (_has_lower) {
         int limit = _first_out[_root];
         for (int j = 0; j != limit; ++j) {
-          if (!_forward[j]) _res_cap[j] += _lower[j];
+          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
         }
       }
@@ -807 +870 @@
         for (int i = 0; i != _node_num; ++i) {
           _pi[i] -= pr;
-        }        
-      }
-      
+        }
+      }
+
       return pt;
     }