r879:25804ef35064
Thu, 12 Nov 2009 23:52:51
[Not Reviewed]
0 comments (0 inline)
0
3
0
| ... | ... |
@@ -397,33 +397,31 @@ |
| 397 | 397 |
@ingroup algs |
| 398 | 398 |
|
| 399 | 399 |
\brief Algorithms for finding minimum cost flows and circulations. |
| 400 | 400 |
|
| 401 | 401 |
This group contains the algorithms for finding minimum cost flows and |
| 402 | 402 |
circulations \ref amo93networkflows. For more information about this |
| 403 | 403 |
problem and its dual solution, see \ref min_cost_flow |
| 404 | 404 |
"Minimum Cost Flow Problem". |
| 405 | 405 |
|
| 406 | 406 |
LEMON contains several algorithms for this problem. |
| 407 | 407 |
- \ref NetworkSimplex Primal Network Simplex algorithm with various |
| 408 | 408 |
pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. |
| 409 |
- \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on |
|
| 410 |
cost scaling \ref goldberg90approximation, \ref goldberg97efficient, |
|
| 409 |
- \ref CostScaling Cost Scaling algorithm based on push/augment and |
|
| 410 |
relabel operations \ref goldberg90approximation, \ref goldberg97efficient, |
|
| 411 | 411 |
\ref bunnagel98efficient. |
| 412 |
- \ref CapacityScaling Successive Shortest %Path algorithm with optional |
|
| 413 |
capacity scaling \ref edmondskarp72theoretical. |
|
| 414 |
- \ref CancelAndTighten The Cancel and Tighten algorithm |
|
| 415 |
\ref goldberg89cyclecanceling. |
|
| 416 |
- \ref CycleCanceling Cycle-Canceling algorithms |
|
| 417 |
\ref klein67primal, \ref goldberg89cyclecanceling. |
|
| 412 |
- \ref CapacityScaling Capacity Scaling algorithm based on the successive |
|
| 413 |
shortest path method \ref edmondskarp72theoretical. |
|
| 414 |
- \ref CycleCanceling Cycle-Canceling algorithms, two of which are |
|
| 415 |
strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. |
|
| 418 | 416 |
|
| 419 | 417 |
In general NetworkSimplex is the most efficient implementation, |
| 420 | 418 |
but in special cases other algorithms could be faster. |
| 421 | 419 |
For example, if the total supply and/or capacities are rather small, |
| 422 | 420 |
CapacityScaling is usually the fastest algorithm (without effective scaling). |
| 423 | 421 |
*/ |
| 424 | 422 |
|
| 425 | 423 |
/** |
| 426 | 424 |
@defgroup min_cut Minimum Cut Algorithms |
| 427 | 425 |
@ingroup algs |
| 428 | 426 |
|
| 429 | 427 |
\brief Algorithms for finding minimum cut in graphs. |
| ... | ... |
@@ -57,25 +57,26 @@ |
| 57 | 57 |
/// must be \ref RangeMap "RangeMap<int>". |
| 58 | 58 |
typedef BinHeap<Cost, RangeMap<int> > Heap; |
| 59 | 59 |
}; |
| 60 | 60 |
|
| 61 | 61 |
/// \addtogroup min_cost_flow_algs |
| 62 | 62 |
/// @{
|
| 63 | 63 |
|
| 64 | 64 |
/// \brief Implementation of the Capacity Scaling algorithm for |
| 65 | 65 |
/// finding a \ref min_cost_flow "minimum cost flow". |
| 66 | 66 |
/// |
| 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" |
|
| 69 |
/// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows, |
|
| 70 |
/// \ref edmondskarp72theoretical. It is an efficient dual |
|
| 70 | 71 |
/// solution method. |
| 71 | 72 |
/// |
| 72 | 73 |
/// Most of the parameters of the problem (except for the digraph) |
| 73 | 74 |
/// can be given using separate functions, and the algorithm can be |
| 74 | 75 |
/// executed using the \ref run() function. If some parameters are not |
| 75 | 76 |
/// specified, then default values will be used. |
| 76 | 77 |
/// |
| 77 | 78 |
/// \tparam GR The digraph type the algorithm runs on. |
| 78 | 79 |
/// \tparam V The number type used for flow amounts, capacity bounds |
| 79 | 80 |
/// and supply values in the algorithm. By default it is \c int. |
| 80 | 81 |
/// \tparam C The number type used for costs and potentials in the |
| 81 | 82 |
/// algorithm. By default it is the same as \c V. |
| ... | ... |
@@ -81,26 +81,28 @@ |
| 81 | 81 |
typedef long LargeCost; |
| 82 | 82 |
#endif |
| 83 | 83 |
}; |
| 84 | 84 |
|
| 85 | 85 |
|
| 86 | 86 |
/// \addtogroup min_cost_flow_algs |
| 87 | 87 |
/// @{
|
| 88 | 88 |
|
| 89 | 89 |
/// \brief Implementation of the Cost Scaling algorithm for |
| 90 | 90 |
/// finding a \ref min_cost_flow "minimum cost flow". |
| 91 | 91 |
/// |
| 92 | 92 |
/// \ref CostScaling implements a cost scaling algorithm that performs |
| 93 |
/// push/augment and relabel operations for finding a minimum cost |
|
| 94 |
/// flow. It is an efficient primal-dual solution method, which |
|
| 93 |
/// push/augment and relabel operations for finding a \ref min_cost_flow |
|
| 94 |
/// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation, |
|
| 95 |
/// \ref goldberg97efficient, \ref bunnagel98efficient. |
|
| 96 |
/// It is a highly efficient primal-dual solution method, which |
|
| 95 | 97 |
/// can be viewed as the generalization of the \ref Preflow |
| 96 | 98 |
/// "preflow push-relabel" algorithm for the maximum flow problem. |
| 97 | 99 |
/// |
| 98 | 100 |
/// Most of the parameters of the problem (except for the digraph) |
| 99 | 101 |
/// can be given using separate functions, and the algorithm can be |
| 100 | 102 |
/// executed using the \ref run() function. If some parameters are not |
| 101 | 103 |
/// specified, then default values will be used. |
| 102 | 104 |
/// |
| 103 | 105 |
/// \tparam GR The digraph type the algorithm runs on. |
| 104 | 106 |
/// \tparam V The number type used for flow amounts, capacity bounds |
| 105 | 107 |
/// and supply values in the algorithm. By default it is \c int. |
| 106 | 108 |
/// \tparam C The number type used for costs and potentials in the |
0 comments (0 inline)