Support multiple run() calls in NetworkSimplex (#234)
authorPeter Kovacs <kpeter@inf.elte.hu>
Wed, 25 Mar 2009 21:37:50 +0100
changeset 598c7d160f73d52
parent 597 5232721b3f14
child 599 9ad8d2122b50
Support multiple run() calls in NetworkSimplex (#234)
lemon/network_simplex.h
test/min_cost_flow_test.cc
     1.1 --- a/lemon/network_simplex.h	Wed Mar 25 15:58:44 2009 +0100
     1.2 +++ b/lemon/network_simplex.h	Wed Mar 25 21:37:50 2009 +0100
     1.3 @@ -41,12 +41,18 @@
     1.4    ///
     1.5    /// \ref NetworkSimplex implements the primal Network Simplex algorithm
     1.6    /// for finding a \ref min_cost_flow "minimum cost flow".
     1.7 +  /// This algorithm is a specialized version of the linear programming
     1.8 +  /// simplex method directly for the minimum cost flow problem.
     1.9 +  /// It is one of the most efficient solution methods.
    1.10 +  ///
    1.11 +  /// In general this class is the fastest implementation available
    1.12 +  /// in LEMON for the minimum cost flow problem.
    1.13    ///
    1.14    /// \tparam GR The digraph type the algorithm runs on.
    1.15    /// \tparam V The value type used in the algorithm.
    1.16    /// By default it is \c int.
    1.17    ///
    1.18 -  /// \warning \c V must be a signed integer type.
    1.19 +  /// \warning The value type must be a signed integer type.
    1.20    ///
    1.21    /// \note %NetworkSimplex provides five different pivot rule
    1.22    /// implementations. For more information see \ref PivotRule.
    1.23 @@ -789,7 +795,7 @@
    1.24      ///
    1.25      /// This function runs the algorithm.
    1.26      /// The paramters can be specified using \ref lowerMap(),
    1.27 -    /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(), 
    1.28 +    /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(),
    1.29      /// \ref costMap(), \ref supplyMap() and \ref stSupply()
    1.30      /// functions. For example,
    1.31      /// \code
    1.32 @@ -798,6 +804,11 @@
    1.33      ///     .supplyMap(sup).run();
    1.34      /// \endcode
    1.35      ///
    1.36 +    /// This function can be called more than once. All the parameters
    1.37 +    /// that have been given are kept for the next call, unless
    1.38 +    /// \ref reset() is called, thus only the modified parameters
    1.39 +    /// have to be set again. See \ref reset() for examples.
    1.40 +    ///
    1.41      /// \param pivot_rule The pivot rule that will be used during the
    1.42      /// algorithm. For more information see \ref PivotRule.
    1.43      ///
    1.44 @@ -806,6 +817,51 @@
    1.45        return init() && start(pivot_rule);
    1.46      }
    1.47  
    1.48 +    /// \brief Reset all the parameters that have been given before.
    1.49 +    ///
    1.50 +    /// This function resets all the paramaters that have been given
    1.51 +    /// using \ref lowerMap(), \ref upperMap(), \ref capacityMap(),
    1.52 +    /// \ref boundMaps(), \ref costMap(), \ref supplyMap() and
    1.53 +    /// \ref stSupply() functions before.
    1.54 +    ///
    1.55 +    /// It is useful for multiple run() calls. If this function is not
    1.56 +    /// used, all the parameters given before are kept for the next
    1.57 +    /// \ref run() call.
    1.58 +    ///
    1.59 +    /// For example,
    1.60 +    /// \code
    1.61 +    ///   NetworkSimplex<ListDigraph> ns(graph);
    1.62 +    ///
    1.63 +    ///   // First run
    1.64 +    ///   ns.lowerMap(lower).capacityMap(cap).costMap(cost)
    1.65 +    ///     .supplyMap(sup).run();
    1.66 +    ///
    1.67 +    ///   // Run again with modified cost map (reset() is not called,
    1.68 +    ///   // so only the cost map have to be set again)
    1.69 +    ///   cost[e] += 100;
    1.70 +    ///   ns.costMap(cost).run();
    1.71 +    ///
    1.72 +    ///   // Run again from scratch using reset()
    1.73 +    ///   // (the lower bounds will be set to zero on all arcs)
    1.74 +    ///   ns.reset();
    1.75 +    ///   ns.capacityMap(cap).costMap(cost)
    1.76 +    ///     .supplyMap(sup).run();
    1.77 +    /// \endcode
    1.78 +    ///
    1.79 +    /// \return <tt>(*this)</tt>
    1.80 +    NetworkSimplex& reset() {
    1.81 +      delete _plower;
    1.82 +      delete _pupper;
    1.83 +      delete _pcost;
    1.84 +      delete _psupply;
    1.85 +      _plower = NULL;
    1.86 +      _pupper = NULL;
    1.87 +      _pcost = NULL;
    1.88 +      _psupply = NULL;
    1.89 +      _pstsup = false;
    1.90 +      return *this;
    1.91 +    }
    1.92 +
    1.93      /// @}
    1.94  
    1.95      /// \name Query Functions
    1.96 @@ -920,8 +976,8 @@
    1.97        _cap.resize(all_arc_num);
    1.98        _cost.resize(all_arc_num);
    1.99        _supply.resize(all_node_num);
   1.100 -      _flow.resize(all_arc_num, 0);
   1.101 -      _pi.resize(all_node_num, 0);
   1.102 +      _flow.resize(all_arc_num);
   1.103 +      _pi.resize(all_node_num);
   1.104  
   1.105        _parent.resize(all_node_num);
   1.106        _pred.resize(all_node_num);
   1.107 @@ -930,7 +986,7 @@
   1.108        _rev_thread.resize(all_node_num);
   1.109        _succ_num.resize(all_node_num);
   1.110        _last_succ.resize(all_node_num);
   1.111 -      _state.resize(all_arc_num, STATE_LOWER);
   1.112 +      _state.resize(all_arc_num);
   1.113  
   1.114        // Initialize node related data
   1.115        bool valid_supply = true;
   1.116 @@ -986,12 +1042,16 @@
   1.117            _target[i] = _node_id[_graph.target(e)];
   1.118            _cap[i] = (*_pupper)[e];
   1.119            _cost[i] = (*_pcost)[e];
   1.120 +          _flow[i] = 0;
   1.121 +          _state[i] = STATE_LOWER;
   1.122          }
   1.123        } else {
   1.124          for (int i = 0; i != _arc_num; ++i) {
   1.125            Arc e = _arc_ref[i];
   1.126            _source[i] = _node_id[_graph.source(e)];
   1.127            _target[i] = _node_id[_graph.target(e)];
   1.128 +          _flow[i] = 0;
   1.129 +          _state[i] = STATE_LOWER;
   1.130          }
   1.131          if (_pupper) {
   1.132            for (int i = 0; i != _arc_num; ++i)
   1.133 @@ -1032,6 +1092,9 @@
   1.134          _last_succ[u] = u;
   1.135          _parent[u] = _root;
   1.136          _pred[u] = e;
   1.137 +        _cost[e] = max_cost;
   1.138 +        _cap[e] = max_cap;
   1.139 +        _state[e] = STATE_TREE;
   1.140          if (_supply[u] >= 0) {
   1.141            _flow[e] = _supply[u];
   1.142            _forward[u] = true;
   1.143 @@ -1041,9 +1104,6 @@
   1.144            _forward[u] = false;
   1.145            _pi[u] = max_cost;
   1.146          }
   1.147 -        _cost[e] = max_cost;
   1.148 -        _cap[e] = max_cap;
   1.149 -        _state[e] = STATE_TREE;
   1.150        }
   1.151  
   1.152        return true;
     2.1 --- a/test/min_cost_flow_test.cc	Wed Mar 25 15:58:44 2009 +0100
     2.2 +++ b/test/min_cost_flow_test.cc	Wed Mar 25 21:37:50 2009 +0100
     2.3 @@ -89,7 +89,8 @@
     2.4  
     2.5        MCF mcf(g);
     2.6  
     2.7 -      b = mcf.lowerMap(lower)
     2.8 +      b = mcf.reset()
     2.9 +             .lowerMap(lower)
    2.10               .upperMap(upper)
    2.11               .capacityMap(upper)
    2.12               .boundMaps(lower, upper)
    2.13 @@ -242,46 +243,44 @@
    2.14  
    2.15    // A. Test NetworkSimplex with the default pivot rule
    2.16    {
    2.17 -    NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr),
    2.18 -                            mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr);
    2.19 +    NetworkSimplex<Digraph> mcf(gr);
    2.20  
    2.21 -    checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(),
    2.22 +    mcf.upperMap(u).costMap(c);
    2.23 +    checkMcf(mcf, mcf.supplyMap(s1).run(),
    2.24               gr, l1, u, c, s1, true,  5240, "#A1");
    2.25 -    checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(),
    2.26 +    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
    2.27               gr, l1, u, c, s2, true,  7620, "#A2");
    2.28 -    checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(),
    2.29 +    mcf.lowerMap(l2);
    2.30 +    checkMcf(mcf, mcf.supplyMap(s1).run(),
    2.31               gr, l2, u, c, s1, true,  5970, "#A3");
    2.32 -    checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(),
    2.33 +    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
    2.34               gr, l2, u, c, s2, true,  8010, "#A4");
    2.35 -    checkMcf(mcf5, mcf5.supplyMap(s1).run(),
    2.36 +    mcf.reset();
    2.37 +    checkMcf(mcf, mcf.supplyMap(s1).run(),
    2.38               gr, l1, cu, cc, s1, true,  74, "#A5");
    2.39 -    checkMcf(mcf6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(),
    2.40 +    checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
    2.41               gr, l2, cu, cc, s2, true,  94, "#A6");
    2.42 -    checkMcf(mcf7, mcf7.run(),
    2.43 +    mcf.reset();
    2.44 +    checkMcf(mcf, mcf.run(),
    2.45               gr, l1, cu, cc, s3, true,   0, "#A7");
    2.46 -    checkMcf(mcf8, mcf8.boundMaps(l2, u).run(),
    2.47 +    checkMcf(mcf, mcf.boundMaps(l2, u).run(),
    2.48               gr, l2, u, cc, s3, false,   0, "#A8");
    2.49    }
    2.50  
    2.51    // B. Test NetworkSimplex with each pivot rule
    2.52    {
    2.53 -    NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr);
    2.54 -    NetworkSimplex<Digraph>::PivotRule pr;
    2.55 +    NetworkSimplex<Digraph> mcf(gr);
    2.56 +    mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2);
    2.57  
    2.58 -    pr = NetworkSimplex<Digraph>::FIRST_ELIGIBLE;
    2.59 -    checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
    2.60 +    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
    2.61               gr, l2, u, c, s1, true,  5970, "#B1");
    2.62 -    pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE;
    2.63 -    checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
    2.64 +    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
    2.65               gr, l2, u, c, s1, true,  5970, "#B2");
    2.66 -    pr = NetworkSimplex<Digraph>::BLOCK_SEARCH;
    2.67 -    checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
    2.68 +    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
    2.69               gr, l2, u, c, s1, true,  5970, "#B3");
    2.70 -    pr = NetworkSimplex<Digraph>::CANDIDATE_LIST;
    2.71 -    checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
    2.72 +    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
    2.73               gr, l2, u, c, s1, true,  5970, "#B4");
    2.74 -    pr = NetworkSimplex<Digraph>::ALTERING_LIST;
    2.75 -    checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
    2.76 +    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
    2.77               gr, l2, u, c, s1, true,  5970, "#B5");
    2.78    }
    2.79