Changes in / [726:3fc2a801c39e:731:0977046c60d2] in lemon-main
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/network_simplex.h
r663 r730 162 162 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 163 163 164 typedef std::vector<Arc> ArcVector;165 typedef std::vector<Node> NodeVector;166 164 typedef std::vector<int> IntVector; 167 165 typedef std::vector<bool> BoolVector; … … 365 363 Cost c, min = 0; 366 364 int cnt = _block_size; 367 int e , min_arc = _next_arc;365 int e; 368 366 for (e = _next_arc; e < _search_arc_num; ++e) { 369 367 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 370 368 if (c < min) { 371 369 min = c; 372 min_arc = e;370 _in_arc = e; 373 371 } 374 372 if (--cnt == 0) { 375 if (min < 0) break;373 if (min < 0) goto search_end; 376 374 cnt = _block_size; 377 375 } 378 376 } 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 } 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; 390 386 } 391 387 } 392 388 if (min >= 0) return false; 393 _in_arc = min_arc; 389 390 search_end: 394 391 _next_arc = e; 395 392 return true; … … 429 426 { 430 427 // The main parameters of the pivot rule 431 const double LIST_LENGTH_FACTOR = 1.0;428 const double LIST_LENGTH_FACTOR = 0.25; 432 429 const int MIN_LIST_LENGTH = 10; 433 430 const double MINOR_LIMIT_FACTOR = 0.1; … … 446 443 bool findEnteringArc() { 447 444 Cost min, c; 448 int e , min_arc = _next_arc;445 int e; 449 446 if (_curr_length > 0 && _minor_count < _minor_limit) { 450 447 // Minor iteration: select the best eligible arc from the … … 457 454 if (c < min) { 458 455 min = c; 459 min_arc = e;456 _in_arc = e; 460 457 } 461 if (c >= 0) {458 else if (c >= 0) { 462 459 _candidates[i--] = _candidates[--_curr_length]; 463 460 } 464 461 } 465 if (min < 0) { 466 _in_arc = min_arc; 467 return true; 468 } 462 if (min < 0) return true; 469 463 } 470 464 … … 478 472 if (c < min) { 479 473 min = c; 480 min_arc = e;474 _in_arc = e; 481 475 } 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; 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; 495 486 } 487 if (_curr_length == _list_length) goto search_end; 496 488 } 497 489 } 498 490 if (_curr_length == 0) return false; 491 492 search_end: 499 493 _minor_count = 1; 500 _in_arc = min_arc;501 494 _next_arc = e; 502 495 return true; … … 550 543 { 551 544 // The main parameters of the pivot rule 552 const double BLOCK_SIZE_FACTOR = 1. 5;545 const double BLOCK_SIZE_FACTOR = 1.0; 553 546 const int MIN_BLOCK_SIZE = 10; 554 547 const double HEAD_LENGTH_FACTOR = 0.1; … … 579 572 // Extend the list 580 573 int cnt = _block_size; 581 int last_arc = 0;582 574 int limit = _head_length; 583 575 584 for ( inte = _next_arc; e < _search_arc_num; ++e) {576 for (e = _next_arc; e < _search_arc_num; ++e) { 585 577 _cand_cost[e] = _state[e] * 586 578 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 587 579 if (_cand_cost[e] < 0) { 588 580 _candidates[_curr_length++] = e; 589 last_arc = e;590 581 } 591 582 if (--cnt == 0) { 592 if (_curr_length > limit) break;583 if (_curr_length > limit) goto search_end; 593 584 limit = 0; 594 585 cnt = _block_size; 595 586 } 596 587 } 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 } 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; 610 598 } 611 599 } 612 600 if (_curr_length == 0) return false; 613 _next_arc = last_arc + 1; 601 602 search_end: 614 603 615 604 // Make heap of the candidate list (approximating a partial sort) … … 619 608 // Pop the first element of the heap 620 609 _in_arc = _candidates[0]; 610 _next_arc = e; 621 611 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, 622 612 _sort_func ); … … 634 624 /// 635 625 /// \param graph The digraph the algorithm runs on. 636 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) : 637 631 _graph(graph), _node_id(graph), _arc_id(graph), 638 632 INF(std::numeric_limits<Value>::has_infinity ? … … 672 666 _state.resize(max_arc_num); 673 667 674 // Copy the graph (store the arcs in a mixed order)668 // Copy the graph 675 669 int i = 0; 676 670 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 677 671 _node_id[n] = i; 678 672 } 679 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 680 i = 0; 681 for (ArcIt a(_graph); a != INVALID; ++a) { 682 _arc_id[a] = i; 683 _source[i] = _node_id[_graph.source(a)]; 684 _target[i] = _node_id[_graph.target(a)]; 685 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 } 686 691 } 687 692 688 // Initialize maps 689 for (int i = 0; i != _node_num; ++i) { 690 _supply[i] = 0; 691 } 692 for (int i = 0; i != _arc_num; ++i) { 693 _lower[i] = 0; 694 _upper[i] = INF; 695 _cost[i] = 1; 696 } 697 _have_lower = false; 698 _stype = GEQ; 693 // Reset parameters 694 reset(); 699 695 } 700 696 … … 769 765 /// If neither this function nor \ref stSupply() is used before 770 766 /// calling \ref run(), the supply of each node will be set to zero. 771 /// (It makes sense only if non-zero lower bounds are given.)772 767 /// 773 768 /// \param map A node map storing the supply values. … … 790 785 /// If neither this function nor \ref supplyMap() is used before 791 786 /// calling \ref run(), the supply of each node will be set to zero. 792 /// (It makes sense only if non-zero lower bounds are given.)793 787 /// 794 788 /// Using this function has the same effect as using \ref supplyMap()
Note: See TracChangeset
for help on using the changeset viewer.