45 #define TREE 0 |
45 #define TREE 0 |
46 /// \brief State constant for edges at their upper bounds. |
46 /// \brief State constant for edges at their upper bounds. |
47 #define UPPER -1 |
47 #define UPPER -1 |
48 |
48 |
49 #ifdef EDGE_BLOCK_PIVOT |
49 #ifdef EDGE_BLOCK_PIVOT |
50 /// \brief Number of blocks for the "Edge Block" pivot rule. |
50 #include <cmath> |
51 #define BLOCK_NUM 100 |
|
52 /// \brief Lower bound for the size of blocks. |
51 /// \brief Lower bound for the size of blocks. |
53 #define MIN_BLOCK_SIZE 10 |
52 #define MIN_BLOCK_SIZE 10 |
54 #endif |
53 #endif |
55 |
54 |
56 #ifdef CANDIDATE_LIST_PIVOT |
55 #ifdef CANDIDATE_LIST_PIVOT |
57 #include <list> |
56 #include <vector> |
58 /// \brief The maximum length of the edge list for the |
57 #define LIST_LENGTH_DIV 50 |
59 /// "Candidate List" pivot rule. |
58 #define MINOR_LIMIT_DIV 200 |
60 #define LIST_LENGTH 100 |
|
61 /// \brief The maximum number of minor iterations between two major |
|
62 /// itarations. |
|
63 #define MINOR_LIMIT 10 |
|
64 #endif |
59 #endif |
65 |
60 |
66 #ifdef SORTED_LIST_PIVOT |
61 #ifdef SORTED_LIST_PIVOT |
67 #include <deque> |
62 #include <vector> |
68 #include <algorithm> |
63 #include <algorithm> |
69 /// \brief The maximum length of the edge list for the |
64 #define LIST_LENGTH_DIV 100 |
70 /// "Sorted List" pivot rule. |
65 #define LOWER_DIV 4 |
71 #define LIST_LENGTH 500 |
|
72 #define LOWER_DIV 3 |
|
73 #endif |
66 #endif |
74 |
67 |
75 namespace lemon { |
68 namespace lemon { |
76 |
69 |
77 /// \addtogroup min_cost_flow |
70 /// \addtogroup min_cost_flow |
221 int block_size; |
214 int block_size; |
222 #endif |
215 #endif |
223 #ifdef CANDIDATE_LIST_PIVOT |
216 #ifdef CANDIDATE_LIST_PIVOT |
224 /// \brief The list of candidate edges for the "Candidate List" |
217 /// \brief The list of candidate edges for the "Candidate List" |
225 /// pivot rule. |
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 /// \brief The number of minor iterations. |
226 /// \brief The number of minor iterations. |
228 int minor_count; |
227 int minor_count; |
229 #endif |
228 #endif |
230 #ifdef SORTED_LIST_PIVOT |
229 #ifdef SORTED_LIST_PIVOT |
231 /// \brief The list of candidate edges for the "Sorted List" |
230 /// \brief The list of candidate edges for the "Sorted List" |
232 /// pivot rule. |
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 #endif |
237 #endif |
235 |
238 |
236 // Root node of the starting spanning tree. |
239 // Root node of the starting spanning tree. |
237 Node root; |
240 Node root; |
238 // The entering edge of the current pivot iteration. |
241 // The entering edge of the current pivot iteration. |
515 thread[last] = root; |
518 thread[last] = root; |
516 |
519 |
517 #ifdef EDGE_BLOCK_PIVOT |
520 #ifdef EDGE_BLOCK_PIVOT |
518 // Initializing block_size for the edge block pivot rule |
521 // Initializing block_size for the edge block pivot rule |
519 int edge_num = countEdges(graph); |
522 int edge_num = countEdges(graph); |
520 block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ? |
523 block_size = 2 * int(sqrt(countEdges(graph))); |
521 edge_num / BLOCK_NUM : MIN_BLOCK_SIZE; |
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 #endif |
527 #endif |
523 #ifdef CANDIDATE_LIST_PIVOT |
528 #ifdef CANDIDATE_LIST_PIVOT |
|
529 int edge_num = countEdges(graph); |
524 minor_count = 0; |
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 #endif |
538 #endif |
526 |
539 |
527 return sum == 0; |
540 return sum == 0; |
528 } |
541 } |
529 |
542 |
600 return min < 0; |
613 return min < 0; |
601 } |
614 } |
602 #endif |
615 #endif |
603 |
616 |
604 #ifdef CANDIDATE_LIST_PIVOT |
617 #ifdef CANDIDATE_LIST_PIVOT |
605 /// \brief Functor class for removing non-eligible edges from the |
|
606 /// candidate list. |
|
607 class RemoveFunc |
|
608 { |
|
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 /// \brief Finds entering edge according to the "Candidate List" |
618 /// \brief Finds entering edge according to the "Candidate List" |
621 /// pivot rule. |
619 /// pivot rule. |
622 bool findEnteringEdge() { |
620 bool findEnteringEdge() { |
623 static RemoveFunc remove_func(state, red_cost); |
621 typedef typename std::vector<Edge>::iterator ListIt; |
624 typedef typename std::list<Edge>::iterator ListIt; |
622 |
625 |
623 if (minor_count >= minor_limit || candidates.size() == 0) { |
626 candidates.remove_if(remove_func); |
|
627 if (minor_count >= MINOR_LIMIT || candidates.size() == 0) { |
|
628 // Major iteration |
624 // Major iteration |
|
625 candidates.clear(); |
629 for (EdgeIt e(graph); e != INVALID; ++e) { |
626 for (EdgeIt e(graph); e != INVALID; ++e) { |
630 if (state[e] * red_cost[e] < 0) { |
627 if (state[e] * red_cost[e] < 0) { |
631 candidates.push_back(e); |
628 candidates.push_back(e); |
632 if (candidates.size() == LIST_LENGTH) break; |
629 if (candidates.size() == list_length) break; |
633 } |
630 } |
634 } |
631 } |
635 if (candidates.size() == 0) return false; |
632 if (candidates.size() == 0) return false; |
636 } |
633 } |
637 |
634 |
638 // Minor iteration |
635 // Minor iteration |
639 ++minor_count; |
636 ++minor_count; |
640 Cost min = 0; |
637 Cost min = 0; |
641 for (ListIt it = candidates.begin(); it != candidates.end(); ++it) { |
638 Edge e; |
642 if (state[*it] * red_cost[*it] < min) { |
639 for (int i = 0; i < candidates.size(); ++i) { |
643 min = state[*it] * red_cost[*it]; |
640 e = candidates[i]; |
644 in_edge = *it; |
641 if (state[e] * red_cost[e] < min) { |
|
642 min = state[e] * red_cost[e]; |
|
643 in_edge = e; |
645 } |
644 } |
646 } |
645 } |
647 return true; |
646 return true; |
648 } |
647 } |
649 #endif |
648 #endif |
668 /// pivot rule. |
667 /// pivot rule. |
669 bool findEnteringEdge() { |
668 bool findEnteringEdge() { |
670 static SortFunc sort_func(state, red_cost); |
669 static SortFunc sort_func(state, red_cost); |
671 |
670 |
672 // Minor iteration |
671 // Minor iteration |
673 while (candidates.size() > 0) { |
672 while (list_index < candidates.size()) { |
674 in_edge = candidates.front(); |
673 in_edge = candidates[list_index++]; |
675 candidates.pop_front(); |
|
676 if (state[in_edge] * red_cost[in_edge] < 0) return true; |
674 if (state[in_edge] * red_cost[in_edge] < 0) return true; |
677 } |
675 } |
678 |
676 |
679 // Major iteration |
677 // Major iteration |
|
678 candidates.clear(); |
680 Cost curr, min = 0; |
679 Cost curr, min = 0; |
681 for (EdgeIt e(graph); e != INVALID; ++e) { |
680 for (EdgeIt e(graph); e != INVALID; ++e) { |
682 if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) { |
681 if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) { |
683 candidates.push_back(e); |
682 candidates.push_back(e); |
684 if (curr < min) min = curr; |
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 if (candidates.size() == 0) return false; |
687 if (candidates.size() == 0) return false; |
689 sort(candidates.begin(), candidates.end(), sort_func); |
688 sort(candidates.begin(), candidates.end(), sort_func); |
690 in_edge = candidates.front(); |
689 in_edge = candidates[0]; |
691 candidates.pop_front(); |
690 list_index = 1; |
692 return true; |
691 return true; |
693 } |
692 } |
694 #endif |
693 #endif |
695 |
694 |
696 /// \brief Finds the join node. |
695 /// \brief Finds the join node. |