lemon/network_simplex.h
changeset 616 f2d6d3446adf
parent 609 e6927fe719e6
child 618 b95898314e09
equal deleted inserted replaced
7:2a9d8e31081e 8:302009ca647c
   379       {
   379       {
   380         // The main parameters of the pivot rule
   380         // The main parameters of the pivot rule
   381         const double BLOCK_SIZE_FACTOR = 2.0;
   381         const double BLOCK_SIZE_FACTOR = 2.0;
   382         const int MIN_BLOCK_SIZE = 10;
   382         const int MIN_BLOCK_SIZE = 10;
   383 
   383 
   384         _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_arc_num)),
   384         _block_size = std::max( int(BLOCK_SIZE_FACTOR *
       
   385                                     std::sqrt(double(_arc_num))),
   385                                 MIN_BLOCK_SIZE );
   386                                 MIN_BLOCK_SIZE );
   386       }
   387       }
   387 
   388 
   388       // Find next entering arc
   389       // Find next entering arc
   389       bool findEnteringArc() {
   390       bool findEnteringArc() {
   455         const double LIST_LENGTH_FACTOR = 1.0;
   456         const double LIST_LENGTH_FACTOR = 1.0;
   456         const int MIN_LIST_LENGTH = 10;
   457         const int MIN_LIST_LENGTH = 10;
   457         const double MINOR_LIMIT_FACTOR = 0.1;
   458         const double MINOR_LIMIT_FACTOR = 0.1;
   458         const int MIN_MINOR_LIMIT = 3;
   459         const int MIN_MINOR_LIMIT = 3;
   459 
   460 
   460         _list_length = std::max( int(LIST_LENGTH_FACTOR * sqrt(_arc_num)),
   461         _list_length = std::max( int(LIST_LENGTH_FACTOR *
       
   462                                      std::sqrt(double(_arc_num))),
   461                                  MIN_LIST_LENGTH );
   463                                  MIN_LIST_LENGTH );
   462         _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length),
   464         _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length),
   463                                  MIN_MINOR_LIMIT );
   465                                  MIN_MINOR_LIMIT );
   464         _curr_length = _minor_count = 0;
   466         _curr_length = _minor_count = 0;
   465         _candidates.resize(_list_length);
   467         _candidates.resize(_list_length);
   575         const double BLOCK_SIZE_FACTOR = 1.5;
   577         const double BLOCK_SIZE_FACTOR = 1.5;
   576         const int MIN_BLOCK_SIZE = 10;
   578         const int MIN_BLOCK_SIZE = 10;
   577         const double HEAD_LENGTH_FACTOR = 0.1;
   579         const double HEAD_LENGTH_FACTOR = 0.1;
   578         const int MIN_HEAD_LENGTH = 3;
   580         const int MIN_HEAD_LENGTH = 3;
   579 
   581 
   580         _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_arc_num)),
   582         _block_size = std::max( int(BLOCK_SIZE_FACTOR *
       
   583                                     std::sqrt(double(_arc_num))),
   581                                 MIN_BLOCK_SIZE );
   584                                 MIN_BLOCK_SIZE );
   582         _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size),
   585         _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size),
   583                                  MIN_HEAD_LENGTH );
   586                                  MIN_HEAD_LENGTH );
   584         _candidates.resize(_head_length + _block_size);
   587         _candidates.resize(_head_length + _block_size);
   585         _curr_length = 0;
   588         _curr_length = 0;
  1223       } else {
  1226       } else {
  1224         _pi[_root] = art_cost;
  1227         _pi[_root] = art_cost;
  1225       }
  1228       }
  1226 
  1229 
  1227       // Store the arcs in a mixed order
  1230       // Store the arcs in a mixed order
  1228       int k = std::max(int(sqrt(_arc_num)), 10);
  1231       int k = std::max(int(std::sqrt(double(_arc_num))), 10);
  1229       int i = 0;
  1232       int i = 0;
  1230       for (ArcIt e(_graph); e != INVALID; ++e) {
  1233       for (ArcIt e(_graph); e != INVALID; ++e) {
  1231         _arc_ref[i] = e;
  1234         _arc_ref[i] = e;
  1232         if ((i += k) >= _arc_num) i = (i % k) + 1;
  1235         if ((i += k) >= _arc_num) i = (i % k) + 1;
  1233       }
  1236       }