Changeset 774:cab85bd7859b in lemon for lemon/network_simplex.h
 Timestamp:
 07/01/09 16:34:01 (15 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r710 r774 365 365 Cost c, min = 0; 366 366 int cnt = _block_size; 367 int e , min_arc = _next_arc;367 int e; 368 368 for (e = _next_arc; e < _search_arc_num; ++e) { 369 369 c = _state[e] * (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 370 370 if (c < min) { 371 371 min = c; 372 min_arc = e;372 _in_arc = e; 373 373 } 374 374 if (cnt == 0) { 375 if (min < 0) break;375 if (min < 0) goto search_end; 376 376 cnt = _block_size; 377 377 } 378 378 } 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 } 379 for (e = 0; e < _next_arc; ++e) { 380 c = _state[e] * (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 381 if (c < min) { 382 min = c; 383 _in_arc = e; 384 } 385 if (cnt == 0) { 386 if (min < 0) goto search_end; 387 cnt = _block_size; 390 388 } 391 389 } 392 390 if (min >= 0) return false; 393 _in_arc = min_arc; 391 392 search_end: 394 393 _next_arc = e; 395 394 return true; … … 429 428 { 430 429 // The main parameters of the pivot rule 431 const double LIST_LENGTH_FACTOR = 1.0;430 const double LIST_LENGTH_FACTOR = 0.25; 432 431 const int MIN_LIST_LENGTH = 10; 433 432 const double MINOR_LIMIT_FACTOR = 0.1; … … 446 445 bool findEnteringArc() { 447 446 Cost min, c; 448 int e , min_arc = _next_arc;447 int e; 449 448 if (_curr_length > 0 && _minor_count < _minor_limit) { 450 449 // Minor iteration: select the best eligible arc from the … … 457 456 if (c < min) { 458 457 min = c; 459 min_arc = e;458 _in_arc = e; 460 459 } 461 if (c >= 0) {460 else if (c >= 0) { 462 461 _candidates[i] = _candidates[_curr_length]; 463 462 } 464 463 } 465 if (min < 0) { 466 _in_arc = min_arc; 467 return true; 468 } 464 if (min < 0) return true; 469 465 } 470 466 … … 478 474 if (c < min) { 479 475 min = c; 480 min_arc = e;476 _in_arc = e; 481 477 } 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; 478 if (_curr_length == _list_length) goto search_end; 479 } 480 } 481 for (e = 0; e < _next_arc; ++e) { 482 c = _state[e] * (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 483 if (c < 0) { 484 _candidates[_curr_length++] = e; 485 if (c < min) { 486 min = c; 487 _in_arc = e; 495 488 } 489 if (_curr_length == _list_length) goto search_end; 496 490 } 497 491 } 498 492 if (_curr_length == 0) return false; 493 494 search_end: 499 495 _minor_count = 1; 500 _in_arc = min_arc;501 496 _next_arc = e; 502 497 return true; … … 550 545 { 551 546 // The main parameters of the pivot rule 552 const double BLOCK_SIZE_FACTOR = 1. 5;547 const double BLOCK_SIZE_FACTOR = 1.0; 553 548 const int MIN_BLOCK_SIZE = 10; 554 549 const double HEAD_LENGTH_FACTOR = 0.1; … … 579 574 // Extend the list 580 575 int cnt = _block_size; 581 int last_arc = 0;582 576 int limit = _head_length; 583 577 584 for ( inte = _next_arc; e < _search_arc_num; ++e) {578 for (e = _next_arc; e < _search_arc_num; ++e) { 585 579 _cand_cost[e] = _state[e] * 586 580 (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 587 581 if (_cand_cost[e] < 0) { 588 582 _candidates[_curr_length++] = e; 589 last_arc = e;590 583 } 591 584 if (cnt == 0) { 592 if (_curr_length > limit) break;585 if (_curr_length > limit) goto search_end; 593 586 limit = 0; 594 587 cnt = _block_size; 595 588 } 596 589 } 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 } 590 for (e = 0; e < _next_arc; ++e) { 591 _cand_cost[e] = _state[e] * 592 (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 593 if (_cand_cost[e] < 0) { 594 _candidates[_curr_length++] = e; 595 } 596 if (cnt == 0) { 597 if (_curr_length > limit) goto search_end; 598 limit = 0; 599 cnt = _block_size; 610 600 } 611 601 } 612 602 if (_curr_length == 0) return false; 613 _next_arc = last_arc + 1; 603 604 search_end: 614 605 615 606 // Make heap of the candidate list (approximating a partial sort) … … 619 610 // Pop the first element of the heap 620 611 _in_arc = _candidates[0]; 612 _next_arc = e; 621 613 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, 622 614 _sort_func );
Note: See TracChangeset
for help on using the changeset viewer.