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

@@ -221,464 +221,493 @@
 		      int run(int s, Value delta = 1) {
 		        RangeMap<int> heap_cross_ref(_node_num, Heap::PRE_HEAP);
 		        Heap heap(heap_cross_ref);
 		        heap.push(s, 0);
 		        _pred[s] = -1;
 		        _proc_nodes.clear();
 		        // Process nodes
 		        while (!heap.empty() && _excess[heap.top()] > -delta) {
 		          int u = heap.top(), v;
 		          Cost d = heap.prio() + _pi[u], dn;
 		          _dist[u] = heap.prio();
 		          _proc_nodes.push_back(u);
 		          heap.pop();
 		          // Traverse outgoing residual arcs
 		          int last_out = _geq ? _first_out[u+1] : _first_out[u+1] - 1;
 		          for (int a = _first_out[u]; a != last_out; ++a) {
 		            if (_res_cap[a] < delta) continue;
 		            v = _target[a];
 		            switch (heap.state(v)) {
 		              case Heap::PRE_HEAP:
 		                heap.push(v, d + _cost[a] - _pi[v]);
 		                _pred[v] = a;
 		                break;
 		              case Heap::IN_HEAP:
 		                dn = d + _cost[a] - _pi[v];
 		                if (dn < heap[v]) {
 		                  heap.decrease(v, dn);
 		                  _pred[v] = a;
+		                }
 		                break;
 		              case Heap::POST_HEAP:
 		                break;
+		            }
+		          }
+		        }
 		        if (heap.empty()) return -1;
 		        // Update potentials of processed nodes
 		        int t = heap.top();
 		        Cost dt = heap.prio();
 		        for (int i = 0; i < int(_proc_nodes.size()); ++i) {
 		          _pi[_proc_nodes[i]] += _dist[_proc_nodes[i]] - dt;
+		        }
 		        return t;
+		      }
 		    }; //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;
+		    }
 		    /// \brief Set the costs of the arcs.
 		    ///
 		    /// This function sets the costs of the arcs.
 		    /// If it is not used before calling \ref run(), the costs
 		    /// will be set to \c 1 on all arcs.
 		    ///
 		    /// \param map An arc map storing the costs.
 		    /// Its \c Value type must be convertible to the \c Cost type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename CostMap>
 		    CapacityScaling& costMap(const CostMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _cost[_arc_idf[a]] =  map[a];
 		        _cost[_arc_idb[a]] = -map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the supply values of the nodes.
 		    ///
 		    /// This function sets the supply values of the nodes.
 		    /// If neither this function nor \ref stSupply() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// \param map A node map storing the supply values.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename SupplyMap>
 		    CapacityScaling& supplyMap(const SupplyMap& map) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _supply[_node_id[n]] = map[n];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set single source and target nodes and a supply value.
 		    ///
 		    /// This function sets a single source node and a single target node
 		    /// and the required flow value.
 		    /// If neither this function nor \ref supplyMap() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
 		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k The required amount of flow from node \c s to node \c t
 		    /// (i.e. the supply of \c s and the demand of \c t).
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
 		      for (int i = 0; i != _node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      _supply[_node_id[s]] =  k;
 		      _supply[_node_id[t]] = -k;
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Execution control
 		    /// The algorithm can be executed using \ref run().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    /// The paramters can be specified using functions \ref lowerMap(),
 		    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
 		    /// For example,
 		    /// \code
 		    ///   CapacityScaling<ListDigraph> cs(graph);
 		    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// This function can be called more than once. All the parameters
 		    /// that have been given are kept for the next call, unless
 		    /// \ref reset() is called, thus only the modified parameters
 		    /// have to be set again. See \ref reset() for examples.
 		    /// However, the underlying digraph must not be modified after this
 		    /// class have been constructed, since it copies and extends the graph.
 		    /// 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]];
+		    }
 		    /// \brief Return the flow map (the primal solution).
 		    ///
 		    /// This function copies the flow value on each arc into the given
 		    /// map. The \c Value type of the algorithm must be convertible to
 		    /// the \c Value type of the map.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename FlowMap>
 		    void flowMap(FlowMap &map) const {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        map.set(a, _res_cap[_arc_idb[a]]);
+		      }
+		    }
 		    /// \brief Return the potential (dual value) of the given node.
 		    ///
 		    /// This function returns the potential (dual value) of the
 		    /// given node.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Cost potential(const Node& n) const {
 		      return _pi[_node_id[n]];
+		    }
 		    /// \brief Return the potential map (the dual solution).
 		    ///
 		    /// This function copies the potential (dual value) of each node
 		    /// into the given map.
 		    /// The \c Cost type of the algorithm must be convertible to the
 		    /// \c Value type of the map.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename PotentialMap>
 		    void potentialMap(PotentialMap &map) const {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        map.set(n, _pi[_node_id[n]]);
+		      }
+		    }
 		    /// @}
 		  private:
 		    // Initialize the algorithm
 		    ProblemType init() {
 		      if (_node_num <= 1) return INFEASIBLE;

lemon/cost_scaling.h

Show inline comments

@@ -240,476 +240,498 @@
 		    int _res_node_num;
 		    int _res_arc_num;
 		    int _root;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    Value _sum_supply;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    IntArcMap _arc_idf;
 		    IntArcMap _arc_idb;
 		    IntVector _first_out;
 		    BoolVector _forward;
 		    IntVector _source;
 		    IntVector _target;
 		    IntVector _reverse;
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    CostVector _scost;
 		    ValueVector _supply;
 		    ValueVector _res_cap;
 		    LargeCostVector _cost;
 		    LargeCostVector _pi;
 		    ValueVector _excess;
 		    IntVector _next_out;
 		    std::deque<int> _active_nodes;
 		    // Data for scaling
 		    LargeCost _epsilon;
 		    int _alpha;
 		    // Data for a StaticDigraph structure
 		    typedef std::pair<int, int> IntPair;
 		    StaticDigraph _sgr;
 		    std::vector<IntPair> _arc_vec;
 		    std::vector<LargeCost> _cost_vec;
 		    LargeCostArcMap _cost_map;
 		    LargeCostNodeMap _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:
 		    /// \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;
+		    }
 		    /// \brief Set the costs of the arcs.
 		    ///
 		    /// This function sets the costs of the arcs.
 		    /// If it is not used before calling \ref run(), the costs
 		    /// will be set to \c 1 on all arcs.
 		    ///
 		    /// \param map An arc map storing the costs.
 		    /// Its \c Value type must be convertible to the \c Cost type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename CostMap>
 		    CostScaling& costMap(const CostMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _scost[_arc_idf[a]] =  map[a];
 		        _scost[_arc_idb[a]] = -map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the supply values of the nodes.
 		    ///
 		    /// This function sets the supply values of the nodes.
 		    /// If neither this function nor \ref stSupply() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// \param map A node map storing the supply values.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename SupplyMap>
 		    CostScaling& supplyMap(const SupplyMap& map) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _supply[_node_id[n]] = map[n];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set single source and target nodes and a supply value.
 		    ///
 		    /// This function sets a single source node and a single target node
 		    /// and the required flow value.
 		    /// If neither this function nor \ref supplyMap() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
 		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k The required amount of flow from node \c s to node \c t
 		    /// (i.e. the supply of \c s and the demand of \c t).
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    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]];
+		    }
 		    /// \brief Return the flow map (the primal solution).
 		    ///
 		    /// This function copies the flow value on each arc into the given
 		    /// map. The \c Value type of the algorithm must be convertible to
 		    /// the \c Value type of the map.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename FlowMap>
 		    void flowMap(FlowMap &map) const {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        map.set(a, _res_cap[_arc_idb[a]]);
+		      }
+		    }
 		    /// \brief Return the potential (dual value) of the given node.
 		    ///
 		    /// This function returns the potential (dual value) of the
 		    /// given node.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Cost potential(const Node& n) const {
 		      return static_cast<Cost>(_pi[_node_id[n]]);
+		    }
 		    /// \brief Return the potential map (the dual solution).
 		    ///
 		    /// This function copies the potential (dual value) of each node
 		    /// into the given map.
 		    /// The \c Cost type of the algorithm must be convertible to the
 		    /// \c Value type of the map.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename PotentialMap>
 		    void potentialMap(PotentialMap &map) const {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        map.set(n, static_cast<Cost>(_pi[_node_id[n]]));
+		      }
+		    }
 		    /// @}
 		  private:
 		    // Initialize the algorithm
 		    ProblemType init() {
 		      if (_res_node_num <= 1) return INFEASIBLE;

lemon/cycle_canceling.h

Show inline comments

@@ -157,472 +157,501 @@
 		      typedef KT Key;
 		      typedef VT Value;
 		      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
 		      const Value& operator[](const Key& key) const {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      Value& operator[](const Key& key) {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      void set(const Key& key, const Value& val) {
 		        _v[StaticDigraph::id(key)] = val;
+		      }
 		    private:
 		      std::vector<Value>& _v;
 		    };
 		    typedef StaticVectorMap<StaticDigraph::Node, Cost> CostNodeMap;
 		    typedef StaticVectorMap<StaticDigraph::Arc, Cost> CostArcMap;
 		  private:
 		    // Data related to the underlying digraph
 		    const GR &_graph;
 		    int _node_num;
 		    int _arc_num;
 		    int _res_node_num;
 		    int _res_arc_num;
 		    int _root;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    Value _sum_supply;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    IntArcMap _arc_idf;
 		    IntArcMap _arc_idb;
 		    IntVector _first_out;
 		    CharVector _forward;
 		    IntVector _source;
 		    IntVector _target;
 		    IntVector _reverse;
 		    // 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;
+		    }
 		    /// \brief Set the costs of the arcs.
 		    ///
 		    /// This function sets the costs of the arcs.
 		    /// If it is not used before calling \ref run(), the costs
 		    /// will be set to \c 1 on all arcs.
 		    ///
 		    /// \param map An arc map storing the costs.
 		    /// Its \c Value type must be convertible to the \c Cost type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename CostMap>
 		    CycleCanceling& costMap(const CostMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _cost[_arc_idf[a]] =  map[a];
 		        _cost[_arc_idb[a]] = -map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the supply values of the nodes.
 		    ///
 		    /// This function sets the supply values of the nodes.
 		    /// If neither this function nor \ref stSupply() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// \param map A node map storing the supply values.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename SupplyMap>
 		    CycleCanceling& supplyMap(const SupplyMap& map) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _supply[_node_id[n]] = map[n];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set single source and target nodes and a supply value.
 		    ///
 		    /// This function sets a single source node and a single target node
 		    /// and the required flow value.
 		    /// If neither this function nor \ref supplyMap() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
 		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k The required amount of flow from node \c s to node \c t
 		    /// (i.e. the supply of \c s and the demand of \c t).
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    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]];
+		    }
 		    /// \brief Return the flow map (the primal solution).
 		    ///
 		    /// This function copies the flow value on each arc into the given
 		    /// map. The \c Value type of the algorithm must be convertible to
 		    /// the \c Value type of the map.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename FlowMap>
 		    void flowMap(FlowMap &map) const {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        map.set(a, _res_cap[_arc_idb[a]]);
+		      }
+		    }
 		    /// \brief Return the potential (dual value) of the given node.
 		    ///
 		    /// This function returns the potential (dual value) of the
 		    /// given node.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Cost potential(const Node& n) const {
 		      return static_cast<Cost>(_pi[_node_id[n]]);
+		    }
 		    /// \brief Return the potential map (the dual solution).
 		    ///
 		    /// This function copies the potential (dual value) of each node
 		    /// into the given map.
 		    /// The \c Cost type of the algorithm must be convertible to the
 		    /// \c Value type of the map.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename PotentialMap>
 		    void potentialMap(PotentialMap &map) const {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        map.set(n, static_cast<Cost>(_pi[_node_id[n]]));
+		      }
+		    }
 		    /// @}
 		  private:
 		    // Initialize the algorithm
 		    ProblemType init() {
 		      if (_res_node_num <= 1) return INFEASIBLE;

lemon/network_simplex.h

Show inline comments

@@ -101,192 +101,193 @@
 		    /// \brief Constants for selecting the type of the supply constraints.
 		    ///
 		    /// Enum type containing constants for selecting the supply type,
 		    /// i.e. the direction of the inequalities in the supply/demand
 		    /// constraints of the \ref min_cost_flow "minimum cost flow problem".
 		    ///
 		    /// The default supply type is \c GEQ, the \c LEQ type can be
 		    /// selected using \ref supplyType().
 		    /// The equality form is a special case of both supply types.
 		    enum SupplyType {
 		      /// This option means that there are <em>"greater or equal"</em>
 		      /// supply/demand constraints in the definition of the problem.
 		      GEQ,
 		      /// This option means that there are <em>"less or equal"</em>
 		      /// supply/demand constraints in the definition of the problem.
 		      LEQ
 		    };
 		    /// \brief Constants for selecting the pivot rule.
 		    ///
 		    /// Enum type containing constants for selecting the pivot rule for
 		    /// the \ref run() function.
 		    ///
 		    /// \ref NetworkSimplex provides five different pivot rule
 		    /// implementations that significantly affect the running time
 		    /// of the algorithm.
 		    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
 		    /// proved to be the most efficient and the most robust on various
 		    /// test inputs.
 		    /// However, another pivot rule can be selected using the \ref run()
 		    /// function with the proper parameter.
 		    enum PivotRule {
 		      /// The \e First \e Eligible pivot rule.
 		      /// The next eligible arc is selected in a wraparound fashion
 		      /// in every iteration.
 		      FIRST_ELIGIBLE,
 		      /// The \e Best \e Eligible pivot rule.
 		      /// The best eligible arc is selected in every iteration.
 		      BEST_ELIGIBLE,
 		      /// The \e Block \e Search pivot rule.
 		      /// A specified number of arcs are examined in every iteration
 		      /// in a wraparound fashion and the best eligible arc is selected
 		      /// from this block.
 		      BLOCK_SEARCH,
 		      /// 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;
 		      const IntVector  &_target;
 		      const CostVector &_cost;
 		      const CharVector &_state;
 		      const CostVector &_pi;
 		      int &_in_arc;
 		      int _search_arc_num;
 		      // Pivot rule data
 		      int _next_arc;
 		    public:
 		      // Constructor
 		      FirstEligiblePivotRule(NetworkSimplex &ns) :
 		        _source(ns._source), _target(ns._target),
 		        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
 		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
 		        _next_arc(0)
 		      {}
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        Cost c;
 		        for (int e = _next_arc; e < _search_arc_num; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < 0) {
 		            _in_arc = e;
 		            _next_arc = e + 1;
 		            return true;
+		          }
+		        }
 		        for (int e = 0; e < _next_arc; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < 0) {
 		            _in_arc = e;
 		            _next_arc = e + 1;
 		            return true;
+		          }
+		        }
 		        return false;
+		      }
 		    }; //class FirstEligiblePivotRule
 		    // Implementation of the Best Eligible pivot rule
 		    class BestEligiblePivotRule
+		    {
@@ -540,472 +541,503 @@
 		      // Constructor
 		      AlteringListPivotRule(NetworkSimplex &ns) :
 		        _source(ns._source), _target(ns._target),
 		        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
 		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
 		        _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost)
+		      {
 		        // The main parameters of the pivot rule
 		        const double BLOCK_SIZE_FACTOR = 1.0;
 		        const int MIN_BLOCK_SIZE = 10;
 		        const double HEAD_LENGTH_FACTOR = 0.1;
 		        const int MIN_HEAD_LENGTH = 3;
 		        _block_size = std::max( int(BLOCK_SIZE_FACTOR *
 		                                    std::sqrt(double(_search_arc_num))),
 		                                MIN_BLOCK_SIZE );
 		        _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size),
 		                                 MIN_HEAD_LENGTH );
 		        _candidates.resize(_head_length + _block_size);
 		        _curr_length = 0;
+		      }
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        // Check the current candidate list
 		        int e;
 		        for (int i = 0; i < _curr_length; ++i) {
 		          e = _candidates[i];
 		          _cand_cost[e] = _state[e] *
 		            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (_cand_cost[e] >= 0) {
 		            _candidates[i--] = _candidates[--_curr_length];
+		          }
+		        }
 		        // Extend the list
 		        int cnt = _block_size;
 		        int limit = _head_length;
 		        for (e = _next_arc; e < _search_arc_num; ++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;
+		          }
+		        }
 		        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;
+		    }
 		    /// \brief Set the costs of the arcs.
 		    ///
 		    /// This function sets the costs of the arcs.
 		    /// If it is not used before calling \ref run(), the costs
 		    /// will be set to \c 1 on all arcs.
 		    ///
 		    /// \param map An arc map storing the costs.
 		    /// Its \c Value type must be convertible to the \c Cost type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename CostMap>
 		    NetworkSimplex& costMap(const CostMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _cost[_arc_id[a]] = map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the supply values of the nodes.
 		    ///
 		    /// This function sets the supply values of the nodes.
 		    /// If neither this function nor \ref stSupply() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// \param map A node map storing the supply values.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename SupplyMap>
 		    NetworkSimplex& supplyMap(const SupplyMap& map) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _supply[_node_id[n]] = map[n];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set single source and target nodes and a supply value.
 		    ///
 		    /// This function sets a single source node and a single target node
 		    /// and the required flow value.
 		    /// If neither this function nor \ref supplyMap() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
 		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k The required amount of flow from node \c s to node \c t
 		    /// (i.e. the supply of \c s and the demand of \c t).
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    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]];
+		    }
 		    /// \brief Return the flow map (the primal solution).
 		    ///
 		    /// This function copies the flow value on each arc into the given
 		    /// map. The \c Value type of the algorithm must be convertible to
 		    /// the \c Value type of the map.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename FlowMap>
 		    void flowMap(FlowMap &map) const {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        map.set(a, _flow[_arc_id[a]]);
+		      }
+		    }
 		    /// \brief Return the potential (dual value) of the given node.
 		    ///
 		    /// This function returns the potential (dual value) of the
 		    /// given node.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Cost potential(const Node& n) const {
 		      return _pi[_node_id[n]];
+		    }
 		    /// \brief Return the potential map (the dual solution).
 		    ///
 		    /// This function copies the potential (dual value) of each node
 		    /// into the given map.
 		    /// The \c Cost type of the algorithm must be convertible to the
 		    /// \c Value type of the map.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename PotentialMap>
 		    void potentialMap(PotentialMap &map) const {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        map.set(n, _pi[_node_id[n]]);
+		      }
+		    }
 		    /// @}
 		  private:
 		    // Initialize internal data structures
 		    bool init() {
 		      if (_node_num == 0) return false;

test/min_cost_flow_test.cc

Show inline comments

@@ -64,416 +64,416 @@
 		  " 4  7    80    2    0    0    0\n"
 		  " 4  8   110    3    0    0    0\n"
 		  " 5  7    60   14    0    0    0\n"
 		  " 5 11   120   12    0    0    0\n"
 		  " 6  3     0    3    0    0    0\n"
 		  " 6  9   140    4    0    0    0\n"
 		  " 6 10    90    8    0    0    0\n"
 		  " 7  1    30    5    0    0   -5\n"
 		  " 8 12    60   16    0    4    3\n"
 		  " 9 12    50    6    0    0    0\n"
 		  "10 12    70   13    0    5    2\n"
 		  "10  2   100    7    0    0    0\n"
 		  "10  7    60   10    0    0   -3\n"
 		  "11 10    20   14    0    6  -20\n"
 		  "12 11    30   10    0    0  -10\n"
 		  "\n"
 		  "@attributes\n"
 		  "source 1\n"
 		  "target 12\n";
 		char test_neg1_lgf[] =
 		  "@nodes\n"
 		  "label   sup\n"
 		  "    1   100\n"
 		  "    2     0\n"
 		  "    3     0\n"
 		  "    4  -100\n"
 		  "    5     0\n"
 		  "    6     0\n"
 		  "    7     0\n"
 		  "@arcs\n"
 		  "      cost   low1   low2\n"
 		  "1 2    100      0      0\n"
 		  "1 3     30      0      0\n"
 		  "2 4     20      0      0\n"
 		  "3 4     80      0      0\n"
 		  "3 2     50      0      0\n"
 		  "5 3     10      0      0\n"
 		  "5 6     80      0   1000\n"
 		  "6 7     30      0  -1000\n"
 		  "7 5   -120      0      0\n";
 		char test_neg2_lgf[] =
 		  "@nodes\n"
 		  "label   sup\n"
 		  "    1   100\n"
 		  "    2  -300\n"
 		  "@arcs\n"
 		  "      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,
 		                SupplyType type = EQ )
+		{
 		  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		  for (ArcIt e(gr); e != INVALID; ++e) {
 		    if (flow[e] < lower[e] || flow[e] > upper[e]) return false;
+		  }
 		  for (NodeIt n(gr); n != INVALID; ++n) {
 		    typename SM::Value sum = 0;
 		    for (OutArcIt e(gr, n); e != INVALID; ++e)
 		      sum += flow[e];
 		    for (InArcIt e(gr, n); e != INVALID; ++e)
 		      sum -= flow[e];
 		    bool b = (type ==  EQ && sum == supply[n]) ||
 		             (type == GEQ && sum >= supply[n]) ||
 		             (type == LEQ && sum <= supply[n]);
 		    if (!b) return false;
+		  }
 		  return true;
+		}
 		// Check the feasibility of the given potentials (dual soluiton)
 		// using the "Complementary Slackness" optimality condition
 		template < typename GR, typename LM, typename UM,
 		           typename CM, typename SM, typename FM, typename PM >
 		bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
 		                     const CM& cost, const SM& supply, const FM& flow,
 		                     const PM& pi, SupplyType type )
+		{
 		  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		  bool opt = true;
 		  for (ArcIt e(gr); opt && e != INVALID; ++e) {
 		    typename CM::Value red_cost =
 		      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
 		    opt = red_cost == 0 ||
 		          (red_cost > 0 && flow[e] == lower[e]) ||
 		          (red_cost < 0 && flow[e] == upper[e]);
+		  }
 		  for (NodeIt n(gr); opt && n != INVALID; ++n) {
 		    typename SM::Value sum = 0;
 		    for (OutArcIt e(gr, n); e != INVALID; ++e)
 		      sum += flow[e];
 		    for (InArcIt e(gr, n); e != INVALID; ++e)
 		      sum -= flow[e];
 		    if (type != LEQ) {
 		      opt = (pi[n] <= 0) && (sum == supply[n] || pi[n] == 0);
 		    } else {
 		      opt = (pi[n] >= 0) && (sum == supply[n] || pi[n] == 0);
+		    }
+		  }
 		  return opt;
+		}
 		// Check whether the dual cost is equal to the primal cost
 		template < typename GR, typename LM, typename UM,
 		           typename CM, typename SM, typename PM >
 		bool checkDualCost( const GR& gr, const LM& lower, const UM& upper,
 		                    const CM& cost, const SM& supply, const PM& pi,
 		                    typename CM::Value total )
+		{
 		  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		  typename CM::Value dual_cost = 0;
 		  SM red_supply(gr);
 		  for (NodeIt n(gr); n != INVALID; ++n) {
 		    red_supply[n] = supply[n];
+		  }
 		  for (ArcIt a(gr); a != INVALID; ++a) {
 		    if (lower[a] != 0) {
 		      dual_cost += lower[a] * cost[a];
 		      red_supply[gr.source(a)] -= lower[a];
 		      red_supply[gr.target(a)] += lower[a];
+		    }
+		  }
 		  for (NodeIt n(gr); n != INVALID; ++n) {
 		    dual_cost -= red_supply[n] * pi[n];
+		  }
 		  for (ArcIt a(gr); a != INVALID; ++a) {
 		    typename CM::Value red_cost =
 		      cost[a] + pi[gr.source(a)] - pi[gr.target(a)];
 		    dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0);
+		  }
 		  return dual_cost == total;
+		}
 		// 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)
 		    .nodeMap("sup4", s4)
 		    .nodeMap("sup5", s5)
 		    .nodeMap("sup6", s6)
 		    .node("source", v)
 		    .node("target", w)
 		    .run();
 		  std::istringstream neg_inp1(test_neg1_lgf);
 		  DigraphReader<Digraph>(neg1_gr, neg_inp1)
 		    .arcMap("cost", neg1_c)
 		    .arcMap("low1", neg1_l1)
 		    .arcMap("low2", neg1_l2)
 		    .nodeMap("sup", neg1_s)
 		    .run();
 		  std::istringstream neg_inp2(test_neg2_lgf);
 		  DigraphReader<Digraph>(neg2_gr, neg_inp2)
 		    .arcMap("cost", neg2_c)
 		    .nodeMap("sup", neg2_s)
 		    .run();
 		  // Check the interface of NetworkSimplex
+		  {
 		    typedef concepts::Digraph GR;
 		    checkConcept< McfClassConcept<GR, int, int>,
 		                  NetworkSimplex<GR> >();
 		    checkConcept< McfClassConcept<GR, double, double>,
 		                  NetworkSimplex<GR, double> >();
 		    checkConcept< McfClassConcept<GR, int, double>,
 		                  NetworkSimplex<GR, int, double> >();
+		  }
 		  // Check the interface of CapacityScaling
+		  {
 		    typedef concepts::Digraph GR;
 		    checkConcept< McfClassConcept<GR, int, int>,
 		                  CapacityScaling<GR> >();
 		    checkConcept< McfClassConcept<GR, double, double>,
 		                  CapacityScaling<GR, double> >();
 		    checkConcept< McfClassConcept<GR, int, double>,
 		                  CapacityScaling<GR, int, double> >();
 		    typedef CapacityScaling<GR>::
 		      SetHeap<concepts::Heap<int, RangeMap<int> > >::Create CAS;
 		    checkConcept< McfClassConcept<GR, int, int>, CAS >();
+		  }
 		  // Check the interface of CostScaling
+		  {

0 comments (0 inline)

RhodeCode

Login to your account