Changeset 777:4a45c8808b33 in lemon for lemon/network_simplex.h
 Timestamp:
 09/26/09 07:16:22 (12 years ago)
 Branch:
 default
 Parents:
 776:be48a648d28f (diff), 775:e2bdd1a988f3 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r775 r777 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; … … 693 691 } 694 692 695 // Initialize maps 696 for (int i = 0; i != _node_num; ++i) { 697 _supply[i] = 0; 698 } 699 for (int i = 0; i != _arc_num; ++i) { 700 _lower[i] = 0; 701 _upper[i] = INF; 702 _cost[i] = 1; 703 } 704 _have_lower = false; 705 _stype = GEQ; 693 // Reset parameters 694 reset(); 706 695 } 707 696 … … 776 765 /// If neither this function nor \ref stSupply() is used before 777 766 /// calling \ref run(), the supply of each node will be set to zero. 778 /// (It makes sense only if nonzero lower bounds are given.)779 767 /// 780 768 /// \param map A node map storing the supply values. … … 797 785 /// If neither this function nor \ref supplyMap() is used before 798 786 /// calling \ref run(), the supply of each node will be set to zero. 799 /// (It makes sense only if nonzero lower bounds are given.)800 787 /// 801 788 /// Using this function has the same effect as using \ref supplyMap() 
lemon/network_simplex.h
r776 r777 363 363 Cost c, min = 0; 364 364 int cnt = _block_size; 365 int e , min_arc = _next_arc;365 int e; 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 min_arc = e;370 _in_arc = e; 371 371 } 372 372 if (cnt == 0) { 373 if (min < 0) break;373 if (min < 0) goto search_end; 374 374 cnt = _block_size; 375 375 } 376 376 } 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 } 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; 388 386 } 389 387 } 390 388 if (min >= 0) return false; 391 _in_arc = min_arc; 389 390 search_end: 392 391 _next_arc = e; 393 392 return true; … … 427 426 { 428 427 // The main parameters of the pivot rule 429 const double LIST_LENGTH_FACTOR = 1.0;428 const double LIST_LENGTH_FACTOR = 0.25; 430 429 const int MIN_LIST_LENGTH = 10; 431 430 const double MINOR_LIMIT_FACTOR = 0.1; … … 444 443 bool findEnteringArc() { 445 444 Cost min, c; 446 int e , min_arc = _next_arc;445 int e; 447 446 if (_curr_length > 0 && _minor_count < _minor_limit) { 448 447 // Minor iteration: select the best eligible arc from the … … 455 454 if (c < min) { 456 455 min = c; 457 min_arc = e;456 _in_arc = e; 458 457 } 459 if (c >= 0) {458 else if (c >= 0) { 460 459 _candidates[i] = _candidates[_curr_length]; 461 460 } 462 461 } 463 if (min < 0) { 464 _in_arc = min_arc; 465 return true; 466 } 462 if (min < 0) return true; 467 463 } 468 464 … … 476 472 if (c < min) { 477 473 min = c; 478 min_arc = e;474 _in_arc = e; 479 475 } 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; 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; 493 486 } 487 if (_curr_length == _list_length) goto search_end; 494 488 } 495 489 } 496 490 if (_curr_length == 0) return false; 491 492 search_end: 497 493 _minor_count = 1; 498 _in_arc = min_arc;499 494 _next_arc = e; 500 495 return true; … … 548 543 { 549 544 // The main parameters of the pivot rule 550 const double BLOCK_SIZE_FACTOR = 1. 5;545 const double BLOCK_SIZE_FACTOR = 1.0; 551 546 const int MIN_BLOCK_SIZE = 10; 552 547 const double HEAD_LENGTH_FACTOR = 0.1; … … 577 572 // Extend the list 578 573 int cnt = _block_size; 579 int last_arc = 0;580 574 int limit = _head_length; 581 575 582 for ( inte = _next_arc; e < _search_arc_num; ++e) {576 for (e = _next_arc; e < _search_arc_num; ++e) { 583 577 _cand_cost[e] = _state[e] * 584 578 (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 585 579 if (_cand_cost[e] < 0) { 586 580 _candidates[_curr_length++] = e; 587 last_arc = e;588 581 } 589 582 if (cnt == 0) { 590 if (_curr_length > limit) break;583 if (_curr_length > limit) goto search_end; 591 584 limit = 0; 592 585 cnt = _block_size; 593 586 } 594 587 } 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 } 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; 608 598 } 609 599 } 610 600 if (_curr_length == 0) return false; 611 _next_arc = last_arc + 1; 601 602 search_end: 612 603 613 604 // Make heap of the candidate list (approximating a partial sort) … … 617 608 // Pop the first element of the heap 618 609 _in_arc = _candidates[0]; 610 _next_arc = e; 619 611 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, 620 612 _sort_func ); … … 632 624 /// 633 625 /// \param graph The digraph the algorithm runs on. 634 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) : 635 631 _graph(graph), _node_id(graph), _arc_id(graph), 636 632 INF(std::numeric_limits<Value>::has_infinity ? … … 670 666 _state.resize(max_arc_num); 671 667 672 // Copy the graph (store the arcs in a mixed order)668 // Copy the graph 673 669 int i = 0; 674 670 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 675 671 _node_id[n] = i; 676 672 } 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; 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 } 684 691 } 685 692
Note: See TracChangeset
for help on using the changeset viewer.