Changeset 1165:16f55008c863 in lemon for lemon
- Timestamp:
- 01/30/12 23:24:40 (12 years ago)
- Branch:
- default
- Phase:
- public
- Location:
- lemon
- Files:
-
- 4 edited
-
capacity_scaling.h (modified) (3 diffs)
-
cost_scaling.h (modified) (3 diffs)
-
cycle_canceling.h (modified) (7 diffs)
-
network_simplex.h (modified) (3 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r1026 r1165 70 70 /// \ref edmondskarp72theoretical. It is an efficient dual 71 71 /// solution method. 72 /// 73 /// This algorithm is typically slower than \ref CostScaling and 74 /// \ref NetworkSimplex, but in special cases, it can be more 75 /// efficient than them. 76 /// (For more information, see \ref min_cost_flow_algs "the module page".) 72 77 /// 73 78 /// Most of the parameters of the problem (except for the digraph) … … 677 682 } 678 683 679 /// \brief Return the flow map (the primal solution). 684 /// \brief Copy the flow values (the primal solution) into the 685 /// given map. 680 686 /// 681 687 /// This function copies the flow value on each arc into the given … … 701 707 } 702 708 703 /// \brief Return the potential map (the dual solution). 709 /// \brief Copy the potential values (the dual solution) into the 710 /// given map. 704 711 /// 705 712 /// This function copies the potential (dual value) of each node -
lemon/cost_scaling.h
r1049 r1165 99 99 /// 100 100 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest 101 /// implementations available in LEMON for this problem. 101 /// implementations available in LEMON for solving this problem. 102 /// (For more information, see \ref min_cost_flow_algs "the module page".) 102 103 /// 103 104 /// Most of the parameters of the problem (except for the digraph) … … 705 706 } 706 707 707 /// \brief Return the flow map (the primal solution). 708 /// \brief Copy the flow values (the primal solution) into the 709 /// given map. 708 710 /// 709 711 /// This function copies the flow value on each arc into the given … … 729 731 } 730 732 731 /// \brief Return the potential map (the dual solution). 733 /// \brief Copy the potential values (the dual solution) into the 734 /// given map. 732 735 /// 733 736 /// This function copies the potential (dual value) of each node -
lemon/cycle_canceling.h
r1026 r1165 49 49 /// \ref amo93networkflows, \ref klein67primal, 50 50 /// \ref goldberg89cyclecanceling. 51 /// The most efficent one (both theoretically and practically) 52 /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm, 53 /// thus it is the default method. 54 /// It is strongly polynomial, but in practice, it is typically much 55 /// slower than the scaling algorithms and NetworkSimplex. 51 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN 52 /// "Cancel-and-Tighten" algorithm, thus it is the default method. 53 /// It runs in strongly polynomial time, but in practice, it is typically 54 /// orders of magnitude slower than the scaling algorithms and 55 /// \ref NetworkSimplex. 56 /// (For more information, see \ref min_cost_flow_algs "the module page".) 56 57 /// 57 58 /// Most of the parameters of the problem (except for the digraph) … … 117 118 /// 118 119 /// \ref CycleCanceling provides three different cycle-canceling 119 /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel andTighten"120 /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten" 120 121 /// is used, which is by far the most efficient and the most robust. 121 122 /// However, the other methods can be selected using the \ref run() … … 123 124 enum Method { 124 125 /// A simple cycle-canceling method, which uses the 125 /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration 126 /// number for detecting negative cycles in the residual network. 126 /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative 127 /// cycles in the residual network. 128 /// The number of Bellman-Ford iterations is bounded by a successively 129 /// increased limit. 127 130 SIMPLE_CYCLE_CANCELING, 128 131 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a … … 130 133 /// \ref goldberg89cyclecanceling. It improves along a 131 134 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. 132 /// Its running time complexity is O(n<sup>2</sup> m<sup>3</sup>log(n)).135 /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)). 133 136 MINIMUM_MEAN_CYCLE_CANCELING, 134 /// The "Cancel AndTighten" algorithm, which can be viewed as an137 /// The "Cancel-and-Tighten" algorithm, which can be viewed as an 135 138 /// improved version of the previous method 136 139 /// \ref goldberg89cyclecanceling. 137 140 /// It is faster both in theory and in practice, its running time 138 /// complexity is O(n<sup>2</sup> m<sup>2</sup>log(n)).141 /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)). 139 142 CANCEL_AND_TIGHTEN 140 143 }; … … 611 614 } 612 615 613 /// \brief Return the flow map (the primal solution). 616 /// \brief Copy the flow values (the primal solution) into the 617 /// given map. 614 618 /// 615 619 /// This function copies the flow value on each arc into the given … … 635 639 } 636 640 637 /// \brief Return the potential map (the dual solution). 641 /// \brief Copy the potential values (the dual solution) into the 642 /// given map. 638 643 /// 639 644 /// This function copies the potential (dual value) of each node … … 955 960 } 956 961 957 // Execute the "Cancel AndTighten" method962 // Execute the "Cancel-and-Tighten" method 958 963 void startCancelAndTighten() { 959 964 // Constants for the min mean cycle computations -
lemon/network_simplex.h
r1026 r1165 49 49 /// 50 50 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest 51 /// implementations available in LEMON for this problem. 51 /// implementations available in LEMON for solving this problem. 52 /// (For more information, see \ref min_cost_flow_algs "the module page".) 52 53 /// Furthermore, this class supports both directions of the supply/demand 53 54 /// inequality constraints. For more information, see \ref SupplyType. … … 1007 1008 } 1008 1009 1009 /// \brief Return the flow map (the primal solution). 1010 /// \brief Copy the flow values (the primal solution) into the 1011 /// given map. 1010 1012 /// 1011 1013 /// This function copies the flow value on each arc into the given … … 1031 1033 } 1032 1034 1033 /// \brief Return the potential map (the dual solution). 1035 /// \brief Copy the potential values (the dual solution) into the 1036 /// given map. 1034 1037 /// 1035 1038 /// This function copies the potential (dual value) of each node
Note: See TracChangeset
for help on using the changeset viewer.
