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

@@ -269,159 +269,97 @@
 		    }; //class ResidualDijkstra
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetHeapTraits : public Traits {
 		      typedef T Heap;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c Heap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c Heap
 		    /// type, which is used for internal Dijkstra computations.
 		    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
 		    /// its priority type must be \c Cost and its cross reference type
 		    /// must be \ref RangeMap "RangeMap<int>".
 		    template <typename T>
 		    struct SetHeap
 		      : public CapacityScaling<GR, V, C, SetHeapTraits<T> > {
 		      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) {
 		        _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;
@@ -466,171 +404,262 @@
 		      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.
 		    /// 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.
 		    template <typename Number>
 		    Number totalCost() const {
 		      Number c = 0;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int i = _arc_idb[a];
 		        c += static_cast<Number>(_res_cap[i]) *
 		             (-static_cast<Number>(_cost[i]));
+		      }
 		      return c;
+		    }
 		#ifndef DOXYGEN
 		    Cost totalCost() const {
 		      return totalCost<Cost>();
+		    }
 		#endif
 		    /// \brief Return the flow on the given arc.
 		    ///
 		    /// This function returns the flow on the given arc.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Value flow(const Arc& a) const {
 		      return _res_cap[_arc_idb[a]];

lemon/cost_scaling.h

Show inline comments

@@ -287,164 +287,98 @@
 		    /// Constant for infinite upper bounds (capacities).
 		    /// It is \c std::numeric_limits<Value>::infinity() if available,
 		    /// \c std::numeric_limits<Value>::max() otherwise.
 		    const Value INF;
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetLargeCostTraits : public Traits {
 		      typedef T LargeCost;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c LargeCost type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c LargeCost
 		    /// type, which is used for internal computations in the algorithm.
 		    /// \c Cost must be convertible to \c LargeCost.
 		    template <typename T>
 		    struct SetLargeCost
 		      : public CostScaling<GR, V, C, SetLargeCostTraits<T> > {
 		      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) {
 		        _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>
 		    CostScaling& upperMap(const UpperMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _upper[_arc_idf[a]] = map[a];
+		      }
 		      return *this;
@@ -489,179 +423,267 @@
 		      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>
 		    CostScaling& stSupply(const Node& s, const Node& t, Value k) {
 		      for (int i = 0; i != _res_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
 		    ///   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.
 		    template <typename Number>
 		    Number totalCost() const {
 		      Number c = 0;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int i = _arc_idb[a];
 		        c += static_cast<Number>(_res_cap[i]) *
 		             (-static_cast<Number>(_scost[i]));
+		      }
 		      return c;
+		    }
 		#ifndef DOXYGEN
 		    Cost totalCost() const {
 		      return totalCost<Cost>();
+		    }
 		#endif
 		    /// \brief Return the flow on the given arc.
 		    ///
 		    /// This function returns the flow on the given arc.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Value flow(const Arc& a) const {
 		      return _res_cap[_arc_idb[a]];

lemon/cycle_canceling.h

Show inline comments

@@ -205,161 +205,97 @@
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    CostVector _cost;
 		    ValueVector _supply;
 		    ValueVector _res_cap;
 		    CostVector _pi;
 		    // Data for a StaticDigraph structure
 		    typedef std::pair<int, int> IntPair;
 		    StaticDigraph _sgr;
 		    std::vector<IntPair> _arc_vec;
 		    std::vector<Cost> _cost_vec;
 		    IntVector _id_vec;
 		    CostArcMap _cost_map;
 		    CostNodeMap _pi_map;
 		  public:
 		    /// \brief Constant for infinite upper bounds (capacities).
 		    ///
 		    /// Constant for infinite upper bounds (capacities).
 		    /// 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) {
 		        _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>
 		    CycleCanceling& upperMap(const UpperMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _upper[_arc_idf[a]] = map[a];
+		      }
 		      return *this;
@@ -404,177 +340,270 @@
 		      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>
 		    CycleCanceling& stSupply(const Node& s, const Node& t, Value k) {
 		      for (int i = 0; i != _res_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
 		    ///   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.
 		    template <typename Number>
 		    Number totalCost() const {
 		      Number c = 0;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int i = _arc_idb[a];
 		        c += static_cast<Number>(_res_cap[i]) *
 		             (-static_cast<Number>(_cost[i]));
+		      }
 		      return c;
+		    }
 		#ifndef DOXYGEN
 		    Cost totalCost() const {
 		      return totalCost<Cost>();
+		    }
 		#endif
 		    /// \brief Return the flow on the given arc.
 		    ///
 		    /// This function returns the flow on the given arc.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Value flow(const Arc& a) const {
 		      return _res_cap[_arc_idb[a]];

lemon/network_simplex.h

Show inline comments

@@ -149,96 +149,97 @@
 		      /// The \e Candidate \e List pivot rule.
 		      /// In a major iteration a candidate list is built from eligible arcs
 		      /// in a wraparound fashion and in the following minor iterations
 		      /// the best eligible arc is selected from this list.
 		      CANDIDATE_LIST,
 		      /// The \e Altering \e Candidate \e List pivot rule.
 		      /// It is a modified version of the Candidate List method.
 		      /// It keeps only the several best eligible arcs from the former
 		      /// candidate list and extends this list in every iteration.
 		      ALTERING_LIST
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<char> CharVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    // State constants for arcs
 		    enum ArcStateEnum {
 		      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;
 		    int first, second, right, last;
 		    int stem, par_stem, new_stem;
 		    Value delta;
 		    const Value MAX;
 		  public:
 		    /// \brief Constant for infinite upper bounds (capacities).
 		    ///
 		    /// Constant for infinite upper bounds (capacities).
 		    /// It is \c std::numeric_limits<Value>::infinity() if available,
 		    /// \c std::numeric_limits<Value>::max() otherwise.
 		    const Value INF;
 		  private:
 		    // Implementation of the First Eligible pivot rule
 		    class FirstEligiblePivotRule
+		    {
 		    private:
 		      // References to the NetworkSimplex class
 		      const IntVector  &_source;
@@ -588,158 +589,108 @@
 		            limit = 0;
 		            cnt = _block_size;
+		          }
+		        }
 		        for (e = 0; e < _next_arc; ++e) {
 		          _cand_cost[e] = _state[e] *
 		            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (_cand_cost[e] < 0) {
 		            _candidates[_curr_length++] = e;
+		          }
 		          if (--cnt == 0) {
 		            if (_curr_length > limit) goto search_end;
 		            limit = 0;
 		            cnt = _block_size;
+		          }
+		        }
 		        if (_curr_length == 0) return false;
 		      search_end:
 		        // Make heap of the candidate list (approximating a partial sort)
 		        make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
 		                   _sort_func );
 		        // 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) {
 		        _lower[_arc_id[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>
 		    NetworkSimplex& upperMap(const UpperMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _upper[_arc_id[a]] = map[a];
+		      }
 		      return *this;
+		    }
@@ -797,167 +748,248 @@
 		    /// \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>
 		    NetworkSimplex& 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;
+		    }
 		    /// \brief Set the type of the supply constraints.
 		    ///
 		    /// This function sets the type of the supply/demand constraints.
 		    /// If it is not used before calling \ref run(), the \ref GEQ supply
 		    /// type will be used.
 		    ///
 		    /// For more information, see \ref SupplyType.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    NetworkSimplex& supplyType(SupplyType supply_type) {
 		      _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.
 		    template <typename Number>
 		    Number totalCost() const {
 		      Number c = 0;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int i = _arc_id[a];
 		        c += Number(_flow[i]) * Number(_cost[i]);
+		      }
 		      return c;
+		    }
 		#ifndef DOXYGEN
 		    Cost totalCost() const {
 		      return totalCost<Cost>();
+		    }
 		#endif
 		    /// \brief Return the flow on the given arc.
 		    ///
 		    /// This function returns the flow on the given arc.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Value flow(const Arc& a) const {
 		      return _flow[_arc_id[a]];
+		    }

test/min_cost_flow_test.cc

Show inline comments

@@ -112,97 +112,97 @@
 		  "      cost\n"
 		  "1 2     -1\n";
 		// Test data
 		typedef ListDigraph Digraph;
 		DIGRAPH_TYPEDEFS(ListDigraph);
 		Digraph gr;
 		Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
 		Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
 		ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
 		Node v, w;
 		Digraph neg1_gr;
 		Digraph::ArcMap<int> neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr);
 		ConstMap<Arc, int> neg1_u1(std::numeric_limits<int>::max()), neg1_u2(5000);
 		Digraph::NodeMap<int> neg1_s(neg1_gr);
 		Digraph neg2_gr;
 		Digraph::ArcMap<int> neg2_c(neg2_gr);
 		ConstMap<Arc, int> neg2_l(0), neg2_u(1000);
 		Digraph::NodeMap<int> neg2_s(neg2_gr);
 		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;
 		    VAM lower;
 		    VAM upper;
 		    CAM cost;
 		    NM sup;
 		    Node n;
 		    Arc a;
 		    Value k;
 		    FlowMap fm;
 		    PotMap pm;
 		    bool b;
 		    double x;
 		    typename MCF::Value v;
 		    typename MCF::Cost c;
 		  };
 		};
 		// Check the feasibility of the given flow (primal soluiton)
 		template < typename GR, typename LM, typename UM,
 		           typename SM, typename FM >
 		bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
 		                const SM& supply, const FM& flow,
@@ -301,131 +301,131 @@
 		// Run a minimum cost flow algorithm and check the results
 		template < typename MCF, typename GR,
 		           typename LM, typename UM,
 		           typename CM, typename SM,
 		           typename PT >
 		void checkMcf( const MCF& mcf, PT mcf_result,
 		               const GR& gr, const LM& lower, const UM& upper,
 		               const CM& cost, const SM& supply,
 		               PT result, bool optimal, typename CM::Value total,
 		               const std::string &test_id = "",
 		               SupplyType type = EQ )
+		{
 		  check(mcf_result == result, "Wrong result " + test_id);
 		  if (optimal) {
 		    typename GR::template ArcMap<typename SM::Value> flow(gr);
 		    typename GR::template NodeMap<typename CM::Value> pi(gr);
 		    mcf.flowMap(flow);
 		    mcf.potentialMap(pi);
 		    check(checkFlow(gr, lower, upper, supply, flow, type),
 		          "The flow is not feasible " + test_id);
 		    check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
 		    check(checkPotential(gr, lower, upper, cost, supply, flow, pi, type),
 		          "Wrong potentials " + test_id);
 		    check(checkDualCost(gr, lower, upper, cost, supply, pi, total),
 		          "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);
 		  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s6,
 		           mcf1.OPTIMAL, true,   5080, test_str + "-19", LEQ);
 		  mcf1.lowerMap(l2);
 		  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,
 		           mcf1.OPTIMAL, true,   5930, test_str + "-20", LEQ);
 		  mcf1.supplyMap(s5);
 		  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,
 		           mcf1.INFEASIBLE, false,  0, test_str + "-21", LEQ);
+		}
 		int main()
+		{
 		  // Read the test networks
 		  std::istringstream input(test_lgf);
 		  DigraphReader<Digraph>(gr, input)
 		    .arcMap("cost", c)
 		    .arcMap("cap", u)
 		    .arcMap("low1", l1)
 		    .arcMap("low2", l2)
 		    .arcMap("low3", l3)
 		    .nodeMap("sup1", s1)
 		    .nodeMap("sup2", s2)
 		    .nodeMap("sup3", s3)

0 comments (0 inline)

RhodeCode

Login to your account