COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/network_simplex.h

    r835 r898  
    4444  /// \ref amo93networkflows, \ref dantzig63linearprog,
    4545  /// \ref kellyoneill91netsimplex.
    46   /// This algorithm is a specialized version of the linear programming
    47   /// simplex method directly for the minimum cost flow problem.
    48   /// It is one of the most efficient solution methods.
     46  /// This algorithm is a highly efficient specialized version of the
     47  /// linear programming simplex method directly for the minimum cost
     48  /// flow problem.
    4949  ///
    50   /// In general this class is the fastest implementation available
    51   /// in LEMON for the minimum cost flow problem.
    52   /// Moreover it supports both directions of the supply/demand inequality
     50  /// In general, %NetworkSimplex is the fastest implementation available
     51  /// in LEMON for this problem.
     52  /// Moreover, it supports both directions of the supply/demand inequality
    5353  /// constraints. For more information, see \ref SupplyType.
    5454  ///
    … …  
    5959  ///
    6060  /// \tparam GR The digraph type the algorithm runs on.
    61   /// \tparam V The value type used for flow amounts, capacity bounds
     61  /// \tparam V The number type used for flow amounts, capacity bounds
    6262  /// and supply values in the algorithm. By default, it is \c int.
    63   /// \tparam C The value type used for costs and potentials in the
     63  /// \tparam C The number type used for costs and potentials in the
    6464  /// algorithm. By default, it is the same as \c V.
    6565  ///
    66   /// \warning Both value types must be signed and all input data must
     66  /// \warning Both number types must be signed and all input data must
    6767  /// be integer.
    6868  ///
    … …  
    127127    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
    128128    /// proved to be the most efficient and the most robust on various
    129     /// test inputs according to our benchmark tests.
     129    /// test inputs.
    130130    /// However, another pivot rule can be selected using the \ref run()
    131131    /// function with the proper parameter.
    … …  
    165165
    166166    typedef std::vector<int> IntVector;
    167     typedef std::vector<bool> BoolVector;
     167    typedef std::vector<char> CharVector;
    168168    typedef std::vector<Value> ValueVector;
    169169    typedef std::vector<Cost> CostVector;
    … …  
    195195    IntVector _source;
    196196    IntVector _target;
     197    bool _arc_mixing;
    197198
    198199    // Node and arc data
    … …  
    213214    IntVector _last_succ;
    214215    IntVector _dirty_revs;
    215     BoolVector _forward;
    216     IntVector _state;
     216    CharVector _forward;
     217    CharVector _state;
    217218    int _root;
    218219
    … …  
    222223    int stem, par_stem, new_stem;
    223224    Value delta;
     225   
     226    const Value MAX;
    224227
    225228  public:
    … …  
    243246      const IntVector  &_target;
    244247      const CostVector &_cost;
    245       const IntVector &_state;
     248      const CharVector &_state;
    246249      const CostVector &_pi;
    247250      int &_in_arc;
    … …  
    295298      const IntVector  &_target;
    296299      const CostVector &_cost;
    297       const IntVector &_state;
     300      const CharVector &_state;
    298301      const CostVector &_pi;
    299302      int &_in_arc;
    … …  
    334337      const IntVector  &_target;
    335338      const CostVector &_cost;
    336       const IntVector &_state;
     339      const CharVector &_state;
    337340      const CostVector &_pi;
    338341      int &_in_arc;
    … …  
    407410      const IntVector  &_target;
    408411      const CostVector &_cost;
    409       const IntVector &_state;
     412      const CharVector &_state;
    410413      const CostVector &_pi;
    411414      int &_in_arc;
    … …  
    510513      const IntVector  &_target;
    511514      const CostVector &_cost;
    512       const IntVector &_state;
     515      const CharVector &_state;
    513516      const CostVector &_pi;
    514517      int &_in_arc;
    … …  
    632635    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    633636      _graph(graph), _node_id(graph), _arc_id(graph),
     637      _arc_mixing(arc_mixing),
     638      MAX(std::numeric_limits<Value>::max()),
    634639      INF(std::numeric_limits<Value>::has_infinity ?
    635           std::numeric_limits<Value>::infinity() :
    636           std::numeric_limits<Value>::max())
     640          std::numeric_limits<Value>::infinity() : MAX)
    637641    {
    638       // Check the value types
     642      // Check the number types
    639643      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
    640644        "The flow type of NetworkSimplex must be signed");
    … …  
    642646        "The cost type of NetworkSimplex must be signed");
    643647       
    644       // Resize vectors
    645       _node_num = countNodes(_graph);
    646       _arc_num = countArcs(_graph);
    647       int all_node_num = _node_num + 1;
    648       int max_arc_num = _arc_num + 2 * _node_num;
    649 
    650       _source.resize(max_arc_num);
    651       _target.resize(max_arc_num);
    652 
    653       _lower.resize(_arc_num);
    654       _upper.resize(_arc_num);
    655       _cap.resize(max_arc_num);
    656       _cost.resize(max_arc_num);
    657       _supply.resize(all_node_num);
    658       _flow.resize(max_arc_num);
    659       _pi.resize(all_node_num);
    660 
    661       _parent.resize(all_node_num);
    662       _pred.resize(all_node_num);
    663       _forward.resize(all_node_num);
    664       _thread.resize(all_node_num);
    665       _rev_thread.resize(all_node_num);
    666       _succ_num.resize(all_node_num);
    667       _last_succ.resize(all_node_num);
    668       _state.resize(max_arc_num);
    669 
    670       // Copy the graph
    671       int i = 0;
    672       for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    673         _node_id[n] = i;
    674       }
    675       if (arc_mixing) {
    676         // Store the arcs in a mixed order
    677         int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    678         int i = 0, j = 0;
    679         for (ArcIt a(_graph); a != INVALID; ++a) {
    680           _arc_id[a] = i;
    681           _source[i] = _node_id[_graph.source(a)];
    682           _target[i] = _node_id[_graph.target(a)];
    683           if ((i += k) >= _arc_num) i = ++j;
    684         }
    685       } else {
    686         // Store the arcs in the original order
    687         int i = 0;
    688         for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
    689           _arc_id[a] = i;
    690           _source[i] = _node_id[_graph.source(a)];
    691           _target[i] = _node_id[_graph.target(a)];
    692         }
    693       }
    694      
    695       // Reset parameters
     648      // Reset data structures
    696649      reset();
    697650    }
    … …  
    728681    /// If it is not used before calling \ref run(), the upper bounds
    729682    /// will be set to \ref INF on all arcs (i.e. the flow value will be
    730     /// unbounded from above on each arc).
     683    /// unbounded from above).
    731684    ///
    732685    /// \param map An arc map storing the upper bounds.
    … …  
    841794    /// \endcode
    842795    ///
    843     /// This function can be called more than once. All the parameters
    844     /// that have been given are kept for the next call, unless
    845     /// \ref reset() is called, thus only the modified parameters
    846     /// have to be set again. See \ref reset() for examples.
    847     /// However, the underlying digraph must not be modified after this
    848     /// class have been constructed, since it copies and extends the graph.
     796    /// This function can be called more than once. All the given parameters
     797    /// are kept for the next call, unless \ref resetParams() or \ref reset()
     798    /// is used, thus only the modified parameters have to be set again.
     799    /// If the underlying digraph was also modified after the construction
     800    /// of the class (or the last \ref reset() call), then the \ref reset()
     801    /// function must be called.
    849802    ///
    850803    /// \param pivot_rule The pivot rule that will be used during the
    … …  
    860813    ///
    861814    /// \see ProblemType, PivotRule
     815    /// \see resetParams(), reset()
    862816    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
    863817      if (!init()) return INFEASIBLE;
    … …  
    871825    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
    872826    ///
    873     /// It is useful for multiple run() calls. If this function is not
    874     /// used, all the parameters given before are kept for the next
    875     /// \ref run() call.
    876     /// However, the underlying digraph must not be modified after this
    877     /// class have been constructed, since it copies and extends the graph.
     827    /// It is useful for multiple \ref run() calls. Basically, all the given
     828    /// parameters are kept for the next \ref run() call, unless
     829    /// \ref resetParams() or \ref reset() is used.
     830    /// If the underlying digraph was also modified after the construction
     831    /// of the class or the last \ref reset() call, then the \ref reset()
     832    /// function must be used, otherwise \ref resetParams() is sufficient.
    878833    ///
    879834    /// For example,
    … …  
    885840    ///     .supplyMap(sup).run();
    886841    ///
    887     ///   // Run again with modified cost map (reset() is not called,
     842    ///   // Run again with modified cost map (resetParams() is not called,
    888843    ///   // so only the cost map have to be set again)
    889844    ///   cost[e] += 100;
    890845    ///   ns.costMap(cost).run();
    891846    ///
    892     ///   // Run again from scratch using reset()
     847    ///   // Run again from scratch using resetParams()
    893848    ///   // (the lower bounds will be set to zero on all arcs)
    894     ///   ns.reset();
     849    ///   ns.resetParams();
    895850    ///   ns.upperMap(capacity).costMap(cost)
    896851    ///     .supplyMap(sup).run();
    … …  
    898853    ///
    899854    /// \return <tt>(*this)</tt>
    900     NetworkSimplex& reset() {
     855    ///
     856    /// \see reset(), run()
     857    NetworkSimplex& resetParams() {
    901858      for (int i = 0; i != _node_num; ++i) {
    902859        _supply[i] = 0;
    … …  
    912869    }
    913870
     871    /// \brief Reset the internal data structures and all the parameters
     872    /// that have been given before.
     873    ///
     874    /// This function resets the internal data structures and all the
     875    /// paramaters that have been given before using functions \ref lowerMap(),
     876    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
     877    /// \ref supplyType().
     878    ///
     879    /// It is useful for multiple \ref run() calls. Basically, all the given
     880    /// parameters are kept for the next \ref run() call, unless
     881    /// \ref resetParams() or \ref reset() is used.
     882    /// If the underlying digraph was also modified after the construction
     883    /// of the class or the last \ref reset() call, then the \ref reset()
     884    /// function must be used, otherwise \ref resetParams() is sufficient.
     885    ///
     886    /// See \ref resetParams() for examples.
     887    ///
     888    /// \return <tt>(*this)</tt>
     889    ///
     890    /// \see resetParams(), run()
     891    NetworkSimplex& reset() {
     892      // Resize vectors
     893      _node_num = countNodes(_graph);
     894      _arc_num = countArcs(_graph);
     895      int all_node_num = _node_num + 1;
     896      int max_arc_num = _arc_num + 2 * _node_num;
     897
     898      _source.resize(max_arc_num);
     899      _target.resize(max_arc_num);
     900
     901      _lower.resize(_arc_num);
     902      _upper.resize(_arc_num);
     903      _cap.resize(max_arc_num);
     904      _cost.resize(max_arc_num);
     905      _supply.resize(all_node_num);
     906      _flow.resize(max_arc_num);
     907      _pi.resize(all_node_num);
     908
     909      _parent.resize(all_node_num);
     910      _pred.resize(all_node_num);
     911      _forward.resize(all_node_num);
     912      _thread.resize(all_node_num);
     913      _rev_thread.resize(all_node_num);
     914      _succ_num.resize(all_node_num);
     915      _last_succ.resize(all_node_num);
     916      _state.resize(max_arc_num);
     917
     918      // Copy the graph
     919      int i = 0;
     920      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
     921        _node_id[n] = i;
     922      }
     923      if (_arc_mixing) {
     924        // Store the arcs in a mixed order
     925        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     926        int i = 0, j = 0;
     927        for (ArcIt a(_graph); a != INVALID; ++a) {
     928          _arc_id[a] = i;
     929          _source[i] = _node_id[_graph.source(a)];
     930          _target[i] = _node_id[_graph.target(a)];
     931          if ((i += k) >= _arc_num) i = ++j;
     932        }
     933      } else {
     934        // Store the arcs in the original order
     935        int i = 0;
     936        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
     937          _arc_id[a] = i;
     938          _source[i] = _node_id[_graph.source(a)];
     939          _target[i] = _node_id[_graph.target(a)];
     940        }
     941      }
     942     
     943      // Reset parameters
     944      resetParams();
     945      return *this;
     946    }
     947   
    914948    /// @}
    915949
    … …  
    10211055          Value c = _lower[i];
    10221056          if (c >= 0) {
    1023             _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
     1057            _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
    10241058          } else {
    1025             _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
     1059            _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
    10261060          }
    10271061          _supply[_source[i]] -= c;
    … …  
    12151249        e = _pred[u];
    12161250        d = _forward[u] ?
    1217           _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
     1251          _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
    12181252        if (d < delta) {
    12191253          delta = d;
    … …  
    12261260        e = _pred[u];
    12271261        d = _forward[u] ?
    1228           (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
     1262          (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
    12291263        if (d <= delta) {
    12301264          delta = d;
    … …  
    14251459        findJoinNode();
    14261460        bool change = findLeavingArc();
    1427         if (delta >= INF) return UNBOUNDED;
     1461        if (delta >= MAX) return UNBOUNDED;
    14281462        changeFlow(change);
    14291463        if (change) {
Note: See TracChangeset for help on using the changeset viewer.