Changeset 2471:ed70b226cc48 in lemon-0.x
- Timestamp:
- 09/14/07 00:06:54 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3309
- Location:
- lemon
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r2457 r2471 31 31 32 32 #define WITH_SCALING 33 34 #ifdef WITH_SCALING 35 #define SCALING_FACTOR 2 36 #endif 33 37 34 38 //#define _DEBUG_ITER_ … … 543 547 } 544 548 if (max_dem < max_sup) max_sup = max_dem; 545 for (delta = 1; 2 * delta < max_sup; delta *= 2) ; 549 for ( delta = 1; SCALING_FACTOR * delta < max_sup; 550 delta *= SCALING_FACTOR ) ; 546 551 #endif 547 552 return true; … … 560 565 // Processing capacity scaling phases 561 566 ResNode s, t; 562 for ( ; delta >= 1; delta = delta < 4&& delta > 1 ?563 1 : delta / 4)567 for ( ; delta >= 1; delta = delta < SCALING_FACTOR && delta > 1 ? 568 1 : delta / SCALING_FACTOR ) 564 569 { 565 570 // Saturating edges not satisfying the optimality condition -
lemon/network_simplex.h
r2457 r2471 48 48 49 49 #ifdef EDGE_BLOCK_PIVOT 50 /// \brief Number of blocks for the "Edge Block" pivot rule. 51 #define BLOCK_NUM 100 50 #include <cmath> 52 51 /// \brief Lower bound for the size of blocks. 53 52 #define MIN_BLOCK_SIZE 10 … … 55 54 56 55 #ifdef CANDIDATE_LIST_PIVOT 57 #include <list> 58 /// \brief The maximum length of the edge list for the 59 /// "Candidate List" pivot rule. 60 #define LIST_LENGTH 100 61 /// \brief The maximum number of minor iterations between two major 62 /// itarations. 63 #define MINOR_LIMIT 10 56 #include <vector> 57 #define LIST_LENGTH_DIV 50 58 #define MINOR_LIMIT_DIV 200 64 59 #endif 65 60 66 61 #ifdef SORTED_LIST_PIVOT 67 #include < deque>62 #include <vector> 68 63 #include <algorithm> 69 /// \brief The maximum length of the edge list for the 70 /// "Sorted List" pivot rule. 71 #define LIST_LENGTH 500 72 #define LOWER_DIV 3 64 #define LIST_LENGTH_DIV 100 65 #define LOWER_DIV 4 73 66 #endif 74 67 … … 224 217 /// \brief The list of candidate edges for the "Candidate List" 225 218 /// pivot rule. 226 std::list<Edge> candidates; 219 std::vector<Edge> candidates; 220 /// \brief The maximum length of the edge list for the 221 /// "Candidate List" pivot rule. 222 int list_length; 223 /// \brief The maximum number of minor iterations between two major 224 /// itarations. 225 int minor_limit; 227 226 /// \brief The number of minor iterations. 228 227 int minor_count; … … 231 230 /// \brief The list of candidate edges for the "Sorted List" 232 231 /// pivot rule. 233 std::deque<Edge> candidates; 232 std::vector<Edge> candidates; 233 /// \brief The maximum length of the edge list for the 234 /// "Sorted List" pivot rule. 235 int list_length; 236 int list_index; 234 237 #endif 235 238 … … 518 521 // Initializing block_size for the edge block pivot rule 519 522 int edge_num = countEdges(graph); 520 block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ? 521 edge_num / BLOCK_NUM : MIN_BLOCK_SIZE; 523 block_size = 2 * int(sqrt(countEdges(graph))); 524 if (block_size < MIN_BLOCK_SIZE) block_size = MIN_BLOCK_SIZE; 525 // block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ? 526 // edge_num / BLOCK_NUM : MIN_BLOCK_SIZE; 522 527 #endif 523 528 #ifdef CANDIDATE_LIST_PIVOT 529 int edge_num = countEdges(graph); 524 530 minor_count = 0; 531 list_length = edge_num / LIST_LENGTH_DIV; 532 minor_limit = edge_num / MINOR_LIMIT_DIV; 533 #endif 534 #ifdef SORTED_LIST_PIVOT 535 int edge_num = countEdges(graph); 536 list_index = 0; 537 list_length = edge_num / LIST_LENGTH_DIV; 525 538 #endif 526 539 … … 603 616 604 617 #ifdef CANDIDATE_LIST_PIVOT 605 /// \brief Functor class for removing non-eligible edges from the606 /// candidate list.607 class RemoveFunc608 {609 private:610 const IntEdgeMap &st;611 const ReducedCostMap &rc;612 public:613 RemoveFunc(const IntEdgeMap &_st, const ReducedCostMap &_rc) :614 st(_st), rc(_rc) {}615 bool operator()(const Edge &e) {616 return st[e] * rc[e] >= 0;617 }618 };619 620 618 /// \brief Finds entering edge according to the "Candidate List" 621 619 /// pivot rule. 622 620 bool findEnteringEdge() { 623 static RemoveFunc remove_func(state, red_cost); 624 typedef typename std::list<Edge>::iterator ListIt; 625 626 candidates.remove_if(remove_func); 627 if (minor_count >= MINOR_LIMIT || candidates.size() == 0) { 621 typedef typename std::vector<Edge>::iterator ListIt; 622 623 if (minor_count >= minor_limit || candidates.size() == 0) { 628 624 // Major iteration 625 candidates.clear(); 629 626 for (EdgeIt e(graph); e != INVALID; ++e) { 630 627 if (state[e] * red_cost[e] < 0) { 631 628 candidates.push_back(e); 632 if (candidates.size() == LIST_LENGTH) break;629 if (candidates.size() == list_length) break; 633 630 } 634 631 } … … 639 636 ++minor_count; 640 637 Cost min = 0; 641 for (ListIt it = candidates.begin(); it != candidates.end(); ++it) { 642 if (state[*it] * red_cost[*it] < min) { 643 min = state[*it] * red_cost[*it]; 644 in_edge = *it; 638 Edge e; 639 for (int i = 0; i < candidates.size(); ++i) { 640 e = candidates[i]; 641 if (state[e] * red_cost[e] < min) { 642 min = state[e] * red_cost[e]; 643 in_edge = e; 645 644 } 646 645 } … … 671 670 672 671 // Minor iteration 673 while (candidates.size() > 0) { 674 in_edge = candidates.front(); 675 candidates.pop_front(); 672 while (list_index < candidates.size()) { 673 in_edge = candidates[list_index++]; 676 674 if (state[in_edge] * red_cost[in_edge] < 0) return true; 677 675 } 678 676 679 677 // Major iteration 678 candidates.clear(); 680 679 Cost curr, min = 0; 681 680 for (EdgeIt e(graph); e != INVALID; ++e) { … … 683 682 candidates.push_back(e); 684 683 if (curr < min) min = curr; 685 if (candidates.size() == LIST_LENGTH) break;684 if (candidates.size() == list_length) break; 686 685 } 687 686 } 688 687 if (candidates.size() == 0) return false; 689 688 sort(candidates.begin(), candidates.end(), sort_func); 690 in_edge = candidates .front();691 candidates.pop_front();689 in_edge = candidates[0]; 690 list_index = 1; 692 691 return true; 693 692 }
Note: See TracChangeset
for help on using the changeset viewer.