Changeset 2444:06f3702bf18d in lemon0.x
 Timestamp:
 05/11/07 18:03:20 (13 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3281
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r2440 r2444 31 31 32 32 /// \brief The pivot rule used in the algorithm. 33 #define EDGE_BLOCK_PIVOT34 33 //#define FIRST_ELIGIBLE_PIVOT 35 34 //#define BEST_ELIGIBLE_PIVOT 35 #define EDGE_BLOCK_PIVOT 36 36 //#define CANDIDATE_LIST_PIVOT 37 37 //#define SORTED_LIST_PIVOT 38 39 //#define _DEBUG_ITER_ 40 38 41 39 42 /// \brief State constant for edges at their lower bounds. … … 46 49 #ifdef EDGE_BLOCK_PIVOT 47 50 /// \brief Number of blocks for the "Edge Block" pivot rule. 48 #define BLOCK_NUM 100 49 /// \brief Lower bound for the number of edges to use "Edge Block" 50 // pivot rule instead of "First Eligible" pivot rule. 51 #define MIN_BOUND 1000 51 #define BLOCK_NUM 100 52 /// \brief Lower bound for the size of blocks. 53 #define MIN_BLOCK_SIZE 10 52 54 #endif 53 55 … … 56 58 /// \brief The maximum length of the edge list for the 57 59 /// "Candidate List" pivot rule. 58 #define LIST_LENGTH 60 #define LIST_LENGTH 100 59 61 /// \brief The maximum number of minor iterations between two major 60 62 /// itarations. 61 #define MINOR_LIMIT 5063 #define MINOR_LIMIT 10 62 64 #endif 63 65 … … 67 69 /// \brief The maximum length of the edge list for the 68 70 /// "Sorted List" pivot rule. 69 #define LIST_LENGTH 500 70 #define LOWER_DIV 4 71 #endif 72 73 //#define _DEBUG_ITER_ 71 #define LIST_LENGTH 500 72 #define LOWER_DIV 3 73 #endif 74 74 75 75 namespace lemon { … … 514 514 // Initializing block_size for the edge block pivot rule 515 515 int edge_num = countEdges(graph); 516 block_size = edge_num > MIN_BOUND ? edge_num / BLOCK_NUM + 1 : 1; 516 block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ? 517 edge_num / BLOCK_NUM : MIN_BLOCK_SIZE; 517 518 #endif 518 519 #ifdef CANDIDATE_LIST_PIVOT … … 564 565 /// pivot rule. 565 566 bool findEnteringEdge(EdgeIt &next_edge) { 566 if (block_size == 1) { 567 // Performing first eligible selection 568 for (EdgeIt e = next_edge; e != INVALID; ++e) { 569 if (state[e] * red_cost[e] < 0) { 570 in_edge = e; 571 next_edge = ++e; 572 return true; 573 } 574 } 567 // Performing edge block selection 568 Cost curr, min = 0; 569 EdgeIt min_edge(graph); 570 int cnt = 0; 571 for (EdgeIt e = next_edge; e != INVALID; ++e) { 572 if ((curr = state[e] * red_cost[e]) < min) { 573 min = curr; 574 min_edge = e; 575 } 576 if (++cnt == block_size) { 577 if (min < 0) break; 578 cnt = 0; 579 } 580 } 581 if (!(min < 0)) { 575 582 for (EdgeIt e(graph); e != next_edge; ++e) { 576 if (state[e] * red_cost[e] < 0) {577 in_edge = e;578 next_edge = ++e;579 return true;580 }581 }582 return false;583 } else {584 // Performing edge block selection585 Cost curr, min = 0;586 EdgeIt min_edge(graph);587 int cnt = 0;588 for (EdgeIt e = next_edge; e != INVALID; ++e) {589 583 if ((curr = state[e] * red_cost[e]) < min) { 590 584 min = curr; … … 596 590 } 597 591 } 598 if (!(min < 0)) { 599 for (EdgeIt e(graph); e != next_edge; ++e) { 600 if ((curr = state[e] * red_cost[e]) < min) { 601 min = curr; 602 min_edge = e; 603 } 604 if (++cnt == block_size) { 605 if (min < 0) break; 606 cnt = 0; 607 } 608 } 609 } 610 in_edge = min_edge; 611 if ((next_edge = ++min_edge) == INVALID) 612 next_edge = EdgeIt(graph); 613 return min < 0; 614 } 592 } 593 in_edge = min_edge; 594 if ((next_edge = ++min_edge) == INVALID) 595 next_edge = EdgeIt(graph); 596 return min < 0; 615 597 } 616 598 #endif … … 697 679 candidates.push_back(e); 698 680 if (curr < min) min = curr; 699 if (candidates.size() >= LIST_LENGTH) break;681 if (candidates.size() == LIST_LENGTH) break; 700 682 } 701 683 } 702 684 if (candidates.size() == 0) return false; 703 685 sort(candidates.begin(), candidates.end(), sort_func); 686 in_edge = candidates.front(); 687 candidates.pop_front(); 704 688 return true; 705 689 } … … 910 894 911 895 #ifdef _DEBUG_ITER_ 912 t_iter.stop();913 896 std::cout << "Network Simplex algorithm finished. " << iter_num 914 << " pivot iterations performed." ;897 << " pivot iterations performed." << std::endl; 915 898 #endif 916 899
Note: See TracChangeset
for help on using the changeset viewer.