Changeset 1003:16f55008c863 in lemon-main
- Timestamp:
- 01/30/12 23:24:40 (13 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 5 edited
-
doc/groups.dox (modified) (1 diff)
-
lemon/capacity_scaling.h (modified) (3 diffs)
-
lemon/cost_scaling.h (modified) (3 diffs)
-
lemon/cycle_canceling.h (modified) (7 diffs)
-
lemon/network_simplex.h (modified) (3 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r1002 r1003 408 408 409 409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient 410 implementations, but the other algorithms could be faster in special cases. 410 implementations. 411 \ref NetworkSimplex is usually the fastest on relatively small graphs (up to 412 several thousands of nodes) and on dense graphs, while \ref CostScaling is 413 typically more efficient on large graphs (e.g. hundreds of thousands of 414 nodes or above), especially if they are sparse. 415 However, other algorithms could be faster in special cases. 411 416 For example, if the total supply and/or capacities are rather small, 412 417 \ref CapacityScaling is usually the fastest algorithm (without effective scaling). -
lemon/capacity_scaling.h
r922 r1003 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
r938 r1003 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
r922 r1003 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
r922 r1003 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.
