Changes in lemon/capacity_scaling.h [956:141f9c0db4a3:1270:dceba191c00d] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r956 r1270 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2013 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 67 67 /// \ref CapacityScaling implements the capacity scaling version 68 68 /// of the successive shortest path algorithm for finding a 69 /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows, 70 /// \ref edmondskarp72theoretical. It is an efficient dual 71 /// solution method. 69 /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows, 70 /// \cite edmondskarp72theoretical. It is an efficient dual 71 /// solution method, which runs in polynomial time 72 /// \f$O(m\log U (n+m)\log n)\f$, where <i>U</i> denotes the maximum 73 /// of node supply and arc capacity values. 74 /// 75 /// This algorithm is typically slower than \ref CostScaling and 76 /// \ref NetworkSimplex, but in special cases, it can be more 77 /// efficient than them. 78 /// (For more information, see \ref min_cost_flow_algs "the module page".) 72 79 /// 73 80 /// Most of the parameters of the problem (except for the digraph) … … 87 94 /// consider to use the named template parameters instead. 88 95 /// 89 /// \warning Both number types must be signed and all input data must 90 /// be integer. 91 /// \warning This algorithm does not support negative costs for such 92 /// arcs that have infinite upper bound. 96 /// \warning Both \c V and \c C must be signed number types. 97 /// \warning Capacity bounds and supply values must be integer, but 98 /// arc costs can be arbitrary real numbers. 99 /// \warning This algorithm does not support negative costs for 100 /// arcs having infinite upper bound. 93 101 #ifdef DOXYGEN 94 102 template <typename GR, typename V, typename C, typename TR> … … 111 119 typedef typename TR::Heap Heap; 112 120 113 /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm 121 /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class" 122 /// of the algorithm 114 123 typedef TR Traits; 115 124 … … 423 432 /// 424 433 /// Using this function has the same effect as using \ref supplyMap() 425 /// with sucha map in which \c k is assigned to \c s, \c -k is434 /// with a map in which \c k is assigned to \c s, \c -k is 426 435 /// assigned to \c t and all other nodes have zero supply value. 427 436 /// … … 638 647 /// 639 648 /// This function returns the total cost of the found flow. 640 /// Its complexity is O( e).649 /// Its complexity is O(m). 641 650 /// 642 651 /// \note The return type of the function can be specified as a … … 676 685 } 677 686 678 /// \brief Return the flow map (the primal solution). 687 /// \brief Copy the flow values (the primal solution) into the 688 /// given map. 679 689 /// 680 690 /// This function copies the flow value on each arc into the given … … 700 710 } 701 711 702 /// \brief Return the potential map (the dual solution). 712 /// \brief Copy the potential values (the dual solution) into the 713 /// given map. 703 714 /// 704 715 /// This function copies the potential (dual value) of each node … … 729 740 } 730 741 if (_sum_supply > 0) return INFEASIBLE; 742 743 // Check lower and upper bounds 744 LEMON_DEBUG(checkBoundMaps(), 745 "Upper bounds must be greater or equal to the lower bounds"); 746 731 747 732 748 // Initialize vectors … … 822 838 823 839 return OPTIMAL; 840 } 841 842 // Check if the upper bound is greater or equal to the lower bound 843 // on each arc. 844 bool checkBoundMaps() { 845 for (int j = 0; j != _res_arc_num; ++j) { 846 if (_upper[j] < _lower[j]) return false; 847 } 848 return true; 824 849 } 825 850
Note: See TracChangeset
for help on using the changeset viewer.