Changes in lemon/network_simplex.h [663:8b0df68370a4:755:134852d7fb0a] in lemon-main
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/network_simplex.h
r663 r755 41 41 /// 42 42 /// \ref NetworkSimplex implements the primal Network Simplex algorithm 43 /// for finding a \ref min_cost_flow "minimum cost flow". 43 /// for finding a \ref min_cost_flow "minimum cost flow" 44 /// \ref amo93networkflows, \ref dantzig63linearprog, 45 /// \ref kellyoneill91netsimplex. 44 46 /// This algorithm is a specialized version of the linear programming 45 47 /// simplex method directly for the minimum cost flow problem. … … 162 164 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 163 165 164 typedef std::vector<Arc> ArcVector;165 typedef std::vector<Node> NodeVector;166 166 typedef std::vector<int> IntVector; 167 167 typedef std::vector<bool> BoolVector; … … 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 ); … … 634 626 /// 635 627 /// \param graph The digraph the algorithm runs on. 636 NetworkSimplex(const GR& graph) : 628 /// \param arc_mixing Indicate if the arcs have to be stored in a 629 /// mixed order in the internal data structure. 630 /// In special cases, it could lead to better overall performance, 631 /// but it is usually slower. Therefore it is disabled by default. 632 NetworkSimplex(const GR& graph, bool arc_mixing = false) : 637 633 _graph(graph), _node_id(graph), _arc_id(graph), 638 634 INF(std::numeric_limits<Value>::has_infinity ? … … 672 668 _state.resize(max_arc_num); 673 669 674 // Copy the graph (store the arcs in a mixed order)670 // Copy the graph 675 671 int i = 0; 676 672 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 677 673 _node_id[n] = i; 678 674 } 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; 675 if (arc_mixing) { 676 // Store the arcs in a mixed order 677 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 678 int i = 0, j = 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 = ++j; 684 } 685 } else { 686 // Store the arcs in the original order 687 int i = 0; 688 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 689 _arc_id[a] = i; 690 _source[i] = _node_id[_graph.source(a)]; 691 _target[i] = _node_id[_graph.target(a)]; 692 } 686 693 } 687 694 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; 695 // Reset parameters 696 reset(); 699 697 } 700 698 … … 769 767 /// If neither this function nor \ref stSupply() is used before 770 768 /// 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 769 /// 773 770 /// \param map A node map storing the supply values. … … 790 787 /// If neither this function nor \ref supplyMap() is used before 791 788 /// 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 789 /// 794 790 /// Using this function has the same effect as using \ref supplyMap()
Note: See TracChangeset
for help on using the changeset viewer.