Changeset 2619:30fb4d68b0e8 in lemon0.x
 Timestamp:
 10/05/08 15:36:43 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3504
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r2593 r2619 33 33 #include <lemon/math.h> 34 34 35 #define _DEBUG_ 36 35 37 namespace lemon { 36 38 … … 38 40 /// @{ 39 41 40 /// \brief Implementation of the network simplex algorithm for41 /// f inding a minimum cost flow.42 /// \brief Implementation of the primal network simplex algorithm 43 /// for finding a minimum cost flow. 42 44 /// 43 /// \ref NetworkSimplex implements the network simplex algorithm for44 /// f inding a minimum cost flow.45 /// \ref NetworkSimplex implements the primal network simplex algorithm 46 /// for finding a minimum cost flow. 45 47 /// 46 48 /// \tparam Graph The directed graph type the algorithm runs on. … … 56 58 ///  \c CostMap::Value must be signed type. 57 59 /// 58 /// \note \ref NetworkSimplex provides sixdifferent pivot rule60 /// \note \ref NetworkSimplex provides five different pivot rule 59 61 /// implementations that significantly affect the efficiency of the 60 62 /// algorithm. 61 /// By default a combined pivot rule is used, which is the fastest62 /// implementationaccording to our benchmark tests.63 /// Another pivot rule can be selected using \ref run() function64 /// with the proper parameter.63 /// By default "Block Search" pivot rule is used, which proved to be 64 /// by far the most efficient according to our benchmark tests. 65 /// However another pivot rule can be selected using \ref run() 66 /// function with the proper parameter. 65 67 /// 66 68 /// \author Peter Kovacs 67 68 69 template < typename Graph, 69 70 typename LowerMap = typename Graph::template EdgeMap<int>, … … 90 91 typedef typename SGraph::template NodeMap<Edge> EdgeNodeMap; 91 92 typedef typename SGraph::template EdgeMap<int> IntEdgeMap; 93 typedef typename SGraph::template EdgeMap<bool> BoolEdgeMap; 92 94 93 95 typedef typename Graph::template NodeMap<Node> NodeRefMap; 94 96 typedef typename Graph::template EdgeMap<Edge> EdgeRefMap; 97 98 typedef std::vector<Edge> EdgeVector; 95 99 96 100 public: … … 108 112 BEST_ELIGIBLE_PIVOT, 109 113 BLOCK_SEARCH_PIVOT, 110 LIMITED_SEARCH_PIVOT,111 114 CANDIDATE_LIST_PIVOT, 112 COMBINED_PIVOT115 ALTERING_LIST_PIVOT 113 116 }; 114 117 … … 149 152 /// This class implements the "First Eligible" pivot rule 150 153 /// for the \ref NetworkSimplex "network simplex" algorithm. 154 /// 155 /// For more information see \ref NetworkSimplex::run(). 151 156 class FirstEligiblePivotRule 152 157 { 153 158 private: 154 159 160 // References to the NetworkSimplex class 155 161 NetworkSimplex &_ns; 156 EdgeIt _next_edge; 162 EdgeVector &_edges; 163 164 int _next_edge; 157 165 158 166 public: 159 167 160 /// Constructor. 161 FirstEligiblePivotRule(NetworkSimplex &ns) : 162 _ns(ns), _next_edge(ns._graph) {} 163 164 /// Finds the next entering edge. 165 bool findEnteringEdge() { 166 for (EdgeIt e = _next_edge; e != INVALID; ++e) { 168 /// Constructor 169 FirstEligiblePivotRule(NetworkSimplex &ns, EdgeVector &edges) : 170 _ns(ns), _edges(edges), _next_edge(0) {} 171 172 /// Find next entering edge 173 inline bool findEnteringEdge() { 174 Edge e; 175 for (int i = _next_edge; i < int(_edges.size()); ++i) { 176 e = _edges[i]; 167 177 if (_ns._state[e] * _ns._red_cost[e] < 0) { 168 178 _ns._in_edge = e; 169 _next_edge = ++e;179 _next_edge = i + 1; 170 180 return true; 171 181 } 172 182 } 173 for (EdgeIt e(_ns._graph); e != _next_edge; ++e) { 183 for (int i = 0; i < _next_edge; ++i) { 184 e = _edges[i]; 174 185 if (_ns._state[e] * _ns._red_cost[e] < 0) { 175 186 _ns._in_edge = e; 176 _next_edge = ++e;187 _next_edge = i + 1; 177 188 return true; 178 189 } … … 187 198 /// This class implements the "Best Eligible" pivot rule 188 199 /// for the \ref NetworkSimplex "network simplex" algorithm. 200 /// 201 /// For more information see \ref NetworkSimplex::run(). 189 202 class BestEligiblePivotRule 190 203 { 191 204 private: 192 205 206 // References to the NetworkSimplex class 193 207 NetworkSimplex &_ns; 208 EdgeVector &_edges; 194 209 195 210 public: 196 211 197 /// Constructor. 198 BestEligiblePivotRule(NetworkSimplex &ns) : _ns(ns) {} 199 200 /// Finds the next entering edge. 201 bool findEnteringEdge() { 212 /// Constructor 213 BestEligiblePivotRule(NetworkSimplex &ns, EdgeVector &edges) : 214 _ns(ns), _edges(edges) {} 215 216 /// Find next entering edge 217 inline bool findEnteringEdge() { 202 218 Cost min = 0; 203 for (EdgeIt e(_ns._graph); e != INVALID; ++e) { 219 Edge e; 220 for (int i = 0; i < int(_edges.size()); ++i) { 221 e = _edges[i]; 204 222 if (_ns._state[e] * _ns._red_cost[e] < min) { 205 223 min = _ns._state[e] * _ns._red_cost[e]; … … 216 234 /// This class implements the "Block Search" pivot rule 217 235 /// for the \ref NetworkSimplex "network simplex" algorithm. 236 /// 237 /// For more information see \ref NetworkSimplex::run(). 218 238 class BlockSearchPivotRule 219 239 { 220 240 private: 221 241 242 // References to the NetworkSimplex class 222 243 NetworkSimplex &_ns; 223 EdgeIt _next_edge, _min_edge; 244 EdgeVector &_edges; 245 224 246 int _block_size; 225 226 static const int MIN_BLOCK_SIZE = 10; 247 int _next_edge, _min_edge; 227 248 228 249 public: 229 250 230 /// Constructor .231 BlockSearchPivotRule(NetworkSimplex &ns ) :232 _ns(ns), _ next_edge(ns._graph), _min_edge(ns._graph)251 /// Constructor 252 BlockSearchPivotRule(NetworkSimplex &ns, EdgeVector &edges) : 253 _ns(ns), _edges(edges), _next_edge(0), _min_edge(0) 233 254 { 234 _block_size = 2 * int(sqrt(countEdges(_ns._graph))); 235 if (_block_size < MIN_BLOCK_SIZE) _block_size = MIN_BLOCK_SIZE; 236 } 237 238 /// Finds the next entering edge. 239 bool findEnteringEdge() { 255 // The main parameters of the pivot rule 256 const double BLOCK_SIZE_FACTOR = 2.0; 257 const int MIN_BLOCK_SIZE = 10; 258 259 _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_edges.size())), 260 MIN_BLOCK_SIZE ); 261 } 262 263 /// Find next entering edge 264 inline bool findEnteringEdge() { 240 265 Cost curr, min = 0; 241 int cnt = 0; 242 for (EdgeIt e = _next_edge; e != INVALID; ++e) { 266 Edge e; 267 int cnt = _block_size; 268 int i; 269 for (i = _next_edge; i < int(_edges.size()); ++i) { 270 e = _edges[i]; 243 271 if ((curr = _ns._state[e] * _ns._red_cost[e]) < min) { 244 272 min = curr; 245 _min_edge = e;273 _min_edge = i; 246 274 } 247 if ( ++cnt == _block_size) {275 if (cnt == 0) { 248 276 if (min < 0) break; 249 cnt = 0;277 cnt = _block_size; 250 278 } 251 279 } 252 if (min == 0) { 253 for (EdgeIt e(_ns._graph); e != _next_edge; ++e) { 280 if (min == 0  cnt > 0) { 281 for (i = 0; i < _next_edge; ++i) { 282 e = _edges[i]; 254 283 if ((curr = _ns._state[e] * _ns._red_cost[e]) < min) { 255 284 min = curr; 256 _min_edge = e;285 _min_edge = i; 257 286 } 258 if ( ++cnt == _block_size) {287 if (cnt == 0) { 259 288 if (min < 0) break; 260 cnt = 0;289 cnt = _block_size; 261 290 } 262 291 } 263 292 } 264 _ns._in_edge = _min_edge; 265 _next_edge = ++_min_edge; 266 return min < 0; 293 if (min >= 0) return false; 294 _ns._in_edge = _edges[_min_edge]; 295 _next_edge = i; 296 return true; 267 297 } 268 298 }; //class BlockSearchPivotRule 269 270 /// \brief Implementation of the "Limited Search" pivot rule for the271 /// \ref NetworkSimplex "network simplex" algorithm.272 ///273 /// This class implements the "Limited Search" pivot rule274 /// for the \ref NetworkSimplex "network simplex" algorithm.275 class LimitedSearchPivotRule276 {277 private:278 279 NetworkSimplex &_ns;280 EdgeIt _next_edge, _min_edge;281 int _sample_size;282 283 static const int SAMPLE_SIZE_FACTOR = 15;284 static const int MIN_SAMPLE_SIZE = 10;285 286 public:287 288 /// Constructor.289 LimitedSearchPivotRule(NetworkSimplex &ns) :290 _ns(ns), _next_edge(ns._graph), _min_edge(ns._graph)291 {292 _sample_size = countEdges(_ns._graph) *293 SAMPLE_SIZE_FACTOR / 10000;294 if (_sample_size < MIN_SAMPLE_SIZE)295 _sample_size = MIN_SAMPLE_SIZE;296 }297 298 /// Finds the next entering edge.299 bool findEnteringEdge() {300 Cost curr, min = 0;301 int cnt = 0;302 for (EdgeIt e = _next_edge; e != INVALID; ++e) {303 if ((curr = _ns._state[e] * _ns._red_cost[e]) < min) {304 min = curr;305 _min_edge = e;306 }307 if (curr < 0 && ++cnt == _sample_size) break;308 }309 if (min == 0) {310 for (EdgeIt e(_ns._graph); e != _next_edge; ++e) {311 if ((curr = _ns._state[e] * _ns._red_cost[e]) < min) {312 min = curr;313 _min_edge = e;314 }315 if (curr < 0 && ++cnt == _sample_size) break;316 }317 }318 _ns._in_edge = _min_edge;319 _next_edge = ++_min_edge;320 return min < 0;321 }322 }; //class LimitedSearchPivotRule323 299 324 300 /// \brief Implementation of the "Candidate List" pivot rule for the … … 327 303 /// This class implements the "Candidate List" pivot rule 328 304 /// for the \ref NetworkSimplex "network simplex" algorithm. 305 /// 306 /// For more information see \ref NetworkSimplex::run(). 329 307 class CandidateListPivotRule 330 308 { 331 309 private: 332 310 311 // References to the NetworkSimplex class 333 312 NetworkSimplex &_ns; 334 335 // The list of candidate edges. 336 std::vector<Edge> _candidates; 337 // The maximum length of the edge list. 338 int _list_length; 339 // The maximum number of minor iterations between two major 340 // itarations. 341 int _minor_limit; 342 343 int _minor_count; 344 EdgeIt _next_edge; 345 346 static const int LIST_LENGTH_FACTOR = 20; 347 static const int MINOR_LIMIT_FACTOR = 10; 348 static const int MIN_LIST_LENGTH = 10; 349 static const int MIN_MINOR_LIMIT = 2; 313 EdgeVector &_edges; 314 315 EdgeVector _candidates; 316 int _list_length, _minor_limit; 317 int _curr_length, _minor_count; 318 int _next_edge, _min_edge; 350 319 351 320 public: 352 321 353 /// Constructor .354 CandidateListPivotRule(NetworkSimplex &ns ) :355 _ns(ns), _ next_edge(ns._graph)322 /// Constructor 323 CandidateListPivotRule(NetworkSimplex &ns, EdgeVector &edges) : 324 _ns(ns), _edges(edges), _next_edge(0), _min_edge(0) 356 325 { 357 int edge_num = countEdges(_ns._graph); 358 _minor_count = 0; 359 _list_length = edge_num * LIST_LENGTH_FACTOR / 10000; 360 if (_list_length < MIN_LIST_LENGTH) 361 _list_length = MIN_LIST_LENGTH; 362 _minor_limit = _list_length * MINOR_LIMIT_FACTOR / 100; 363 if (_minor_limit < MIN_MINOR_LIMIT) 364 _minor_limit = MIN_MINOR_LIMIT; 365 } 366 367 /// Finds the next entering edge. 368 bool findEnteringEdge() { 326 // The main parameters of the pivot rule 327 const double LIST_LENGTH_FACTOR = 1.0; 328 const int MIN_LIST_LENGTH = 10; 329 const double MINOR_LIMIT_FACTOR = 0.1; 330 const int MIN_MINOR_LIMIT = 3; 331 332 _list_length = std::max( int(LIST_LENGTH_FACTOR * sqrt(_edges.size())), 333 MIN_LIST_LENGTH ); 334 _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length), 335 MIN_MINOR_LIMIT ); 336 _curr_length = _minor_count = 0; 337 _candidates.resize(_list_length); 338 } 339 340 /// Find next entering edge 341 inline bool findEnteringEdge() { 369 342 Cost min, curr; 370 if (_minor_count < _minor_limit && _candidates.size() > 0) { 371 // Minor iteration 343 if (_curr_length > 0 && _minor_count < _minor_limit) { 344 // Minor iteration: selecting the best eligible edge from 345 // the current candidate list 372 346 ++_minor_count; 373 347 Edge e; 374 348 min = 0; 375 for (int i = 0; i < int(_candidates.size()); ++i) {349 for (int i = 0; i < _curr_length; ++i) { 376 350 e = _candidates[i]; 377 if ((curr = _ns._state[e] * _ns._red_cost[e]) < min) { 378 min = curr; 379 _ns._in_edge = e; 380 } 381 } 382 if (min < 0) return true; 383 } 384 385 // Major iteration 386 _candidates.clear(); 387 EdgeIt e = _next_edge; 388 min = 0; 389 for ( ; e != INVALID; ++e) { 390 if ((curr = _ns._state[e] * _ns._red_cost[e]) < 0) { 391 _candidates.push_back(e); 351 curr = _ns._state[e] * _ns._red_cost[e]; 392 352 if (curr < min) { 393 353 min = curr; 394 354 _ns._in_edge = e; 395 355 } 396 if (int(_candidates.size()) == _list_length) break; 356 if (curr >= 0) { 357 _candidates[i] = _candidates[_curr_length]; 358 } 397 359 } 398 } 399 if (int(_candidates.size()) < _list_length) { 400 for (e = EdgeIt(_ns._graph); e != _next_edge; ++e) { 360 if (min < 0) return true; 361 } 362 363 // Major iteration: building a new candidate list 364 Edge e; 365 min = 0; 366 _curr_length = 0; 367 int i; 368 for (i = _next_edge; i < int(_edges.size()); ++i) { 369 e = _edges[i]; 370 if ((curr = _ns._state[e] * _ns._red_cost[e]) < 0) { 371 _candidates[_curr_length++] = e; 372 if (curr < min) { 373 min = curr; 374 _min_edge = i; 375 } 376 if (_curr_length == _list_length) break; 377 } 378 } 379 if (_curr_length < _list_length) { 380 for (i = 0; i < _next_edge; ++i) { 381 e = _edges[i]; 401 382 if ((curr = _ns._state[e] * _ns._red_cost[e]) < 0) { 402 _candidates .push_back(e);383 _candidates[_curr_length++] = e; 403 384 if (curr < min) { 404 385 min = curr; 405 _ ns._in_edge = e;386 _min_edge = i; 406 387 } 407 if ( int(_candidates.size())== _list_length) break;388 if (_curr_length == _list_length) break; 408 389 } 409 390 } 410 391 } 411 if (_c andidates.size()== 0) return false;392 if (_curr_length == 0) return false; 412 393 _minor_count = 1; 413 _next_edge = ++e; 394 _ns._in_edge = _edges[_min_edge]; 395 _next_edge = i; 414 396 return true; 415 397 } 416 398 }; //class CandidateListPivotRule 399 400 /// \brief Implementation of the "Altering Candidate List" pivot rule 401 /// for the \ref NetworkSimplex "network simplex" algorithm. 402 /// 403 /// This class implements the "Altering Candidate List" pivot rule 404 /// for the \ref NetworkSimplex "network simplex" algorithm. 405 /// 406 /// For more information see \ref NetworkSimplex::run(). 407 class AlteringListPivotRule 408 { 409 private: 410 411 // References to the NetworkSimplex class 412 NetworkSimplex &_ns; 413 EdgeVector &_edges; 414 415 EdgeVector _candidates; 416 SCostMap _cand_cost; 417 int _block_size, _head_length, _curr_length; 418 int _next_edge; 419 420 // Functor class to compare edges during sort of the candidate list 421 class SortFunc 422 { 423 private: 424 const SCostMap &_map; 425 public: 426 SortFunc(const SCostMap &map) : _map(map) {} 427 bool operator()(const Edge &e1, const Edge &e2) { 428 return _map[e1] < _map[e2]; 429 } 430 }; 431 432 SortFunc _sort_func; 433 434 public: 435 436 /// Constructor 437 AlteringListPivotRule(NetworkSimplex &ns, EdgeVector &edges) : 438 _ns(ns), _edges(edges), _cand_cost(_ns._graph), 439 _next_edge(0), _sort_func(_cand_cost) 440 { 441 // The main parameters of the pivot rule 442 const double BLOCK_SIZE_FACTOR = 1.0; 443 const int MIN_BLOCK_SIZE = 10; 444 const double HEAD_LENGTH_FACTOR = 0.1; 445 const int MIN_HEAD_LENGTH = 5; 446 447 _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_edges.size())), 448 MIN_BLOCK_SIZE ); 449 _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size), 450 MIN_HEAD_LENGTH ); 451 _candidates.resize(_head_length + _block_size); 452 _curr_length = 0; 453 } 454 455 /// Find next entering edge 456 inline bool findEnteringEdge() { 457 // Checking the current candidate list 458 Edge e; 459 for (int idx = 0; idx < _curr_length; ++idx) { 460 e = _candidates[idx]; 461 if ((_cand_cost[e] = _ns._state[e] * _ns._red_cost[e]) >= 0) { 462 _candidates[idx] = _candidates[_curr_length]; 463 } 464 } 465 466 // Extending the list 467 int cnt = _block_size; 468 int last_edge = 0; 469 int limit = _head_length; 470 for (int i = _next_edge; i < int(_edges.size()); ++i) { 471 e = _edges[i]; 472 if ((_cand_cost[e] = _ns._state[e] * _ns._red_cost[e]) < 0) { 473 _candidates[_curr_length++] = e; 474 last_edge = i; 475 } 476 if (cnt == 0) { 477 if (_curr_length > limit) break; 478 limit = 0; 479 cnt = _block_size; 480 } 481 } 482 if (_curr_length <= limit) { 483 for (int i = 0; i < _next_edge; ++i) { 484 e = _edges[i]; 485 if ((_cand_cost[e] = _ns._state[e] * _ns._red_cost[e]) < 0) { 486 _candidates[_curr_length++] = e; 487 last_edge = i; 488 } 489 if (cnt == 0) { 490 if (_curr_length > limit) break; 491 limit = 0; 492 cnt = _block_size; 493 } 494 } 495 } 496 if (_curr_length == 0) return false; 497 _next_edge = last_edge + 1; 498 499 // Sorting the list partially 500 EdgeVector::iterator sort_end = _candidates.begin(); 501 EdgeVector::iterator vector_end = _candidates.begin(); 502 for (int idx = 0; idx < _curr_length; ++idx) { 503 ++vector_end; 504 if (idx <= _head_length) ++sort_end; 505 } 506 partial_sort(_candidates.begin(), sort_end, vector_end, _sort_func); 507 508 _ns._in_edge = _candidates[0]; 509 if (_curr_length > _head_length) { 510 _candidates[0] = _candidates[_head_length  1]; 511 _curr_length = _head_length  1; 512 } else { 513 _candidates[0] = _candidates[_curr_length  1]; 514 _curr_length; 515 } 516 517 return true; 518 } 519 }; //class AlteringListPivotRule 417 520 418 521 private: … … 424 527 STATE_LOWER = 1 425 528 }; 426 427 // Constant for the combined pivot rule.428 static const int COMBINED_PIVOT_MAX_DEG = 5;429 529 430 530 private: … … 466 566 // The reduced cost map 467 567 ReducedCostMap _red_cost; 568 569 // The nonartifical edges 570 EdgeVector _edges; 468 571 469 572 // Members for handling the original graph … … 673 776 } 674 777 675 /// \brief Set sthe flow map.676 /// 677 /// Set sthe flow map.778 /// \brief Set the flow map. 779 /// 780 /// Set the flow map. 678 781 /// 679 782 /// \return \c (*this) … … 687 790 } 688 791 689 /// \brief Set sthe potential map.690 /// 691 /// Set sthe potential map.792 /// \brief Set the potential map. 793 /// 794 /// Set the potential map. 692 795 /// 693 796 /// \return \c (*this) … … 702 805 703 806 /// \name Execution control 704 /// The only way to execute the algorithm is to call the run()705 /// function.706 807 707 808 /// @{ … … 727 828 /// edge is selected from this block (\ref BlockSearchPivotRule). 728 829 /// 729 ///  LIMITED_SEARCH_PIVOT A specified number of eligible edges are 730 /// examined in every iteration in a wraparound fashion and the best 731 /// one is selected from them (\ref LimitedSearchPivotRule). 732 /// 733 ///  CANDIDATE_LIST_PIVOT In major iterations a candidate list is 734 /// built from eligible edges and it is used for edge selection in 735 /// the following minor iterations (\ref CandidateListPivotRule). 736 /// 737 ///  COMBINED_PIVOT This is a combined version of the two fastest 738 /// pivot rules. 739 /// For rather sparse graphs \ref LimitedSearchPivotRule 740 /// "Limited Search" implementation is used, otherwise 741 /// \ref BlockSearchPivotRule "Block Search" pivot rule is used. 742 /// According to our benchmark tests this combined method is the 743 /// most efficient. 830 ///  CANDIDATE_LIST_PIVOT In a major iteration a candidate list is 831 /// built from eligible edges in a wraparound fashion and in the 832 /// following minor iterations the best eligible edge is selected 833 /// from this list (\ref CandidateListPivotRule). 834 /// 835 ///  ALTERING_LIST_PIVOT It is a modified version of the 836 /// "Candidate List" pivot rule. It keeps only the several best 837 /// eligible edges from the former candidate list and extends this 838 /// list in every iteration (\ref AlteringListPivotRule). 839 /// 840 /// According to our comprehensive benchmark tests the "Block Search" 841 /// pivot rule proved to be by far the fastest and the most robust 842 /// on various test inputs. Thus it is the default option. 744 843 /// 745 844 /// \return \c true if a feasible flow can be found. 746 bool run(PivotRuleEnum pivot_rule = COMBINED_PIVOT) {845 bool run(PivotRuleEnum pivot_rule = BLOCK_SEARCH_PIVOT) { 747 846 return init() && start(pivot_rule); 748 847 } … … 751 850 752 851 /// \name Query Functions 753 /// The result of the algorithm can be obtained using these 754 /// functions. 755 /// \n run() must be called before using them. 852 /// The results of the algorithm can be obtained using these 853 /// functions.\n 854 /// \ref lemon::NetworkSimplex::run() "run()" must be called before 855 /// using them. 756 856 757 857 /// @{ 758 858 759 /// \brief Return sa const reference to the edge map storing the859 /// \brief Return a const reference to the edge map storing the 760 860 /// found flow. 761 861 /// 762 /// Return sa const reference to the edge map storing the found flow.862 /// Return a const reference to the edge map storing the found flow. 763 863 /// 764 864 /// \pre \ref run() must be called before using this function. … … 767 867 } 768 868 769 /// \brief Return sa const reference to the node map storing the869 /// \brief Return a const reference to the node map storing the 770 870 /// found potentials (the dual solution). 771 871 /// 772 /// Return sa const reference to the node map storing the found872 /// Return a const reference to the node map storing the found 773 873 /// potentials (the dual solution). 774 874 /// … … 778 878 } 779 879 780 /// \brief Return sthe flow on the given edge.781 /// 782 /// Return sthe flow on the given edge.880 /// \brief Return the flow on the given edge. 881 /// 882 /// Return the flow on the given edge. 783 883 /// 784 884 /// \pre \ref run() must be called before using this function. … … 787 887 } 788 888 789 /// \brief Return sthe potential of the given node.790 /// 791 /// Return sthe potential of the given node.889 /// \brief Return the potential of the given node. 890 /// 891 /// Return the potential of the given node. 792 892 /// 793 893 /// \pre \ref run() must be called before using this function. … … 796 896 } 797 897 798 /// \brief Return sthe total cost of the found flow.799 /// 800 /// Return sthe total cost of the found flow. The complexity of the898 /// \brief Return the total cost of the found flow. 899 /// 900 /// Return the total cost of the found flow. The complexity of the 801 901 /// function is \f$ O(e) \f$. 802 902 /// … … 813 913 private: 814 914 815 /// \brief Extend s the underlaying graph and initializesall the915 /// \brief Extend the underlying graph and initialize all the 816 916 /// node and edge maps. 817 917 bool init() { … … 828 928 } 829 929 830 // Initializing state and flow maps 930 // Initializing the edge vector and the edge maps 931 _edges.reserve(countEdges(_graph)); 831 932 for (EdgeIt e(_graph); e != INVALID; ++e) { 933 _edges.push_back(e); 832 934 _flow[e] = 0; 833 935 _state[e] = STATE_LOWER; … … 874 976 } 875 977 876 /// Find sthe join node.877 Node findJoinNode() {978 /// Find the join node. 979 inline Node findJoinNode() { 878 980 Node u = _graph.source(_in_edge); 879 981 Node v = _graph.target(_in_edge); … … 889 991 } 890 992 891 /// \brief Finds the leaving edge of the cycle. Returns \c true if 892 /// the leaving edge is not the same as the entering edge. 893 bool findLeavingEdge() { 993 /// \brief Find the leaving edge of the cycle. 994 /// \return \c true if the leaving edge is not the same as the 995 /// entering edge. 996 inline bool findLeavingEdge() { 894 997 // Initializing first and second nodes according to the direction 895 998 // of the cycle … … 935 1038 } 936 1039 937 /// Change s\c flow and \c state edge maps.938 void changeFlows(bool change) {1040 /// Change \c flow and \c state edge maps. 1041 inline void changeFlows(bool change) { 939 1042 // Augmenting along the cycle 940 1043 if (delta > 0) { … … 958 1061 } 959 1062 960 /// Update s\c thread and \c parent node maps.961 void updateThreadParent() {1063 /// Update \c thread and \c parent node maps. 1064 inline void updateThreadParent() { 962 1065 Node u; 963 1066 v_out = _parent[u_out]; … … 1017 1120 } 1018 1121 1019 /// Update s\c pred_edge and \c forward node maps.1020 void updatePredEdge() {1122 /// Update \c pred_edge and \c forward node maps. 1123 inline void updatePredEdge() { 1021 1124 Node u = u_out, v; 1022 1125 while (u != u_in) { … … 1030 1133 } 1031 1134 1032 /// Update s\c depth and \c potential node maps.1033 void updateDepthPotential() {1135 /// Update \c depth and \c potential node maps. 1136 inline void updateDepthPotential() { 1034 1137 _depth[u_in] = _depth[v_in] + 1; 1035 1138 _potential[u_in] = _forward[u_in] ? … … 1050 1153 } 1051 1154 1052 /// Execute sthe algorithm.1155 /// Execute the algorithm. 1053 1156 bool start(PivotRuleEnum pivot_rule) { 1157 // Selecting the pivot rule implementation 1054 1158 switch (pivot_rule) { 1055 1159 case FIRST_ELIGIBLE_PIVOT: … … 1059 1163 case BLOCK_SEARCH_PIVOT: 1060 1164 return start<BlockSearchPivotRule>(); 1061 case LIMITED_SEARCH_PIVOT:1062 return start<LimitedSearchPivotRule>();1063 1165 case CANDIDATE_LIST_PIVOT: 1064 1166 return start<CandidateListPivotRule>(); 1065 case COMBINED_PIVOT: 1066 if ( countEdges(_graph) / countNodes(_graph) <= 1067 COMBINED_PIVOT_MAX_DEG ) 1068 return start<LimitedSearchPivotRule>(); 1069 else 1070 return start<BlockSearchPivotRule>(); 1167 case ALTERING_LIST_PIVOT: 1168 return start<AlteringListPivotRule>(); 1071 1169 } 1072 1170 return false; … … 1075 1173 template<class PivotRuleImplementation> 1076 1174 bool start() { 1077 PivotRuleImplementation pivot(*this );1175 PivotRuleImplementation pivot(*this, _edges); 1078 1176 1079 1177 // Executing the network simplex algorithm
Note: See TracChangeset
for help on using the changeset viewer.