LEMON/LEMON-official Changeset - r654:9ad8d2122b50

Repositories » LEMON » LEMON-official

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

Changeset - r654:9ad8d2122b50

« 653:c7d160

655:6ac5d9 »

r654:9ad8d2122b50

Fri, 03 Apr 2009 13:46:16

[Not Reviewed]

0 comments (0 inline)

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

Separate types for flow and cost values in NetworkSimplex (#234)

0 2 0

default

2 files changed with 90 insertions and 80 deletions:

lemon/network_simplex.h

test/min_cost_flow_test.cc

↑ Collapse diff ↑

lemon/network_simplex.h

Show inline comments

@@ -51,6 +51,8 @@
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam V The value type used in the algorithm.
 		  /// By default it is \c int.
 		  /// \tparam F The value type used for flow amounts, capacity bounds
 		  /// and supply values in the algorithm. By default it is \c int.
 		  /// \tparam C The value type used for costs and potentials in the
 		  /// algorithm. By default it is the same as \c F.
 		  ///
-		  /// \warning The value type must be a signed integer type.
+		  /// \warning Both value types must be signed integer types.
 		  ///
@@ -58,3 +60,3 @@
 		  /// implementations. For more information see \ref PivotRule.
-		  template <typename GR, typename V = int>
+		  template <typename GR, typename F = int, typename C = F>
 		  class NetworkSimplex
@@ -63,8 +65,10 @@
 		    /// The value type of the algorithm
 		    typedef V Value;
 		    /// The flow type of the algorithm
 		    typedef F Flow;
 		    /// The cost type of the algorithm
 		    typedef C Cost;
 		    /// The type of the flow map
-		    typedef typename GR::template ArcMap<Value> FlowMap;
+		    typedef typename GR::template ArcMap<Flow> FlowMap;
 		    /// The type of the potential map
-		    typedef typename GR::template NodeMap<Value> PotentialMap;
+		    typedef typename GR::template NodeMap<Cost> PotentialMap;
@@ -119,4 +123,5 @@
 		    typedef typename GR::template ArcMap<Value> ValueArcMap;
 		    typedef typename GR::template NodeMap<Value> ValueNodeMap;
 		    typedef typename GR::template ArcMap<Flow> FlowArcMap;
 		    typedef typename GR::template ArcMap<Cost> CostArcMap;
 		    typedef typename GR::template NodeMap<Flow> FlowNodeMap;
@@ -126,3 +131,4 @@
 		    typedef std::vector<bool> BoolVector;
-		    typedef std::vector<Value> ValueVector;
+		    typedef std::vector<Flow> FlowVector;
 		    typedef std::vector<Cost> CostVector;
@@ -143,9 +149,9 @@
 		    // Parameters of the problem
 		    ValueArcMap *_plower;
 		    ValueArcMap *_pupper;
 		    ValueArcMap *_pcost;
 		    ValueNodeMap *_psupply;
 		    FlowArcMap *_plower;
 		    FlowArcMap *_pupper;
 		    CostArcMap *_pcost;
 		    FlowNodeMap *_psupply;
 		    bool _pstsup;
 		    Node _psource, _ptarget;
-		    Value _pstflow;
+		    Flow _pstflow;
@@ -164,7 +170,7 @@
 		    // Node and arc data
 		    ValueVector _cap;
 		    ValueVector _cost;
 		    ValueVector _supply;
 		    ValueVector _flow;
-		    ValueVector _pi;
+		    FlowVector _cap;
 		    CostVector _cost;
 		    FlowVector _supply;
 		    FlowVector _flow;
 		    CostVector _pi;
@@ -186,3 +192,3 @@
 		    int stem, par_stem, new_stem;
-		    Value delta;
+		    Flow delta;
@@ -198,5 +204,5 @@
 		      const IntVector  &_target;
-		      const ValueVector &_cost;
+		      const CostVector &_cost;
 		      const IntVector  &_state;
-		      const ValueVector &_pi;
+		      const CostVector &_pi;
 		      int &_in_arc;
@@ -218,3 +224,3 @@
 		      bool findEnteringArc() {
-		        Value c;
+		        Cost c;
 		        for (int e = _next_arc; e < _arc_num; ++e) {
@@ -249,5 +255,5 @@
 		      const IntVector  &_target;
-		      const ValueVector &_cost;
+		      const CostVector &_cost;
 		      const IntVector  &_state;
-		      const ValueVector &_pi;
+		      const CostVector &_pi;
 		      int &_in_arc;
@@ -266,3 +272,3 @@
 		      bool findEnteringArc() {
-		        Value c, min = 0;
+		        Cost c, min = 0;
 		        for (int e = 0; e < _arc_num; ++e) {
@@ -288,5 +294,5 @@
 		      const IntVector  &_target;
-		      const ValueVector &_cost;
+		      const CostVector &_cost;
 		      const IntVector  &_state;
-		      const ValueVector &_pi;
+		      const CostVector &_pi;
 		      int &_in_arc;
@@ -316,3 +322,3 @@
 		      bool findEnteringArc() {
-		        Value c, min = 0;
+		        Cost c, min = 0;
 		        int cnt = _block_size;
@@ -360,5 +366,5 @@
 		      const IntVector  &_target;
-		      const ValueVector &_cost;
+		      const CostVector &_cost;
 		      const IntVector  &_state;
-		      const ValueVector &_pi;
+		      const CostVector &_pi;
 		      int &_in_arc;
@@ -396,3 +402,3 @@
 		      bool findEnteringArc() {
-		        Value min, c;
+		        Cost min, c;
 		        int e, min_arc = _next_arc;
@@ -465,5 +471,5 @@
 		      const IntVector  &_target;
-		      const ValueVector &_cost;
+		      const CostVector &_cost;
 		      const IntVector  &_state;
-		      const ValueVector &_pi;
+		      const CostVector &_pi;
 		      int &_in_arc;
@@ -475,3 +481,3 @@
 		      IntVector _candidates;
-		      ValueVector _cand_cost;
+		      CostVector _cand_cost;
@@ -481,5 +487,5 @@
 		      private:
-		        const ValueVector &_map;
+		        const CostVector &_map;
 		      public:
-		        SortFunc(const ValueVector &map) : _map(map) {}
+		        SortFunc(const CostVector &map) : _map(map) {}
 		        bool operator()(int left, int right) {
@@ -592,5 +598,8 @@
+		    {
 		      LEMON_ASSERT(std::numeric_limits<Value>::is_integer &&
 		                   std::numeric_limits<Value>::is_signed,
-		        "The value type of NetworkSimplex must be a signed integer");
+		      LEMON_ASSERT(std::numeric_limits<Flow>::is_integer &&
 		                   std::numeric_limits<Flow>::is_signed,
 		        "The flow type of NetworkSimplex must be signed integer");
 		      LEMON_ASSERT(std::numeric_limits<Cost>::is_integer &&
 		                   std::numeric_limits<Cost>::is_signed,
 		        "The cost type of NetworkSimplex must be signed integer");
+		    }
@@ -611,3 +620,3 @@
 		    /// \param map An arc map storing the lower bounds.
-		    /// Its \c Value type must be convertible to the \c Value type
+		    /// Its \c Value type must be convertible to the \c Flow type
 		    /// of the algorithm.
@@ -618,3 +627,3 @@
 		      delete _plower;
-		      _plower = new ValueArcMap(_graph);
+		      _plower = new FlowArcMap(_graph);
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
@@ -631,6 +640,6 @@
 		    /// the upper bounds (capacities) will be set to
-		    /// \c std::numeric_limits<Value>::max() on all arcs.
+		    /// \c std::numeric_limits<Flow>::max() on all arcs.
 		    ///
 		    /// \param map An arc map storing the upper bounds.
-		    /// Its \c Value type must be convertible to the \c Value type
+		    /// Its \c Value type must be convertible to the \c Flow type
 		    /// of the algorithm.
@@ -641,3 +650,3 @@
 		      delete _pupper;
-		      _pupper = new ValueArcMap(_graph);
+		      _pupper = new FlowArcMap(_graph);
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
@@ -668,3 +677,3 @@
 		    /// the upper bounds (capacities) will be set to
-		    /// \c std::numeric_limits<Value>::max() on all arcs.
+		    /// \c std::numeric_limits<Flow>::max() on all arcs.
 		    ///
@@ -674,3 +683,3 @@
 		    /// The \c Value type of the maps must be convertible to the
-		    /// \c Value type of the algorithm.
+		    /// \c Flow type of the algorithm.
 		    ///
@@ -692,3 +701,3 @@
 		    /// \param map An arc map storing the costs.
-		    /// Its \c Value type must be convertible to the \c Value type
+		    /// Its \c Value type must be convertible to the \c Cost type
 		    /// of the algorithm.
@@ -699,3 +708,3 @@
 		      delete _pcost;
-		      _pcost = new ValueArcMap(_graph);
+		      _pcost = new CostArcMap(_graph);
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
@@ -714,3 +723,3 @@
 		    /// \param map A node map storing the supply values.
-		    /// Its \c Value type must be convertible to the \c Value type
+		    /// Its \c Value type must be convertible to the \c Flow type
 		    /// of the algorithm.
@@ -722,3 +731,3 @@
 		      _pstsup = false;
-		      _psupply = new ValueNodeMap(_graph);
+		      _psupply = new FlowNodeMap(_graph);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
@@ -743,3 +752,3 @@
 		    /// \return <tt>(*this)</tt>
-		    NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
+		    NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) {
 		      delete _psupply;
@@ -876,3 +885,3 @@
 		    /// This function returns the total cost of the found flow.
-		    /// The complexity of the function is \f$ O(e) \f$.
 		    /// The complexity of the function is O(e).
 		    ///
@@ -883,3 +892,3 @@
 		    /// \endcode
-		    /// It is useful if the total cost cannot be stored in the \c Value
+		    /// 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
@@ -902,4 +911,4 @@
 		#ifndef DOXYGEN
 		    Value totalCost() const {
 		      return totalCost<Value>();
 		    Cost totalCost() const {
 		      return totalCost<Cost>();
+		    }
@@ -912,3 +921,3 @@
 		    /// \pre \ref run() must be called before using this function.
-		    Value flow(const Arc& a) const {
+		    Flow flow(const Arc& a) const {
 		      return (*_flow_map)[a];
@@ -932,3 +941,3 @@
 		    /// \pre \ref run() must be called before using this function.
-		    Value potential(const Node& n) const {
+		    Cost potential(const Node& n) const {
 		      return (*_potential_map)[n];
@@ -998,3 +1007,3 @@
 		      if (_psupply) {
-		        Value sum = 0;
+		        Flow sum = 0;
 		        int i = 0;
@@ -1037,2 +1046,4 @@
 		      // Initialize arc maps
 		      Flow max_cap = std::numeric_limits<Flow>::max();
 		      Cost max_cost = std::numeric_limits<Cost>::max() / 4;
 		      if (_pupper && _pcost) {
@@ -1059,5 +1070,4 @@
 		        } else {
 		          Value val = std::numeric_limits<Value>::max();
 		          for (int i = 0; i != _arc_num; ++i)
-		            _cap[i] = val;
+		            _cap[i] = max_cap;
+		        }
@@ -1075,3 +1085,3 @@
 		        for (int i = 0; i != _arc_num; ++i) {
-		          Value c = (*_plower)[_arc_ref[i]];
+		          Flow c = (*_plower)[_arc_ref[i]];
 		          if (c != 0) {
@@ -1085,4 +1095,2 @@
 		      // Add artificial arcs and initialize the spanning tree data structure
 		      Value max_cap = std::numeric_limits<Value>::max();
 		      Value max_cost = std::numeric_limits<Value>::max() / 4;
 		      for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
@@ -1139,3 +1147,3 @@
 		      int result = 0;
-		      Value d;
+		      Flow d;
 		      int e;
@@ -1177,3 +1185,3 @@
 		      if (delta > 0) {
-		        Value val = _state[in_arc] * delta;
+		        Flow val = _state[in_arc] * delta;
 		        _flow[in_arc] += val;
@@ -1318,3 +1326,3 @@
 		    void updatePotential() {
-		      Value sigma = _forward[u_in] ?
+		      Cost sigma = _forward[u_in] ?
 		        _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :

test/min_cost_flow_test.cc

Show inline comments

@@ -79,3 +79,3 @@
 		// Check the interface of an MCF algorithm
-		template <typename GR, typename Value>
+		template <typename GR, typename Flow, typename Cost>
 		class McfClassConcept
@@ -118,9 +118,10 @@
 		    typedef typename GR::Arc Arc;
 		    typedef concepts::ReadMap<Node, Value> NM;
 		    typedef concepts::ReadMap<Arc, Value> AM;
 		    typedef concepts::ReadMap<Node, Flow> NM;
 		    typedef concepts::ReadMap<Arc, Flow> FAM;
 		    typedef concepts::ReadMap<Arc, Cost> CAM;
 		    const GR &g;
 		    const AM &lower;
 		    const AM &upper;
-		    const AM &cost;
+		    const FAM &lower;
 		    const FAM &upper;
 		    const CAM &cost;
 		    const NM &sup;
@@ -128,4 +129,4 @@
 		    const Arc &a;
 		    const Value &k;
 		    Value v;
 		    const Flow &k;
 		    Flow v;
 		    bool b;
@@ -208,3 +209,4 @@
+		  {
-		    typedef int Value;
+		    typedef int Flow;
 		    typedef int Cost;
 		    // TODO: This typedef should be enabled if the standard maps are
@@ -215,4 +217,4 @@
 		/**/
 		    checkConcept< McfClassConcept<GR, Value>,
 		                  NetworkSimplex<GR, Value> >();
 		    checkConcept< McfClassConcept<GR, Flow, Cost>,
 		                  NetworkSimplex<GR, Flow, Cost> >();
+		  }

0 comments (0 inline)

RhodeCode

Login to your account