Changes in lemon/network_simplex.h [777:4a45c8808b33:776:be48a648d28f] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/network_simplex.h
r777 r776 363 363 Cost c, min = 0; 364 364 int cnt = _block_size; 365 int e ;365 int e, min_arc = _next_arc; 366 366 for (e = _next_arc; e < _search_arc_num; ++e) { 367 367 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 368 368 if (c < min) { 369 369 min = c; 370 _in_arc = e;370 min_arc = e; 371 371 } 372 372 if (--cnt == 0) { 373 if (min < 0) goto search_end;373 if (min < 0) break; 374 374 cnt = _block_size; 375 375 } 376 376 } 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; 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 } 386 388 } 387 389 } 388 390 if (min >= 0) return false; 389 390 search_end: 391 _in_arc = min_arc; 391 392 _next_arc = e; 392 393 return true; … … 426 427 { 427 428 // The main parameters of the pivot rule 428 const double LIST_LENGTH_FACTOR = 0.25;429 const double LIST_LENGTH_FACTOR = 1.0; 429 430 const int MIN_LIST_LENGTH = 10; 430 431 const double MINOR_LIMIT_FACTOR = 0.1; … … 443 444 bool findEnteringArc() { 444 445 Cost min, c; 445 int e ;446 int e, min_arc = _next_arc; 446 447 if (_curr_length > 0 && _minor_count < _minor_limit) { 447 448 // Minor iteration: select the best eligible arc from the … … 454 455 if (c < min) { 455 456 min = c; 456 _in_arc = e;457 min_arc = e; 457 458 } 458 elseif (c >= 0) {459 if (c >= 0) { 459 460 _candidates[i--] = _candidates[--_curr_length]; 460 461 } 461 462 } 462 if (min < 0) return true; 463 if (min < 0) { 464 _in_arc = min_arc; 465 return true; 466 } 463 467 } 464 468 … … 472 476 if (c < min) { 473 477 min = c; 474 _in_arc = e;478 min_arc = e; 475 479 } 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; 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; 486 493 } 487 if (_curr_length == _list_length) goto search_end;488 494 } 489 495 } 490 496 if (_curr_length == 0) return false; 491 492 search_end:493 497 _minor_count = 1; 498 _in_arc = min_arc; 494 499 _next_arc = e; 495 500 return true; … … 543 548 { 544 549 // The main parameters of the pivot rule 545 const double BLOCK_SIZE_FACTOR = 1. 0;550 const double BLOCK_SIZE_FACTOR = 1.5; 546 551 const int MIN_BLOCK_SIZE = 10; 547 552 const double HEAD_LENGTH_FACTOR = 0.1; … … 572 577 // Extend the list 573 578 int cnt = _block_size; 579 int last_arc = 0; 574 580 int limit = _head_length; 575 581 576 for ( e = _next_arc; e < _search_arc_num; ++e) {582 for (int e = _next_arc; e < _search_arc_num; ++e) { 577 583 _cand_cost[e] = _state[e] * 578 584 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 579 585 if (_cand_cost[e] < 0) { 580 586 _candidates[_curr_length++] = e; 587 last_arc = e; 581 588 } 582 589 if (--cnt == 0) { 583 if (_curr_length > limit) goto search_end;590 if (_curr_length > limit) break; 584 591 limit = 0; 585 592 cnt = _block_size; 586 593 } 587 594 } 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; 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 } 598 608 } 599 609 } 600 610 if (_curr_length == 0) return false; 601 602 search_end: 611 _next_arc = last_arc + 1; 603 612 604 613 // Make heap of the candidate list (approximating a partial sort) … … 608 617 // Pop the first element of the heap 609 618 _in_arc = _candidates[0]; 610 _next_arc = e;611 619 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, 612 620 _sort_func ); … … 624 632 /// 625 633 /// \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) : 634 NetworkSimplex(const GR& graph) : 631 635 _graph(graph), _node_id(graph), _arc_id(graph), 632 636 INF(std::numeric_limits<Value>::has_infinity ? … … 666 670 _state.resize(max_arc_num); 667 671 668 // Copy the graph 672 // Copy the graph (store the arcs in a mixed order) 669 673 int i = 0; 670 674 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 671 675 _node_id[n] = i; 672 676 } 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 } 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; 691 684 } 692 685
Note: See TracChangeset
for help on using the changeset viewer.