COIN-OR::LEMON - Graph Library

Changes in / [731:0977046c60d2:726:3fc2a801c39e] in lemon-main


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r730 r663  
    162162    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    163163
     164    typedef std::vector<Arc> ArcVector;
     165    typedef std::vector<Node> NodeVector;
    164166    typedef std::vector<int> IntVector;
    165167    typedef std::vector<bool> BoolVector;
     
    363365        Cost c, min = 0;
    364366        int cnt = _block_size;
    365         int e;
     367        int e, min_arc = _next_arc;
    366368        for (e = _next_arc; e < _search_arc_num; ++e) {
    367369          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    368370          if (c < min) {
    369371            min = c;
    370             _in_arc = e;
     372            min_arc = e;
    371373          }
    372374          if (--cnt == 0) {
    373             if (min < 0) goto search_end;
     375            if (min < 0) break;
    374376            cnt = _block_size;
    375377          }
    376378        }
    377         for (e = 0; e < _next_arc; ++e) {
    378           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    379           if (c < min) {
    380             min = c;
    381             _in_arc = e;
    382           }
    383           if (--cnt == 0) {
    384             if (min < 0) goto search_end;
    385             cnt = _block_size;
     379        if (min == 0 || cnt > 0) {
     380          for (e = 0; e < _next_arc; ++e) {
     381            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     382            if (c < min) {
     383              min = c;
     384              min_arc = e;
     385            }
     386            if (--cnt == 0) {
     387              if (min < 0) break;
     388              cnt = _block_size;
     389            }
    386390          }
    387391        }
    388392        if (min >= 0) return false;
    389 
    390       search_end:
     393        _in_arc = min_arc;
    391394        _next_arc = e;
    392395        return true;
     
    426429      {
    427430        // The main parameters of the pivot rule
    428         const double LIST_LENGTH_FACTOR = 0.25;
     431        const double LIST_LENGTH_FACTOR = 1.0;
    429432        const int MIN_LIST_LENGTH = 10;
    430433        const double MINOR_LIMIT_FACTOR = 0.1;
     
    443446      bool findEnteringArc() {
    444447        Cost min, c;
    445         int e;
     448        int e, min_arc = _next_arc;
    446449        if (_curr_length > 0 && _minor_count < _minor_limit) {
    447450          // Minor iteration: select the best eligible arc from the
     
    454457            if (c < min) {
    455458              min = c;
    456               _in_arc = e;
     459              min_arc = e;
    457460            }
    458             else if (c >= 0) {
     461            if (c >= 0) {
    459462              _candidates[i--] = _candidates[--_curr_length];
    460463            }
    461464          }
    462           if (min < 0) return true;
     465          if (min < 0) {
     466            _in_arc = min_arc;
     467            return true;
     468          }
    463469        }
    464470
     
    472478            if (c < min) {
    473479              min = c;
    474               _in_arc = e;
     480              min_arc = e;
    475481            }
    476             if (_curr_length == _list_length) goto search_end;
    477           }
    478         }
    479         for (e = 0; e < _next_arc; ++e) {
    480           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    481           if (c < 0) {
    482             _candidates[_curr_length++] = e;
    483             if (c < min) {
    484               min = c;
    485               _in_arc = e;
     482            if (_curr_length == _list_length) break;
     483          }
     484        }
     485        if (_curr_length < _list_length) {
     486          for (e = 0; e < _next_arc; ++e) {
     487            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     488            if (c < 0) {
     489              _candidates[_curr_length++] = e;
     490              if (c < min) {
     491                min = c;
     492                min_arc = e;
     493              }
     494              if (_curr_length == _list_length) break;
    486495            }
    487             if (_curr_length == _list_length) goto search_end;
    488496          }
    489497        }
    490498        if (_curr_length == 0) return false;
    491      
    492       search_end:       
    493499        _minor_count = 1;
     500        _in_arc = min_arc;
    494501        _next_arc = e;
    495502        return true;
     
    543550      {
    544551        // The main parameters of the pivot rule
    545         const double BLOCK_SIZE_FACTOR = 1.0;
     552        const double BLOCK_SIZE_FACTOR = 1.5;
    546553        const int MIN_BLOCK_SIZE = 10;
    547554        const double HEAD_LENGTH_FACTOR = 0.1;
     
    572579        // Extend the list
    573580        int cnt = _block_size;
     581        int last_arc = 0;
    574582        int limit = _head_length;
    575583
    576         for (e = _next_arc; e < _search_arc_num; ++e) {
     584        for (int e = _next_arc; e < _search_arc_num; ++e) {
    577585          _cand_cost[e] = _state[e] *
    578586            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    579587          if (_cand_cost[e] < 0) {
    580588            _candidates[_curr_length++] = e;
     589            last_arc = e;
    581590          }
    582591          if (--cnt == 0) {
    583             if (_curr_length > limit) goto search_end;
     592            if (_curr_length > limit) break;
    584593            limit = 0;
    585594            cnt = _block_size;
    586595          }
    587596        }
    588         for (e = 0; e < _next_arc; ++e) {
    589           _cand_cost[e] = _state[e] *
    590             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    591           if (_cand_cost[e] < 0) {
    592             _candidates[_curr_length++] = e;
    593           }
    594           if (--cnt == 0) {
    595             if (_curr_length > limit) goto search_end;
    596             limit = 0;
    597             cnt = _block_size;
     597        if (_curr_length <= limit) {
     598          for (int e = 0; e < _next_arc; ++e) {
     599            _cand_cost[e] = _state[e] *
     600              (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     601            if (_cand_cost[e] < 0) {
     602              _candidates[_curr_length++] = e;
     603              last_arc = e;
     604            }
     605            if (--cnt == 0) {
     606              if (_curr_length > limit) break;
     607              limit = 0;
     608              cnt = _block_size;
     609            }
    598610          }
    599611        }
    600612        if (_curr_length == 0) return false;
    601        
    602       search_end:
     613        _next_arc = last_arc + 1;
    603614
    604615        // Make heap of the candidate list (approximating a partial sort)
     
    608619        // Pop the first element of the heap
    609620        _in_arc = _candidates[0];
    610         _next_arc = e;
    611621        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    612622                  _sort_func );
     
    624634    ///
    625635    /// \param graph The digraph the algorithm runs on.
    626     /// \param arc_mixing Indicate if the arcs have to be stored in a
    627     /// mixed order in the internal data structure.
    628     /// In special cases, it could lead to better overall performance,
    629     /// but it is usually slower. Therefore it is disabled by default.
    630     NetworkSimplex(const GR& graph, bool arc_mixing = false) :
     636    NetworkSimplex(const GR& graph) :
    631637      _graph(graph), _node_id(graph), _arc_id(graph),
    632638      INF(std::numeric_limits<Value>::has_infinity ?
     
    666672      _state.resize(max_arc_num);
    667673
    668       // Copy the graph
     674      // Copy the graph (store the arcs in a mixed order)
    669675      int i = 0;
    670676      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    671677        _node_id[n] = i;
    672678      }
    673       if (arc_mixing) {
    674         // Store the arcs in a mixed order
    675         int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    676         int i = 0, j = 0;
    677         for (ArcIt a(_graph); a != INVALID; ++a) {
    678           _arc_id[a] = i;
    679           _source[i] = _node_id[_graph.source(a)];
    680           _target[i] = _node_id[_graph.target(a)];
    681           if ((i += k) >= _arc_num) i = ++j;
    682         }
    683       } else {
    684         // Store the arcs in the original order
    685         int i = 0;
    686         for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
    687           _arc_id[a] = i;
    688           _source[i] = _node_id[_graph.source(a)];
    689           _target[i] = _node_id[_graph.target(a)];
    690         }
     679      int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     680      i = 0;
     681      for (ArcIt a(_graph); a != INVALID; ++a) {
     682        _arc_id[a] = i;
     683        _source[i] = _node_id[_graph.source(a)];
     684        _target[i] = _node_id[_graph.target(a)];
     685        if ((i += k) >= _arc_num) i = (i % k) + 1;
    691686      }
    692687     
    693       // Reset parameters
    694       reset();
     688      // Initialize maps
     689      for (int i = 0; i != _node_num; ++i) {
     690        _supply[i] = 0;
     691      }
     692      for (int i = 0; i != _arc_num; ++i) {
     693        _lower[i] = 0;
     694        _upper[i] = INF;
     695        _cost[i] = 1;
     696      }
     697      _have_lower = false;
     698      _stype = GEQ;
    695699    }
    696700
     
    765769    /// If neither this function nor \ref stSupply() is used before
    766770    /// calling \ref run(), the supply of each node will be set to zero.
     771    /// (It makes sense only if non-zero lower bounds are given.)
    767772    ///
    768773    /// \param map A node map storing the supply values.
     
    785790    /// If neither this function nor \ref supplyMap() is used before
    786791    /// calling \ref run(), the supply of each node will be set to zero.
     792    /// (It makes sense only if non-zero lower bounds are given.)
    787793    ///
    788794    /// Using this function has the same effect as using \ref supplyMap()
Note: See TracChangeset for help on using the changeset viewer.