COIN-OR::LEMON - Graph Library

Changeset 777:4a45c8808b33 in lemon


Ignore:
Timestamp:
09/26/09 07:16:22 (14 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
776:be48a648d28f (diff), 775:e2bdd1a988f3 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r775 r777  
    162162    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    163163
    164     typedef std::vector<Arc> ArcVector;
    165     typedef std::vector<Node> NodeVector;
    166164    typedef std::vector<int> IntVector;
    167165    typedef std::vector<bool> BoolVector;
     
    693691      }
    694692     
    695       // Initialize maps
    696       for (int i = 0; i != _node_num; ++i) {
    697         _supply[i] = 0;
    698       }
    699       for (int i = 0; i != _arc_num; ++i) {
    700         _lower[i] = 0;
    701         _upper[i] = INF;
    702         _cost[i] = 1;
    703       }
    704       _have_lower = false;
    705       _stype = GEQ;
     693      // Reset parameters
     694      reset();
    706695    }
    707696
     
    776765    /// If neither this function nor \ref stSupply() is used before
    777766    /// calling \ref run(), the supply of each node will be set to zero.
    778     /// (It makes sense only if non-zero lower bounds are given.)
    779767    ///
    780768    /// \param map A node map storing the supply values.
     
    797785    /// If neither this function nor \ref supplyMap() is used before
    798786    /// calling \ref run(), the supply of each node will be set to zero.
    799     /// (It makes sense only if non-zero lower bounds are given.)
    800787    ///
    801788    /// Using this function has the same effect as using \ref supplyMap()
  • lemon/network_simplex.h

    r776 r777  
    363363        Cost c, min = 0;
    364364        int cnt = _block_size;
    365         int e, min_arc = _next_arc;
     365        int e;
    366366        for (e = _next_arc; e < _search_arc_num; ++e) {
    367367          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    368368          if (c < min) {
    369369            min = c;
    370             min_arc = e;
     370            _in_arc = e;
    371371          }
    372372          if (--cnt == 0) {
    373             if (min < 0) break;
     373            if (min < 0) goto search_end;
    374374            cnt = _block_size;
    375375          }
    376376        }
    377         if (min == 0 || cnt > 0) {
    378           for (e = 0; e < _next_arc; ++e) {
    379             c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    380             if (c < min) {
    381               min = c;
    382               min_arc = e;
    383             }
    384             if (--cnt == 0) {
    385               if (min < 0) break;
    386               cnt = _block_size;
    387             }
     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;
    388386          }
    389387        }
    390388        if (min >= 0) return false;
    391         _in_arc = min_arc;
     389
     390      search_end:
    392391        _next_arc = e;
    393392        return true;
     
    427426      {
    428427        // The main parameters of the pivot rule
    429         const double LIST_LENGTH_FACTOR = 1.0;
     428        const double LIST_LENGTH_FACTOR = 0.25;
    430429        const int MIN_LIST_LENGTH = 10;
    431430        const double MINOR_LIMIT_FACTOR = 0.1;
     
    444443      bool findEnteringArc() {
    445444        Cost min, c;
    446         int e, min_arc = _next_arc;
     445        int e;
    447446        if (_curr_length > 0 && _minor_count < _minor_limit) {
    448447          // Minor iteration: select the best eligible arc from the
     
    455454            if (c < min) {
    456455              min = c;
    457               min_arc = e;
     456              _in_arc = e;
    458457            }
    459             if (c >= 0) {
     458            else if (c >= 0) {
    460459              _candidates[i--] = _candidates[--_curr_length];
    461460            }
    462461          }
    463           if (min < 0) {
    464             _in_arc = min_arc;
    465             return true;
    466           }
     462          if (min < 0) return true;
    467463        }
    468464
     
    476472            if (c < min) {
    477473              min = c;
    478               min_arc = e;
     474              _in_arc = e;
    479475            }
    480             if (_curr_length == _list_length) break;
    481           }
    482         }
    483         if (_curr_length < _list_length) {
    484           for (e = 0; e < _next_arc; ++e) {
    485             c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    486             if (c < 0) {
    487               _candidates[_curr_length++] = e;
    488               if (c < min) {
    489                 min = c;
    490                 min_arc = e;
    491               }
    492               if (_curr_length == _list_length) break;
     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;
    493486            }
     487            if (_curr_length == _list_length) goto search_end;
    494488          }
    495489        }
    496490        if (_curr_length == 0) return false;
     491     
     492      search_end:       
    497493        _minor_count = 1;
    498         _in_arc = min_arc;
    499494        _next_arc = e;
    500495        return true;
     
    548543      {
    549544        // The main parameters of the pivot rule
    550         const double BLOCK_SIZE_FACTOR = 1.5;
     545        const double BLOCK_SIZE_FACTOR = 1.0;
    551546        const int MIN_BLOCK_SIZE = 10;
    552547        const double HEAD_LENGTH_FACTOR = 0.1;
     
    577572        // Extend the list
    578573        int cnt = _block_size;
    579         int last_arc = 0;
    580574        int limit = _head_length;
    581575
    582         for (int e = _next_arc; e < _search_arc_num; ++e) {
     576        for (e = _next_arc; e < _search_arc_num; ++e) {
    583577          _cand_cost[e] = _state[e] *
    584578            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    585579          if (_cand_cost[e] < 0) {
    586580            _candidates[_curr_length++] = e;
    587             last_arc = e;
    588581          }
    589582          if (--cnt == 0) {
    590             if (_curr_length > limit) break;
     583            if (_curr_length > limit) goto search_end;
    591584            limit = 0;
    592585            cnt = _block_size;
    593586          }
    594587        }
    595         if (_curr_length <= limit) {
    596           for (int e = 0; e < _next_arc; ++e) {
    597             _cand_cost[e] = _state[e] *
    598               (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    599             if (_cand_cost[e] < 0) {
    600               _candidates[_curr_length++] = e;
    601               last_arc = e;
    602             }
    603             if (--cnt == 0) {
    604               if (_curr_length > limit) break;
    605               limit = 0;
    606               cnt = _block_size;
    607             }
     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;
    608598          }
    609599        }
    610600        if (_curr_length == 0) return false;
    611         _next_arc = last_arc + 1;
     601       
     602      search_end:
    612603
    613604        // Make heap of the candidate list (approximating a partial sort)
     
    617608        // Pop the first element of the heap
    618609        _in_arc = _candidates[0];
     610        _next_arc = e;
    619611        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    620612                  _sort_func );
     
    632624    ///
    633625    /// \param graph The digraph the algorithm runs on.
    634     NetworkSimplex(const GR& graph) :
     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) :
    635631      _graph(graph), _node_id(graph), _arc_id(graph),
    636632      INF(std::numeric_limits<Value>::has_infinity ?
     
    670666      _state.resize(max_arc_num);
    671667
    672       // Copy the graph (store the arcs in a mixed order)
     668      // Copy the graph
    673669      int i = 0;
    674670      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    675671        _node_id[n] = i;
    676672      }
    677       int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    678       i = 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 = (i % k) + 1;
     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        }
    684691      }
    685692     
Note: See TracChangeset for help on using the changeset viewer.