Changeset 653:c7d160f73d52 in lemon

Timestamp:

03/25/09 21:37:50 (16 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Support multiple run() calls in NetworkSimplex? (#234)

Files:

• lemon/network_simplex.h (modified) (11 diffs)
• test/min_cost_flow_test.cc (modified) (3 diffs)

lemon/network_simplex.h

@@ -42 +42 @@
   /// \ref NetworkSimplex implements the primal Network Simplex algorithm
   /// for finding a \ref min_cost_flow "minimum cost flow".
+  /// This algorithm is a specialized version of the linear programming
+  /// simplex method directly for the minimum cost flow problem.
+  /// It is one of the most efficient solution methods.
+  ///
+  /// In general this class is the fastest implementation available
+  /// in LEMON for the minimum cost flow problem.
   ///
   /// \tparam GR The digraph type the algorithm runs on.
@@ -47 +53 @@
   /// By default it is \c int.
   ///
-  /// \warning \c V must be a signed integer type.
+  /// \warning The value type must be a signed integer type.
   ///
   /// \note %NetworkSimplex provides five different pivot rule
@@ -790 +796 @@
     /// This function runs the algorithm.
     /// The paramters can be specified using \ref lowerMap(),
-    /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(), 
+    /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(),
     /// \ref costMap(), \ref supplyMap() and \ref stSupply()
     /// functions. For example,
@@ -799 +805 @@
     /// \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.
+    ///
     /// \param pivot_rule The pivot rule that will be used during the
     /// algorithm. For more information see \ref PivotRule.
@@ -805 +816 @@
     bool run(PivotRule pivot_rule = BLOCK_SEARCH) {
       return init() && start(pivot_rule);
+    }
+
+    /// \brief Reset all the parameters that have been given before.
+    ///
+    /// This function resets all the paramaters that have been given
+    /// using \ref lowerMap(), \ref upperMap(), \ref capacityMap(),
+    /// \ref boundMaps(), \ref costMap(), \ref supplyMap() and
+    /// \ref stSupply() functions before.
+    ///
+    /// 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.
+    ///
+    /// For example,
+    /// \code
+    ///   NetworkSimplex<ListDigraph> ns(graph);
+    ///
+    ///   // First run
+    ///   ns.lowerMap(lower).capacityMap(cap).costMap(cost)
+    ///     .supplyMap(sup).run();
+    ///
+    ///   // Run again with modified cost map (reset() 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()
+    ///   // (the lower bounds will be set to zero on all arcs)
+    ///   ns.reset();
+    ///   ns.capacityMap(cap).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// \return <tt>(*this)</tt>
+    NetworkSimplex& reset() {
+      delete _plower;
+      delete _pupper;
+      delete _pcost;
+      delete _psupply;
+      _plower = NULL;
+      _pupper = NULL;
+      _pcost = NULL;
+      _psupply = NULL;
+      _pstsup = false;
+      return *this;
     }
 
@@ -921 +977 @@
       _cost.resize(all_arc_num);
       _supply.resize(all_node_num);
-      _flow.resize(all_arc_num, 0);
-      _pi.resize(all_node_num, 0);
+      _flow.resize(all_arc_num);
+      _pi.resize(all_node_num);
 
       _parent.resize(all_node_num);
@@ -931 +987 @@
       _succ_num.resize(all_node_num);
       _last_succ.resize(all_node_num);
-      _state.resize(all_arc_num, STATE_LOWER);
+      _state.resize(all_arc_num);
 
       // Initialize node related data
@@ -987 +1043 @@
           _cap[i] = (*_pupper)[e];
           _cost[i] = (*_pcost)[e];
+          _flow[i] = 0;
+          _state[i] = STATE_LOWER;
         }
       } else {
@@ -993 +1051 @@
           _source[i] = _node_id[_graph.source(e)];
           _target[i] = _node_id[_graph.target(e)];
+          _flow[i] = 0;
+          _state[i] = STATE_LOWER;
         }
         if (_pupper) {
@@ -1033 +1093 @@
         _parent[u] = _root;
         _pred[u] = e;
+        _cost[e] = max_cost;
+        _cap[e] = max_cap;
+        _state[e] = STATE_TREE;
         if (_supply[u] >= 0) {
           _flow[e] = _supply[u];
@@ -1042 +1105 @@
           _pi[u] = max_cost;
         }
-        _cost[e] = max_cost;
-        _cap[e] = max_cap;
-        _state[e] = STATE_TREE;
       }
 

test/min_cost_flow_test.cc

@@ -90 +90 @@
       MCF mcf(g);
 
-      b = mcf.lowerMap(lower)
+      b = mcf.reset()
+             .lowerMap(lower)
              .upperMap(upper)
              .capacityMap(upper)
@@ -243 +244 @@
   // A. Test NetworkSimplex with the default pivot rule
   {
-    NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr),
-                            mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr);
-
-    checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(),
+    NetworkSimplex<Digraph> mcf(gr);
+
+    mcf.upperMap(u).costMap(c);
+    checkMcf(mcf, mcf.supplyMap(s1).run(),
              gr, l1, u, c, s1, true,  5240, "#A1");
-    checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(),
+    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
              gr, l1, u, c, s2, true,  7620, "#A2");
-    checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(),
+    mcf.lowerMap(l2);
+    checkMcf(mcf, mcf.supplyMap(s1).run(),
              gr, l2, u, c, s1, true,  5970, "#A3");
-    checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(),
+    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
              gr, l2, u, c, s2, true,  8010, "#A4");
-    checkMcf(mcf5, mcf5.supplyMap(s1).run(),
+    mcf.reset();
+    checkMcf(mcf, mcf.supplyMap(s1).run(),
              gr, l1, cu, cc, s1, true,  74, "#A5");
-    checkMcf(mcf6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(),
+    checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
              gr, l2, cu, cc, s2, true,  94, "#A6");
-    checkMcf(mcf7, mcf7.run(),
+    mcf.reset();
+    checkMcf(mcf, mcf.run(),
              gr, l1, cu, cc, s3, true,   0, "#A7");
-    checkMcf(mcf8, mcf8.boundMaps(l2, u).run(),
+    checkMcf(mcf, mcf.boundMaps(l2, u).run(),
              gr, l2, u, cc, s3, false,   0, "#A8");
   }
@@ -266 +270 @@
   // B. Test NetworkSimplex with each pivot rule
   {
-    NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr);
-    NetworkSimplex<Digraph>::PivotRule pr;
-
-    pr = NetworkSimplex<Digraph>::FIRST_ELIGIBLE;
-    checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+    NetworkSimplex<Digraph> mcf(gr);
+    mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2);
+
+    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
              gr, l2, u, c, s1, true,  5970, "#B1");
-    pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE;
-    checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
              gr, l2, u, c, s1, true,  5970, "#B2");
-    pr = NetworkSimplex<Digraph>::BLOCK_SEARCH;
-    checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
              gr, l2, u, c, s1, true,  5970, "#B3");
-    pr = NetworkSimplex<Digraph>::CANDIDATE_LIST;
-    checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
              gr, l2, u, c, s1, true,  5970, "#B4");
-    pr = NetworkSimplex<Digraph>::ALTERING_LIST;
-    checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
              gr, l2, u, c, s1, true,  5970, "#B5");
   }