LEMON/LEMON-official Changeset - r898:75c97c3786d6

Repositories » LEMON » LEMON-official

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

Changeset - r898:75c97c3786d6

« 889:a7e93d

899:cc9e0c »

r898:75c97c3786d6

Wed, 10 Feb 2010 19:05:20

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Handle graph changes in the MCF algorithms (#327) The reset() functions are renamed to resetParams() and the new reset() functions handle the graph chnages, as well.

0 5 0

default

5 files changed with 423 insertions and 311 deletions:

lemon/capacity_scaling.h

107

lemon/cost_scaling.h

104

lemon/cycle_canceling.h

109

lemon/network_simplex.h

test/min_cost_flow_test.cc

↑ Collapse diff ↑

lemon/capacity_scaling.h

Show inline comments

@@ -293,111 +293,49 @@
 		      typedef  CapacityScaling<GR, V, C, SetHeapTraits<T> > Create;
 		    };
 		    /// @}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    CapacityScaling(const GR& graph) :
 		      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
 		      INF(std::numeric_limits<Value>::has_infinity ?
 		          std::numeric_limits<Value>::infinity() :
 		          std::numeric_limits<Value>::max())
+		    {
 		      // Check the number types
 		      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
 		        "The flow type of CapacityScaling must be signed");
 		      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
 		        "The cost type of CapacityScaling must be signed");
 		      // Resize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      _res_arc_num = 2 * (_arc_num + _node_num);
 		      _root = _node_num;
 		      ++_node_num;
 		      _first_out.resize(_node_num + 1);
 		      _forward.resize(_res_arc_num);
 		      _source.resize(_res_arc_num);
 		      _target.resize(_res_arc_num);
 		      _reverse.resize(_res_arc_num);
 		      _lower.resize(_res_arc_num);
 		      _upper.resize(_res_arc_num);
 		      _cost.resize(_res_arc_num);
 		      _supply.resize(_node_num);
 		      _res_cap.resize(_res_arc_num);
 		      _pi.resize(_node_num);
 		      _excess.resize(_node_num);
 		      _pred.resize(_node_num);
 		      // Copy the graph
 		      int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _node_id[n] = i;
+		      }
 		      i = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _first_out[i] = j;
 		        for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idf[a] = j;
 		          _forward[j] = true;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idb[a] = j;
 		          _forward[j] = false;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        _forward[j] = false;
 		        _source[j] = i;
 		        _target[j] = _root;
 		        _reverse[j] = k;
 		        _forward[k] = true;
 		        _source[k] = _root;
 		        _target[k] = i;
 		        _reverse[k] = j;
 		        ++j; ++k;
+		      }
 		      _first_out[i] = j;
 		      _first_out[_node_num] = k;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int fi = _arc_idf[a];
 		        int bi = _arc_idb[a];
 		        _reverse[fi] = bi;
 		        _reverse[bi] = fi;
+		      }
-		      // Reset parameters
+		      // 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) {
 		      _have_lower = true;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
@@ -490,123 +428,214 @@
 		      _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.
 		    /// 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 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.
+		    /// 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 (reset() is not called,
+		    ///   // 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 reset()
+		    ///   // Run again from scratch using resetParams()
 		    ///   // (the lower bounds will be set to zero on all arcs)
-		    ///   cs.reset();
+		    ///   cs.resetParams();
 		    ///   cs.upperMap(capacity).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// \return <tt>(*this)</tt>
-		    CapacityScaling& reset() {
+		    ///
 		    /// \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;
+		      }
 		      _have_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);
 		      _arc_num = countArcs(_graph);
 		      _res_arc_num = 2 * (_arc_num + _node_num);
 		      _root = _node_num;
 		      ++_node_num;
 		      _first_out.resize(_node_num + 1);
 		      _forward.resize(_res_arc_num);
 		      _source.resize(_res_arc_num);
 		      _target.resize(_res_arc_num);
 		      _reverse.resize(_res_arc_num);
 		      _lower.resize(_res_arc_num);
 		      _upper.resize(_res_arc_num);
 		      _cost.resize(_res_arc_num);
 		      _supply.resize(_node_num);
 		      _res_cap.resize(_res_arc_num);
 		      _pi.resize(_node_num);
 		      _excess.resize(_node_num);
 		      _pred.resize(_node_num);
 		      // Copy the graph
 		      int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _node_id[n] = i;
+		      }
 		      i = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _first_out[i] = j;
 		        for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idf[a] = j;
 		          _forward[j] = true;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idb[a] = j;
 		          _forward[j] = false;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        _forward[j] = false;
 		        _source[j] = i;
 		        _target[j] = _root;
 		        _reverse[j] = k;
 		        _forward[k] = true;
 		        _source[k] = _root;
 		        _target[k] = i;
 		        _reverse[k] = j;
 		        ++j; ++k;
+		      }
 		      _first_out[i] = j;
 		      _first_out[_node_num] = k;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int fi = _arc_idf[a];
 		        int bi = _arc_idb[a];
 		        _reverse[fi] = bi;
 		        _reverse[bi] = fi;
+		      }
 		      // Reset parameters
 		      resetParams();
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.\n
 		    /// The \ref run() function must be called before using them.
 		    /// @{
 		    /// \brief Return the total cost of the found flow.
 		    ///
 		    /// This function returns the total cost of the found flow.
 		    /// Its complexity is O(e).
 		    ///
 		    /// \note The return type of the function can be specified as a
 		    /// template parameter. For example,
 		    /// \code
 		    ///   cs.totalCost<double>();
 		    /// \endcode
 		    /// It is useful if the total cost cannot be stored in the \c Cost
 		    /// type of the algorithm, which is the default return type of the
 		    /// function.
 		    ///
 		    /// \pre \ref run() must be called before using this function.

lemon/cost_scaling.h

Show inline comments

@@ -311,116 +311,50 @@
 		      typedef  CostScaling<GR, V, C, SetLargeCostTraits<T> > Create;
 		    };
 		    /// @}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    CostScaling(const GR& graph) :
 		      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
 		      _cost_map(_cost_vec), _pi_map(_pi),
 		      INF(std::numeric_limits<Value>::has_infinity ?
 		          std::numeric_limits<Value>::infinity() :
 		          std::numeric_limits<Value>::max())
+		    {
 		      // Check the number types
 		      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
 		        "The flow type of CostScaling must be signed");
 		      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
 		        "The cost type of CostScaling must be signed");
 		      // Resize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      _res_node_num = _node_num + 1;
 		      _res_arc_num = 2 * (_arc_num + _node_num);
 		      _root = _node_num;
 		      _first_out.resize(_res_node_num + 1);
 		      _forward.resize(_res_arc_num);
 		      _source.resize(_res_arc_num);
 		      _target.resize(_res_arc_num);
 		      _reverse.resize(_res_arc_num);
 		      _lower.resize(_res_arc_num);
 		      _upper.resize(_res_arc_num);
 		      _scost.resize(_res_arc_num);
 		      _supply.resize(_res_node_num);
 		      _res_cap.resize(_res_arc_num);
 		      _cost.resize(_res_arc_num);
 		      _pi.resize(_res_node_num);
 		      _excess.resize(_res_node_num);
 		      _next_out.resize(_res_node_num);
 		      _arc_vec.reserve(_res_arc_num);
 		      _cost_vec.reserve(_res_arc_num);
 		      // Copy the graph
 		      int i = 0, j = 0, k = 2 * _arc_num + _node_num;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _node_id[n] = i;
+		      }
 		      i = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _first_out[i] = j;
 		        for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idf[a] = j;
 		          _forward[j] = true;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idb[a] = j;
 		          _forward[j] = false;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        _forward[j] = false;
 		        _source[j] = i;
 		        _target[j] = _root;
 		        _reverse[j] = k;
 		        _forward[k] = true;
 		        _source[k] = _root;
 		        _target[k] = i;
 		        _reverse[k] = j;
 		        ++j; ++k;
+		      }
 		      _first_out[i] = j;
 		      _first_out[_res_node_num] = k;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int fi = _arc_idf[a];
 		        int bi = _arc_idb[a];
 		        _reverse[fi] = bi;
 		        _reverse[bi] = fi;
+		      }
-		      // Reset parameters
+		      // 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>
 		    CostScaling& lowerMap(const LowerMap& map) {
 		      _have_lower = true;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
@@ -513,131 +447,219 @@
 		      _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
 		    ///   CostScaling<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.
 		    /// 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 method The internal method that will be used in the
 		    /// algorithm. For more information, see \ref Method.
 		    /// \param factor The cost scaling factor. It must be larger than one.
 		    ///
 		    /// \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, Method
 		    /// \see resetParams(), reset()
 		    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
 		      _alpha = factor;
 		      ProblemType pt = init();
 		      if (pt != OPTIMAL) return pt;
 		      start(method);
 		      return OPTIMAL;
+		    }
 		    /// \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.
+		    /// 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
 		    ///   CostScaling<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,
+		    ///   // 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 reset()
+		    ///   // Run again from scratch using resetParams()
 		    ///   // (the lower bounds will be set to zero on all arcs)
-		    ///   cs.reset();
+		    ///   cs.resetParams();
 		    ///   cs.upperMap(capacity).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// \return <tt>(*this)</tt>
-		    CostScaling& reset() {
+		    ///
 		    /// \see reset(), run()
 		    CostScaling& resetParams() {
 		      for (int i = 0; i != _res_node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      int limit = _first_out[_root];
 		      for (int j = 0; j != limit; ++j) {
 		        _lower[j] = 0;
 		        _upper[j] = INF;
 		        _scost[j] = _forward[j] ? 1 : -1;
+		      }
 		      for (int j = limit; j != _res_arc_num; ++j) {
 		        _lower[j] = 0;
 		        _upper[j] = INF;
 		        _scost[j] = 0;
 		        _scost[_reverse[j]] = 0;
+		      }
 		      _have_lower = false;
 		      return *this;
+		    }
 		    /// \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.
 		    /// \return <tt>(*this)</tt>
 		    CostScaling& reset() {
 		      // Resize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      _res_node_num = _node_num + 1;
 		      _res_arc_num = 2 * (_arc_num + _node_num);
 		      _root = _node_num;
 		      _first_out.resize(_res_node_num + 1);
 		      _forward.resize(_res_arc_num);
 		      _source.resize(_res_arc_num);
 		      _target.resize(_res_arc_num);
 		      _reverse.resize(_res_arc_num);
 		      _lower.resize(_res_arc_num);
 		      _upper.resize(_res_arc_num);
 		      _scost.resize(_res_arc_num);
 		      _supply.resize(_res_node_num);
 		      _res_cap.resize(_res_arc_num);
 		      _cost.resize(_res_arc_num);
 		      _pi.resize(_res_node_num);
 		      _excess.resize(_res_node_num);
 		      _next_out.resize(_res_node_num);
 		      _arc_vec.reserve(_res_arc_num);
 		      _cost_vec.reserve(_res_arc_num);
 		      // Copy the graph
 		      int i = 0, j = 0, k = 2 * _arc_num + _node_num;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _node_id[n] = i;
+		      }
 		      i = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _first_out[i] = j;
 		        for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idf[a] = j;
 		          _forward[j] = true;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idb[a] = j;
 		          _forward[j] = false;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        _forward[j] = false;
 		        _source[j] = i;
 		        _target[j] = _root;
 		        _reverse[j] = k;
 		        _forward[k] = true;
 		        _source[k] = _root;
 		        _target[k] = i;
 		        _reverse[k] = j;
 		        ++j; ++k;
+		      }
 		      _first_out[i] = j;
 		      _first_out[_res_node_num] = k;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int fi = _arc_idf[a];
 		        int bi = _arc_idb[a];
 		        _reverse[fi] = bi;
 		        _reverse[bi] = fi;
+		      }
 		      // Reset parameters
 		      resetParams();
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.\n
 		    /// The \ref run() function must be called before using them.
 		    /// @{
 		    /// \brief Return the total cost of the found flow.
 		    ///
 		    /// This function returns the total cost of the found flow.
 		    /// Its complexity is O(e).
 		    ///
 		    /// \note The return type of the function can be specified as a
 		    /// template parameter. For example,
 		    /// \code
 		    ///   cs.totalCost<double>();
 		    /// \endcode
 		    /// It is useful if the total cost cannot be stored in the \c Cost
 		    /// type of the algorithm, which is the default return type of the
 		    /// function.
 		    ///
 		    /// \pre \ref run() must be called before using this function.

lemon/cycle_canceling.h

Show inline comments

@@ -229,113 +229,49 @@
 		    /// It is \c std::numeric_limits<Value>::infinity() if available,
 		    /// \c std::numeric_limits<Value>::max() otherwise.
 		    const Value INF;
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    CycleCanceling(const GR& graph) :
 		      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
 		      _cost_map(_cost_vec), _pi_map(_pi),
 		      INF(std::numeric_limits<Value>::has_infinity ?
 		          std::numeric_limits<Value>::infinity() :
 		          std::numeric_limits<Value>::max())
+		    {
 		      // Check the number types
 		      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
 		        "The flow type of CycleCanceling must be signed");
 		      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
 		        "The cost type of CycleCanceling must be signed");
 		      // Resize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      _res_node_num = _node_num + 1;
 		      _res_arc_num = 2 * (_arc_num + _node_num);
 		      _root = _node_num;
 		      _first_out.resize(_res_node_num + 1);
 		      _forward.resize(_res_arc_num);
 		      _source.resize(_res_arc_num);
 		      _target.resize(_res_arc_num);
 		      _reverse.resize(_res_arc_num);
 		      _lower.resize(_res_arc_num);
 		      _upper.resize(_res_arc_num);
 		      _cost.resize(_res_arc_num);
 		      _supply.resize(_res_node_num);
 		      _res_cap.resize(_res_arc_num);
 		      _pi.resize(_res_node_num);
 		      _arc_vec.reserve(_res_arc_num);
 		      _cost_vec.reserve(_res_arc_num);
 		      _id_vec.reserve(_res_arc_num);
 		      // Copy the graph
 		      int i = 0, j = 0, k = 2 * _arc_num + _node_num;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _node_id[n] = i;
+		      }
 		      i = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _first_out[i] = j;
 		        for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idf[a] = j;
 		          _forward[j] = true;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idb[a] = j;
 		          _forward[j] = false;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        _forward[j] = false;
 		        _source[j] = i;
 		        _target[j] = _root;
 		        _reverse[j] = k;
 		        _forward[k] = true;
 		        _source[k] = _root;
 		        _target[k] = i;
 		        _reverse[k] = j;
 		        ++j; ++k;
+		      }
 		      _first_out[i] = j;
 		      _first_out[_res_node_num] = k;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int fi = _arc_idf[a];
 		        int bi = _arc_idb[a];
 		        _reverse[fi] = bi;
 		        _reverse[bi] = fi;
+		      }
-		      // Reset parameters
+		      // 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>
 		    CycleCanceling& lowerMap(const LowerMap& map) {
 		      _have_lower = true;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
@@ -428,129 +364,222 @@
 		      _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
 		    ///   CycleCanceling<ListDigraph> cc(graph);
 		    ///   cc.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.
 		    /// 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 method The cycle-canceling method that will be used.
 		    /// For more information, see \ref Method.
 		    ///
 		    /// \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, Method
 		    /// \see resetParams(), reset()
 		    ProblemType run(Method method = CANCEL_AND_TIGHTEN) {
 		      ProblemType pt = init();
 		      if (pt != OPTIMAL) return pt;
 		      start(method);
 		      return OPTIMAL;
+		    }
 		    /// \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.
+		    /// 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
 		    ///   CycleCanceling<ListDigraph> cs(graph);
 		    ///
 		    ///   // First run
 		    ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    ///
-		    ///   // Run again with modified cost map (reset() is not called,
+		    ///   // Run again with modified cost map (resetParams() is not called,
 		    ///   // so only the cost map have to be set again)
 		    ///   cost[e] += 100;
 		    ///   cc.costMap(cost).run();
 		    ///
-		    ///   // Run again from scratch using reset()
+		    ///   // Run again from scratch using resetParams()
 		    ///   // (the lower bounds will be set to zero on all arcs)
-		    ///   cc.reset();
+		    ///   cc.resetParams();
 		    ///   cc.upperMap(capacity).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// \return <tt>(*this)</tt>
-		    CycleCanceling& reset() {
+		    ///
 		    /// \see reset(), run()
 		    CycleCanceling& resetParams() {
 		      for (int i = 0; i != _res_node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      int limit = _first_out[_root];
 		      for (int j = 0; j != limit; ++j) {
 		        _lower[j] = 0;
 		        _upper[j] = INF;
 		        _cost[j] = _forward[j] ? 1 : -1;
+		      }
 		      for (int j = limit; j != _res_arc_num; ++j) {
 		        _lower[j] = 0;
 		        _upper[j] = INF;
 		        _cost[j] = 0;
 		        _cost[_reverse[j]] = 0;
+		      }
 		      _have_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()
 		    CycleCanceling& reset() {
 		      // Resize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      _res_node_num = _node_num + 1;
 		      _res_arc_num = 2 * (_arc_num + _node_num);
 		      _root = _node_num;
 		      _first_out.resize(_res_node_num + 1);
 		      _forward.resize(_res_arc_num);
 		      _source.resize(_res_arc_num);
 		      _target.resize(_res_arc_num);
 		      _reverse.resize(_res_arc_num);
 		      _lower.resize(_res_arc_num);
 		      _upper.resize(_res_arc_num);
 		      _cost.resize(_res_arc_num);
 		      _supply.resize(_res_node_num);
 		      _res_cap.resize(_res_arc_num);
 		      _pi.resize(_res_node_num);
 		      _arc_vec.reserve(_res_arc_num);
 		      _cost_vec.reserve(_res_arc_num);
 		      _id_vec.reserve(_res_arc_num);
 		      // Copy the graph
 		      int i = 0, j = 0, k = 2 * _arc_num + _node_num;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _node_id[n] = i;
+		      }
 		      i = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _first_out[i] = j;
 		        for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idf[a] = j;
 		          _forward[j] = true;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idb[a] = j;
 		          _forward[j] = false;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        _forward[j] = false;
 		        _source[j] = i;
 		        _target[j] = _root;
 		        _reverse[j] = k;
 		        _forward[k] = true;
 		        _source[k] = _root;
 		        _target[k] = i;
 		        _reverse[k] = j;
 		        ++j; ++k;
+		      }
 		      _first_out[i] = j;
 		      _first_out[_res_node_num] = k;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int fi = _arc_idf[a];
 		        int bi = _arc_idb[a];
 		        _reverse[fi] = bi;
 		        _reverse[bi] = fi;
+		      }
 		      // Reset parameters
 		      resetParams();
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.\n
 		    /// The \ref run() function must be called before using them.
 		    /// @{
 		    /// \brief Return the total cost of the found flow.
 		    ///
 		    /// This function returns the total cost of the found flow.
 		    /// Its complexity is O(e).
 		    ///
 		    /// \note The return type of the function can be specified as a
 		    /// template parameter. For example,
 		    /// \code
 		    ///   cc.totalCost<double>();
 		    /// \endcode
 		    /// It is useful if the total cost cannot be stored in the \c Cost
 		    /// type of the algorithm, which is the default return type of the
 		    /// function.
 		    ///
 		    /// \pre \ref run() must be called before using this function.

lemon/network_simplex.h

Show inline comments

@@ -173,48 +173,49 @@
 		      STATE_UPPER = -1,
 		      STATE_TREE  =  0,
 		      STATE_LOWER =  1
 		    };
 		  private:
 		    // Data related to the underlying digraph
 		    const GR &_graph;
 		    int _node_num;
 		    int _arc_num;
 		    int _all_arc_num;
 		    int _search_arc_num;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    SupplyType _stype;
 		    Value _sum_supply;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    IntArcMap _arc_id;
 		    IntVector _source;
 		    IntVector _target;
 		    bool _arc_mixing;
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    ValueVector _cap;
 		    CostVector _cost;
 		    ValueVector _supply;
 		    ValueVector _flow;
 		    CostVector _pi;
 		    // Data for storing the spanning tree structure
 		    IntVector _parent;
 		    IntVector _pred;
 		    IntVector _thread;
 		    IntVector _rev_thread;
 		    IntVector _succ_num;
 		    IntVector _last_succ;
 		    IntVector _dirty_revs;
 		    CharVector _forward;
 		    CharVector _state;
 		    int _root;
 		    // Temporary data used in the current pivot iteration
 		    int in_arc, join, u_in, v_in, u_out, v_out;
@@ -612,110 +613,60 @@
 		        // Pop the first element of the heap
 		        _in_arc = _candidates[0];
 		        _next_arc = e;
 		        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
 		                  _sort_func );
 		        _curr_length = std::min(_head_length, _curr_length - 1);
 		        return true;
+		      }
 		    }; //class AlteringListPivotRule
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    /// \param arc_mixing Indicate if the arcs have to be stored in a
 		    /// mixed order in the internal data structure.
 		    /// In special cases, it could lead to better overall performance,
 		    /// but it is usually slower. Therefore it is disabled by default.
 		    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
 		      _graph(graph), _node_id(graph), _arc_id(graph),
 		      _arc_mixing(arc_mixing),
 		      MAX(std::numeric_limits<Value>::max()),
 		      INF(std::numeric_limits<Value>::has_infinity ?
 		          std::numeric_limits<Value>::infinity() : MAX)
+		    {
 		      // Check the number types
 		      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
 		        "The flow type of NetworkSimplex must be signed");
 		      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
 		        "The cost type of NetworkSimplex must be signed");
 		      // Resize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      int all_node_num = _node_num + 1;
 		      int max_arc_num = _arc_num + 2 * _node_num;
 		      _source.resize(max_arc_num);
 		      _target.resize(max_arc_num);
 		      _lower.resize(_arc_num);
 		      _upper.resize(_arc_num);
 		      _cap.resize(max_arc_num);
 		      _cost.resize(max_arc_num);
 		      _supply.resize(all_node_num);
 		      _flow.resize(max_arc_num);
 		      _pi.resize(all_node_num);
 		      _parent.resize(all_node_num);
 		      _pred.resize(all_node_num);
 		      _forward.resize(all_node_num);
 		      _thread.resize(all_node_num);
 		      _rev_thread.resize(all_node_num);
 		      _succ_num.resize(all_node_num);
 		      _last_succ.resize(all_node_num);
 		      _state.resize(max_arc_num);
 		      // Copy the graph
 		      int i = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _node_id[n] = i;
+		      }
 		      if (arc_mixing) {
 		        // Store the arcs in a mixed order
 		        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
 		        int i = 0, j = 0;
 		        for (ArcIt a(_graph); a != INVALID; ++a) {
 		          _arc_id[a] = i;
 		          _source[i] = _node_id[_graph.source(a)];
 		          _target[i] = _node_id[_graph.target(a)];
 		          if ((i += k) >= _arc_num) i = ++j;
+		        }
 		      } else {
 		        // Store the arcs in the original order
 		        int i = 0;
 		        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
 		          _arc_id[a] = i;
 		          _source[i] = _node_id[_graph.source(a)];
 		          _target[i] = _node_id[_graph.target(a)];
+		        }
+		      }
 		      // Reset parameters
 		      // 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>
 		    NetworkSimplex& lowerMap(const LowerMap& map) {
 		      _have_lower = true;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
@@ -821,119 +772,200 @@
 		      _stype = supply_type;
 		      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(),
 		    /// \ref supplyType().
 		    /// For example,
 		    /// \code
 		    ///   NetworkSimplex<ListDigraph> ns(graph);
 		    ///   ns.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.
 		    /// 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 pivot_rule The pivot rule that will be used during the
 		    /// algorithm. For more information, see \ref PivotRule.
 		    ///
 		    /// \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 objective function of the problem is
 		    /// unbounded, i.e. there is a directed cycle having negative total
 		    /// cost and infinite upper bound.
 		    ///
 		    /// \see ProblemType, PivotRule
 		    /// \see resetParams(), reset()
 		    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
 		      if (!init()) return INFEASIBLE;
 		      return start(pivot_rule);
+		    }
 		    /// \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(), \ref supplyType().
 		    ///
 		    /// 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.
+		    /// 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
 		    ///   NetworkSimplex<ListDigraph> ns(graph);
 		    ///
 		    ///   // First run
 		    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    ///
-		    ///   // Run again with modified cost map (reset() is not called,
+		    ///   // Run again with modified cost map (resetParams() is not called,
 		    ///   // so only the cost map have to be set again)
 		    ///   cost[e] += 100;
 		    ///   ns.costMap(cost).run();
 		    ///
-		    ///   // Run again from scratch using reset()
+		    ///   // Run again from scratch using resetParams()
 		    ///   // (the lower bounds will be set to zero on all arcs)
-		    ///   ns.reset();
+		    ///   ns.resetParams();
 		    ///   ns.upperMap(capacity).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// \return <tt>(*this)</tt>
-		    NetworkSimplex& reset() {
+		    ///
 		    /// \see reset(), run()
 		    NetworkSimplex& resetParams() {
 		      for (int i = 0; i != _node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      for (int i = 0; i != _arc_num; ++i) {
 		        _lower[i] = 0;
 		        _upper[i] = INF;
 		        _cost[i] = 1;
+		      }
 		      _have_lower = false;
 		      _stype = GEQ;
 		      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(),
 		    /// \ref supplyType().
 		    ///
 		    /// 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()
 		    NetworkSimplex& reset() {
 		      // Resize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      int all_node_num = _node_num + 1;
 		      int max_arc_num = _arc_num + 2 * _node_num;
 		      _source.resize(max_arc_num);
 		      _target.resize(max_arc_num);
 		      _lower.resize(_arc_num);
 		      _upper.resize(_arc_num);
 		      _cap.resize(max_arc_num);
 		      _cost.resize(max_arc_num);
 		      _supply.resize(all_node_num);
 		      _flow.resize(max_arc_num);
 		      _pi.resize(all_node_num);
 		      _parent.resize(all_node_num);
 		      _pred.resize(all_node_num);
 		      _forward.resize(all_node_num);
 		      _thread.resize(all_node_num);
 		      _rev_thread.resize(all_node_num);
 		      _succ_num.resize(all_node_num);
 		      _last_succ.resize(all_node_num);
 		      _state.resize(max_arc_num);
 		      // Copy the graph
 		      int i = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _node_id[n] = i;
+		      }
 		      if (_arc_mixing) {
 		        // Store the arcs in a mixed order
 		        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
 		        int i = 0, j = 0;
 		        for (ArcIt a(_graph); a != INVALID; ++a) {
 		          _arc_id[a] = i;
 		          _source[i] = _node_id[_graph.source(a)];
 		          _target[i] = _node_id[_graph.target(a)];
 		          if ((i += k) >= _arc_num) i = ++j;
+		        }
 		      } else {
 		        // Store the arcs in the original order
 		        int i = 0;
 		        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
 		          _arc_id[a] = i;
 		          _source[i] = _node_id[_graph.source(a)];
 		          _target[i] = _node_id[_graph.target(a)];
+		        }
+		      }
 		      // Reset parameters
 		      resetParams();
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.\n
 		    /// The \ref run() function must be called before using them.
 		    /// @{
 		    /// \brief Return the total cost of the found flow.
 		    ///
 		    /// This function returns the total cost of the found flow.
 		    /// Its complexity is O(e).
 		    ///
 		    /// \note The return type of the function can be specified as a
 		    /// template parameter. For example,
 		    /// \code
 		    ///   ns.totalCost<double>();
 		    /// \endcode
 		    /// It is useful if the total cost cannot be stored in the \c Cost
 		    /// type of the algorithm, which is the default return type of the
 		    /// function.
 		    ///
 		    /// \pre \ref run() must be called before using this function.

test/min_cost_flow_test.cc

Show inline comments

@@ -136,49 +136,49 @@
 		enum SupplyType {
 		  EQ,
 		  GEQ,
 		  LEQ
 		};
 		// Check the interface of an MCF algorithm
 		template <typename GR, typename Value, typename Cost>
 		class McfClassConcept
+		{
 		public:
 		  template <typename MCF>
 		  struct Constraints {
 		    void constraints() {
 		      checkConcept<concepts::Digraph, GR>();
 		      const Constraints& me = *this;
 		      MCF mcf(me.g);
 		      const MCF& const_mcf = mcf;
 		      b = mcf.reset()
+		      b = mcf.reset().resetParams()
 		             .lowerMap(me.lower)
 		             .upperMap(me.upper)
 		             .costMap(me.cost)
 		             .supplyMap(me.sup)
 		             .stSupply(me.n, me.n, me.k)
 		             .run();
 		      c = const_mcf.totalCost();
 		      x = const_mcf.template totalCost<double>();
 		      v = const_mcf.flow(me.a);
 		      c = const_mcf.potential(me.n);
 		      const_mcf.flowMap(fm);
 		      const_mcf.potentialMap(pm);
+		    }
 		    typedef typename GR::Node Node;
 		    typedef typename GR::Arc Arc;
 		    typedef concepts::ReadMap<Node, Value> NM;
 		    typedef concepts::ReadMap<Arc, Value> VAM;
 		    typedef concepts::ReadMap<Arc, Cost> CAM;
 		    typedef concepts::WriteMap<Arc, Value> FlowMap;
 		    typedef concepts::WriteMap<Node, Cost> PotMap;
 		    GR g;
@@ -325,83 +325,83 @@
 		          "Wrong dual cost " + test_id);
+		  }
+		}
 		template < typename MCF, typename Param >
 		void runMcfGeqTests( Param param,
 		                     const std::string &test_str = "",
 		                     bool full_neg_cost_support = false )
+		{
 		  MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr);
 		  // Basic tests
 		  mcf1.upperMap(u).costMap(c).supplyMap(s1);
 		  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s1,
 		           mcf1.OPTIMAL, true,     5240, test_str + "-1");
 		  mcf1.stSupply(v, w, 27);
 		  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s2,
 		           mcf1.OPTIMAL, true,     7620, test_str + "-2");
 		  mcf1.lowerMap(l2).supplyMap(s1);
 		  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s1,
 		           mcf1.OPTIMAL, true,     5970, test_str + "-3");
 		  mcf1.stSupply(v, w, 27);
 		  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2,
 		           mcf1.OPTIMAL, true,     8010, test_str + "-4");
-		  mcf1.reset().supplyMap(s1);
+		  mcf1.resetParams().supplyMap(s1);
 		  checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1,
 		           mcf1.OPTIMAL, true,       74, test_str + "-5");
 		  mcf1.lowerMap(l2).stSupply(v, w, 27);
 		  checkMcf(mcf1, mcf1.run(param), gr, l2, cu, cc, s2,
 		           mcf1.OPTIMAL, true,       94, test_str + "-6");
 		  mcf1.reset();
 		  checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s3,
 		           mcf1.OPTIMAL, true,        0, test_str + "-7");
 		  mcf1.lowerMap(l2).upperMap(u);
 		  checkMcf(mcf1, mcf1.run(param), gr, l2, u, cc, s3,
 		           mcf1.INFEASIBLE, false,    0, test_str + "-8");
 		  mcf1.lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
 		  checkMcf(mcf1, mcf1.run(param), gr, l3, u, c, s4,
 		           mcf1.OPTIMAL, true,     6360, test_str + "-9");
 		  // Tests for the GEQ form
-		  mcf1.reset().upperMap(u).costMap(c).supplyMap(s5);
+		  mcf1.resetParams().upperMap(u).costMap(c).supplyMap(s5);
 		  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5,
 		           mcf1.OPTIMAL, true,     3530, test_str + "-10", GEQ);
 		  mcf1.lowerMap(l2);
 		  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,
 		           mcf1.OPTIMAL, true,     4540, test_str + "-11", GEQ);
 		  mcf1.supplyMap(s6);
 		  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,
 		           mcf1.INFEASIBLE, false,    0, test_str + "-12", GEQ);
 		  // Tests with negative costs
 		  mcf2.lowerMap(neg1_l1).costMap(neg1_c).supplyMap(neg1_s);
 		  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u1, neg1_c, neg1_s,
 		           mcf2.UNBOUNDED, false,     0, test_str + "-13");
 		  mcf2.upperMap(neg1_u2);
 		  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s,
 		           mcf2.OPTIMAL, true,   -40000, test_str + "-14");
-		  mcf2.reset().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
+		  mcf2.resetParams().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
 		  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s,
 		           mcf2.UNBOUNDED, false,     0, test_str + "-15");
 		  mcf3.costMap(neg2_c).supplyMap(neg2_s);
 		  if (full_neg_cost_support) {
 		    checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
 		             mcf3.OPTIMAL, true,   -300, test_str + "-16", GEQ);
 		  } else {
 		    checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
 		             mcf3.UNBOUNDED, false,   0, test_str + "-17", GEQ);
+		  }
 		  mcf3.upperMap(neg2_u);
 		  checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
 		           mcf3.OPTIMAL, true,     -300, test_str + "-18", GEQ);
+		}
 		template < typename MCF, typename Param >
 		void runMcfLeqTests( Param param,
 		                     const std::string &test_str = "" )
+		{
 		  // Tests for the LEQ form
 		  MCF mcf1(gr);
 		  mcf1.supplyType(mcf1.LEQ);
 		  mcf1.upperMap(u).costMap(c).supplyMap(s6);

0 comments (0 inline)

RhodeCode

Login to your account