equal
deleted
inserted
replaced
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 } |