Changeset 2630:d239741cfd44 in lemon-0.x
- Timestamp:
- 11/13/08 17:17:50 (15 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3515
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/network_simplex.h
r2629 r2630 27 27 #include <vector> 28 28 #include <limits> 29 #include <algorithm> 29 30 30 31 #include <lemon/graph_adaptor.h> … … 138 139 Cost operator[](const Edge &e) const { 139 140 return _cost_map[e] + _pot_map[_gr.source(e)] 140 - _pot_map[_gr.target(e)];141 - _pot_map[_gr.target(e)]; 141 142 } 142 143 … … 169 170 170 171 /// Find next entering edge 171 inlinebool findEnteringEdge() {172 bool findEnteringEdge() { 172 173 Edge e; 173 174 for (int i = _next_edge; i < int(_edges.size()); ++i) { … … 213 214 214 215 /// Find next entering edge 215 inlinebool findEnteringEdge() {216 bool findEnteringEdge() { 216 217 Cost min = 0; 217 218 Edge e; … … 260 261 261 262 /// Find next entering edge 262 inlinebool findEnteringEdge() {263 bool findEnteringEdge() { 263 264 Cost curr, min = 0; 264 265 Edge e; … … 337 338 338 339 /// Find next entering edge 339 inlinebool findEnteringEdge() {340 bool findEnteringEdge() { 340 341 Cost min, curr; 341 342 if (_curr_length > 0 && _minor_count < _minor_limit) { 342 // Minor iteration: select ing the best eligible edge from343 // thecurrent candidate list343 // Minor iteration: select the best eligible edge from the 344 // current candidate list 344 345 ++_minor_count; 345 346 Edge e; … … 359 360 } 360 361 361 // Major iteration: build inga new candidate list362 // Major iteration: build a new candidate list 362 363 Edge e; 363 364 min = 0; … … 424 425 SortFunc(const SCostMap &map) : _map(map) {} 425 426 bool operator()(const Edge &e1, const Edge &e2) { 426 return _map[e1] <_map[e2];427 return _map[e1] > _map[e2]; 427 428 } 428 429 }; … … 438 439 { 439 440 // The main parameters of the pivot rule 440 const double BLOCK_SIZE_FACTOR = 1. 0;441 const double BLOCK_SIZE_FACTOR = 1.5; 441 442 const int MIN_BLOCK_SIZE = 10; 442 443 const double HEAD_LENGTH_FACTOR = 0.1; 443 const int MIN_HEAD_LENGTH = 5;444 const int MIN_HEAD_LENGTH = 3; 444 445 445 446 _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_edges.size())), … … 452 453 453 454 /// Find next entering edge 454 inlinebool findEnteringEdge() {455 // Check ingthe current candidate list455 bool findEnteringEdge() { 456 // Check the current candidate list 456 457 Edge e; 457 for (int i dx = 0; idx < _curr_length; ++idx) {458 e = _candidates[i dx];458 for (int ix = 0; ix < _curr_length; ++ix) { 459 e = _candidates[ix]; 459 460 if ((_cand_cost[e] = _ns._state[e] * _ns._red_cost[e]) >= 0) { 460 _candidates[i dx--] = _candidates[--_curr_length];461 } 462 } 463 464 // Extend ingthe list461 _candidates[ix--] = _candidates[--_curr_length]; 462 } 463 } 464 465 // Extend the list 465 466 int cnt = _block_size; 466 467 int last_edge = 0; … … 495 496 _next_edge = last_edge + 1; 496 497 497 // Sorting the list partially 498 EdgeVector::iterator sort_end = _candidates.begin(); 499 EdgeVector::iterator vector_end = _candidates.begin(); 500 for (int idx = 0; idx < _curr_length; ++idx) { 501 ++vector_end; 502 if (idx <= _head_length) ++sort_end; 503 } 504 partial_sort(_candidates.begin(), sort_end, vector_end, _sort_func); 505 498 // Make heap of the candidate list (approximating a partial sort) 499 make_heap( _candidates.begin(), _candidates.begin() + _curr_length, 500 _sort_func ); 501 502 // Pop the first element of the heap 506 503 _ns._in_edge = _candidates[0]; 507 if (_curr_length > _head_length) { 508 _candidates[0] = _candidates[_head_length - 1]; 509 _curr_length = _head_length - 1; 510 } else { 511 _candidates[0] = _candidates[_curr_length - 1]; 512 --_curr_length; 513 } 514 504 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, 505 _sort_func ); 506 _curr_length = std::min(_head_length, _curr_length - 1); 515 507 return true; 516 508 } … … 559 551 // The state edge map 560 552 IntEdgeMap _state; 561 // The root node of the starting spanning tree553 // The artificial root node of the spanning tree structure 562 554 Node _root; 563 555 … … 576 568 EdgeRefMap _edge_ref; 577 569 578 // The entering edge of the current pivot iteration .570 // The entering edge of the current pivot iteration 579 571 Edge _in_edge; 580 572 581 // Temporary nodes used in the current pivot iteration .573 // Temporary nodes used in the current pivot iteration 582 574 Node join, u_in, v_in, u_out, v_out; 583 575 Node right, first, second, last; 584 576 Node stem, par_stem, new_stem; 585 577 // The maximum augment amount along the found cycle in the current 586 // pivot iteration .578 // pivot iteration 587 579 Capacity delta; 588 580 … … 838 830 /// 839 831 /// According to our comprehensive benchmark tests the "Block Search" 840 /// pivot rule proved to be by far the fastest and the most robust841 /// onvarious test inputs. Thus it is the default option.832 /// pivot rule proved to be the fastest and the most robust on 833 /// various test inputs. Thus it is the default option. 842 834 /// 843 835 /// \return \c true if a feasible flow can be found. … … 912 904 private: 913 905 914 /// \brief Extend the underlying graph and initialize all the 915 /// node and edge maps. 906 // Extend the underlying graph and initialize all the node and edge maps 916 907 bool init() { 917 908 if (!_valid_supply) return false; 918 909 919 // Initializ ingresult maps910 // Initialize result maps 920 911 if (!_flow_result) { 921 912 _flow_result = new FlowMap(_graph_ref); … … 927 918 } 928 919 929 // Initializ ingthe edge vector and the edge maps920 // Initialize the edge vector and the edge maps 930 921 _edges.reserve(countEdges(_graph)); 931 922 for (EdgeIt e(_graph); e != INVALID; ++e) { … … 935 926 } 936 927 937 // Add ingan artificial root node to the graph928 // Add an artificial root node to the graph 938 929 _root = _graph.addNode(); 939 930 _parent[_root] = INVALID; … … 943 934 _potential[_root] = 0; 944 935 945 // Add ing artificial edges to the graph and initializing the node946 // mapsof the spanning tree data structure936 // Add artificial edges to the graph and initialize the node maps 937 // of the spanning tree data structure 947 938 Node last = _root; 948 939 Edge e; … … 975 966 } 976 967 977 // / Find the join node.978 inline NodefindJoinNode() {968 // Find the join node 969 void findJoinNode() { 979 970 Node u = _graph.source(_in_edge); 980 971 Node v = _graph.target(_in_edge); … … 987 978 else v = _parent[v]; 988 979 } 989 return u; 990 } 991 992 /// \brief Find the leaving edge of the cycle. 993 /// \return \c true if the leaving edge is not the same as the 994 /// entering edge. 995 inline bool findLeavingEdge() { 996 // Initializing first and second nodes according to the direction 980 join = u; 981 } 982 983 // Find the leaving edge of the cycle and returns true if the 984 // leaving edge is not the same as the entering edge 985 bool findLeavingEdge() { 986 // Initialize first and second nodes according to the direction 997 987 // of the cycle 998 988 if (_state[_in_edge] == STATE_LOWER) { … … 1008 998 Edge e; 1009 999 1010 // Searching the cycle along the path form the first node to the 1011 // root node 1000 // Search the cycle along the path form the first node to the root 1012 1001 for (Node u = first; u != join; u = _parent[u]) { 1013 1002 e = _pred_edge[u]; … … 1021 1010 } 1022 1011 } 1023 // Searching the cycle along the path form the second node to the 1024 // root node 1012 // Search the cycle along the path form the second node to the root 1025 1013 for (Node u = second; u != join; u = _parent[u]) { 1026 1014 e = _pred_edge[u]; … … 1037 1025 } 1038 1026 1039 // / Change \c flow and \c state edge maps.1040 inlinevoid changeFlows(bool change) {1041 // Augment ingalong the cycle1027 // Change _flow and _state edge maps 1028 void changeFlows(bool change) { 1029 // Augment along the cycle 1042 1030 if (delta > 0) { 1043 1031 Capacity val = _state[_in_edge] * delta; … … 1050 1038 } 1051 1039 } 1052 // Updat ingthe state of the entering and leaving edges1040 // Update the state of the entering and leaving edges 1053 1041 if (change) { 1054 1042 _state[_in_edge] = STATE_TREE; … … 1060 1048 } 1061 1049 1062 // / Update \c thread and \c parent node maps.1063 inlinevoid updateThreadParent() {1050 // Update _thread and _parent node maps 1051 void updateThreadParent() { 1064 1052 Node u; 1065 1053 v_out = _parent[u_out]; 1066 1054 1067 // Handl ingthe case when join and v_out coincide1055 // Handle the case when join and v_out coincide 1068 1056 bool par_first = false; 1069 1057 if (join == v_out) { … … 1076 1064 } 1077 1065 1078 // Find ing the last successor of u_in (u) and the node after it1079 // (right)according to the thread index1066 // Find the last successor of u_in (u) and the node after it (right) 1067 // according to the thread index 1080 1068 for (u = u_in; _depth[_thread[u]] > _depth[u_in]; u = _thread[u]) ; 1081 1069 right = _thread[u]; … … 1086 1074 else last = _thread[v_in]; 1087 1075 1088 // Updat ingstem nodes1076 // Update stem nodes 1089 1077 _thread[v_in] = stem = u_in; 1090 1078 par_stem = v_in; … … 1092 1080 _thread[u] = new_stem = _parent[stem]; 1093 1081 1094 // Find ingthe node just before the stem node (u) according to1082 // Find the node just before the stem node (u) according to 1095 1083 // the original thread index 1096 1084 for (u = new_stem; _thread[u] != stem; u = _thread[u]) ; 1097 1085 _thread[u] = right; 1098 1086 1099 // Changing the parent node of stem and shifting stem and 1100 // par_stem nodes 1087 // Change the parent node of stem and shift stem and par_stem nodes 1101 1088 _parent[stem] = par_stem; 1102 1089 par_stem = stem; 1103 1090 stem = new_stem; 1104 1091 1105 // Find ing the last successor of stem (u) and the node after it1106 // (right)according to the thread index1092 // Find the last successor of stem (u) and the node after it (right) 1093 // according to the thread index 1107 1094 for (u = stem; _depth[_thread[u]] > _depth[stem]; u = _thread[u]) ; 1108 1095 right = _thread[u]; … … 1119 1106 } 1120 1107 1121 // / Update \c pred_edge and \cforward node maps.1122 inlinevoid updatePredEdge() {1108 // Update _pred_edge and _forward node maps. 1109 void updatePredEdge() { 1123 1110 Node u = u_out, v; 1124 1111 while (u != u_in) { … … 1132 1119 } 1133 1120 1134 // / Update \c depth and \c potential node maps.1135 inlinevoid updateDepthPotential() {1121 // Update _depth and _potential node maps 1122 void updateDepthPotential() { 1136 1123 _depth[u_in] = _depth[v_in] + 1; 1137 1124 Cost sigma = _forward[u_in] ? … … 1146 1133 } 1147 1134 1148 // / Execute the algorithm.1135 // Execute the algorithm 1149 1136 bool start(PivotRuleEnum pivot_rule) { 1150 // Select ingthe pivot rule implementation1137 // Select the pivot rule implementation 1151 1138 switch (pivot_rule) { 1152 1139 case FIRST_ELIGIBLE_PIVOT: … … 1168 1155 PivotRuleImplementation pivot(*this, _edges); 1169 1156 1170 // Execut ingthe network simplex algorithm1157 // Execute the network simplex algorithm 1171 1158 while (pivot.findEnteringEdge()) { 1172 join =findJoinNode();1159 findJoinNode(); 1173 1160 bool change = findLeavingEdge(); 1174 1161 changeFlows(change); … … 1180 1167 } 1181 1168 1182 // Checking if the flow amount equals zero on all the artificial 1183 // edges 1169 // Check if the flow amount equals zero on all the artificial edges 1184 1170 for (InEdgeIt e(_graph, _root); e != INVALID; ++e) 1185 1171 if (_flow[e] > 0) return false; … … 1187 1173 if (_flow[e] > 0) return false; 1188 1174 1189 // Copy ingflow values to _flow_result1175 // Copy flow values to _flow_result 1190 1176 if (_lower) { 1191 1177 for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) … … 1195 1181 (*_flow_result)[e] = _flow[_edge_ref[e]]; 1196 1182 } 1197 // Copy ingpotential values to _potential_result1183 // Copy potential values to _potential_result 1198 1184 for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) 1199 1185 (*_potential_result)[n] = _potential[_node_ref[n]];
Note: See TracChangeset
for help on using the changeset viewer.