COIN-OR::LEMON - Graph Library

Changeset 606:c7d160f73d52 in lemon-main


Ignore:
Timestamp:
03/25/09 21:37:50 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

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

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r605 r606  
    4242  /// \ref NetworkSimplex implements the primal Network Simplex algorithm
    4343  /// for finding a \ref min_cost_flow "minimum cost flow".
     44  /// This algorithm is a specialized version of the linear programming
     45  /// simplex method directly for the minimum cost flow problem.
     46  /// It is one of the most efficient solution methods.
     47  ///
     48  /// In general this class is the fastest implementation available
     49  /// in LEMON for the minimum cost flow problem.
    4450  ///
    4551  /// \tparam GR The digraph type the algorithm runs on.
     
    4753  /// By default it is \c int.
    4854  ///
    49   /// \warning \c V must be a signed integer type.
     55  /// \warning The value type must be a signed integer type.
    5056  ///
    5157  /// \note %NetworkSimplex provides five different pivot rule
     
    790796    /// This function runs the algorithm.
    791797    /// The paramters can be specified using \ref lowerMap(),
    792     /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(), 
     798    /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(),
    793799    /// \ref costMap(), \ref supplyMap() and \ref stSupply()
    794800    /// functions. For example,
     
    799805    /// \endcode
    800806    ///
     807    /// This function can be called more than once. All the parameters
     808    /// that have been given are kept for the next call, unless
     809    /// \ref reset() is called, thus only the modified parameters
     810    /// have to be set again. See \ref reset() for examples.
     811    ///
    801812    /// \param pivot_rule The pivot rule that will be used during the
    802813    /// algorithm. For more information see \ref PivotRule.
     
    805816    bool run(PivotRule pivot_rule = BLOCK_SEARCH) {
    806817      return init() && start(pivot_rule);
     818    }
     819
     820    /// \brief Reset all the parameters that have been given before.
     821    ///
     822    /// This function resets all the paramaters that have been given
     823    /// using \ref lowerMap(), \ref upperMap(), \ref capacityMap(),
     824    /// \ref boundMaps(), \ref costMap(), \ref supplyMap() and
     825    /// \ref stSupply() functions before.
     826    ///
     827    /// It is useful for multiple run() calls. If this function is not
     828    /// used, all the parameters given before are kept for the next
     829    /// \ref run() call.
     830    ///
     831    /// For example,
     832    /// \code
     833    ///   NetworkSimplex<ListDigraph> ns(graph);
     834    ///
     835    ///   // First run
     836    ///   ns.lowerMap(lower).capacityMap(cap).costMap(cost)
     837    ///     .supplyMap(sup).run();
     838    ///
     839    ///   // Run again with modified cost map (reset() is not called,
     840    ///   // so only the cost map have to be set again)
     841    ///   cost[e] += 100;
     842    ///   ns.costMap(cost).run();
     843    ///
     844    ///   // Run again from scratch using reset()
     845    ///   // (the lower bounds will be set to zero on all arcs)
     846    ///   ns.reset();
     847    ///   ns.capacityMap(cap).costMap(cost)
     848    ///     .supplyMap(sup).run();
     849    /// \endcode
     850    ///
     851    /// \return <tt>(*this)</tt>
     852    NetworkSimplex& reset() {
     853      delete _plower;
     854      delete _pupper;
     855      delete _pcost;
     856      delete _psupply;
     857      _plower = NULL;
     858      _pupper = NULL;
     859      _pcost = NULL;
     860      _psupply = NULL;
     861      _pstsup = false;
     862      return *this;
    807863    }
    808864
     
    921977      _cost.resize(all_arc_num);
    922978      _supply.resize(all_node_num);
    923       _flow.resize(all_arc_num, 0);
    924       _pi.resize(all_node_num, 0);
     979      _flow.resize(all_arc_num);
     980      _pi.resize(all_node_num);
    925981
    926982      _parent.resize(all_node_num);
     
    931987      _succ_num.resize(all_node_num);
    932988      _last_succ.resize(all_node_num);
    933       _state.resize(all_arc_num, STATE_LOWER);
     989      _state.resize(all_arc_num);
    934990
    935991      // Initialize node related data
     
    9871043          _cap[i] = (*_pupper)[e];
    9881044          _cost[i] = (*_pcost)[e];
     1045          _flow[i] = 0;
     1046          _state[i] = STATE_LOWER;
    9891047        }
    9901048      } else {
     
    9931051          _source[i] = _node_id[_graph.source(e)];
    9941052          _target[i] = _node_id[_graph.target(e)];
     1053          _flow[i] = 0;
     1054          _state[i] = STATE_LOWER;
    9951055        }
    9961056        if (_pupper) {
     
    10331093        _parent[u] = _root;
    10341094        _pred[u] = e;
     1095        _cost[e] = max_cost;
     1096        _cap[e] = max_cap;
     1097        _state[e] = STATE_TREE;
    10351098        if (_supply[u] >= 0) {
    10361099          _flow[e] = _supply[u];
     
    10421105          _pi[u] = max_cost;
    10431106        }
    1044         _cost[e] = max_cost;
    1045         _cap[e] = max_cap;
    1046         _state[e] = STATE_TREE;
    10471107      }
    10481108
  • test/min_cost_flow_test.cc

    r605 r606  
    9090      MCF mcf(g);
    9191
    92       b = mcf.lowerMap(lower)
     92      b = mcf.reset()
     93             .lowerMap(lower)
    9394             .upperMap(upper)
    9495             .capacityMap(upper)
     
    243244  // A. Test NetworkSimplex with the default pivot rule
    244245  {
    245     NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr),
    246                             mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr);
    247 
    248     checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(),
     246    NetworkSimplex<Digraph> mcf(gr);
     247
     248    mcf.upperMap(u).costMap(c);
     249    checkMcf(mcf, mcf.supplyMap(s1).run(),
    249250             gr, l1, u, c, s1, true,  5240, "#A1");
    250     checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(),
     251    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
    251252             gr, l1, u, c, s2, true,  7620, "#A2");
    252     checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(),
     253    mcf.lowerMap(l2);
     254    checkMcf(mcf, mcf.supplyMap(s1).run(),
    253255             gr, l2, u, c, s1, true,  5970, "#A3");
    254     checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(),
     256    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
    255257             gr, l2, u, c, s2, true,  8010, "#A4");
    256     checkMcf(mcf5, mcf5.supplyMap(s1).run(),
     258    mcf.reset();
     259    checkMcf(mcf, mcf.supplyMap(s1).run(),
    257260             gr, l1, cu, cc, s1, true,  74, "#A5");
    258     checkMcf(mcf6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(),
     261    checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
    259262             gr, l2, cu, cc, s2, true,  94, "#A6");
    260     checkMcf(mcf7, mcf7.run(),
     263    mcf.reset();
     264    checkMcf(mcf, mcf.run(),
    261265             gr, l1, cu, cc, s3, true,   0, "#A7");
    262     checkMcf(mcf8, mcf8.boundMaps(l2, u).run(),
     266    checkMcf(mcf, mcf.boundMaps(l2, u).run(),
    263267             gr, l2, u, cc, s3, false,   0, "#A8");
    264268  }
     
    266270  // B. Test NetworkSimplex with each pivot rule
    267271  {
    268     NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr);
    269     NetworkSimplex<Digraph>::PivotRule pr;
    270 
    271     pr = NetworkSimplex<Digraph>::FIRST_ELIGIBLE;
    272     checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
     272    NetworkSimplex<Digraph> mcf(gr);
     273    mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2);
     274
     275    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
    273276             gr, l2, u, c, s1, true,  5970, "#B1");
    274     pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE;
    275     checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
     277    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
    276278             gr, l2, u, c, s1, true,  5970, "#B2");
    277     pr = NetworkSimplex<Digraph>::BLOCK_SEARCH;
    278     checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
     279    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
    279280             gr, l2, u, c, s1, true,  5970, "#B3");
    280     pr = NetworkSimplex<Digraph>::CANDIDATE_LIST;
    281     checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
     281    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
    282282             gr, l2, u, c, s1, true,  5970, "#B4");
    283     pr = NetworkSimplex<Digraph>::ALTERING_LIST;
    284     checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
     283    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
    285284             gr, l2, u, c, s1, true,  5970, "#B5");
    286285  }
Note: See TracChangeset for help on using the changeset viewer.