Changeset 812:4b1b378823dc in lemon-main
- Timestamp:
- 11/12/09 23:49:05 (15 years ago)
- Branch:
- default
- Phase:
- public
- Rebase:
- 30323866356537663935353430623930626534653939636630353730643832346265623131623731
- Location:
- lemon
- Files:
-
- 3 edited
-
capacity_scaling.h (modified) (7 diffs)
-
cost_scaling.h (modified) (7 diffs)
-
network_simplex.h (modified) (5 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r811 r812 36 36 /// Default traits class of CapacityScaling algorithm. 37 37 /// \tparam GR Digraph type. 38 /// \tparam V The valuetype used for flow amounts, capacity bounds38 /// \tparam V The number type used for flow amounts, capacity bounds 39 39 /// and supply values. By default it is \c int. 40 /// \tparam C The valuetype used for costs and potentials.40 /// \tparam C The number type used for costs and potentials. 41 41 /// By default it is the same as \c V. 42 42 template <typename GR, typename V = int, typename C = V> … … 76 76 /// 77 77 /// \tparam GR The digraph type the algorithm runs on. 78 /// \tparam V The valuetype used for flow amounts, capacity bounds78 /// \tparam V The number type used for flow amounts, capacity bounds 79 79 /// and supply values in the algorithm. By default it is \c int. 80 /// \tparam C The valuetype used for costs and potentials in the80 /// \tparam C The number type used for costs and potentials in the 81 81 /// algorithm. By default it is the same as \c V. 82 82 /// 83 /// \warning Both valuetypes must be signed and all input data must83 /// \warning Both number types must be signed and all input data must 84 84 /// be integer. 85 85 /// \warning This algorithm does not support negative costs for such … … 123 123 /// The digraph contains an arc of negative cost and infinite 124 124 /// upper bound. It means that the objective function is unbounded 125 /// on that arc, however note that it could actually be bounded125 /// on that arc, however, note that it could actually be bounded 126 126 /// over the feasible flows, but this algroithm cannot handle 127 127 /// these cases. … … 308 308 std::numeric_limits<Value>::max()) 309 309 { 310 // Check the valuetypes310 // Check the number types 311 311 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, 312 312 "The flow type of CapacityScaling must be signed"); … … 412 412 /// If it is not used before calling \ref run(), the upper bounds 413 413 /// will be set to \ref INF on all arcs (i.e. the flow value will be 414 /// unbounded from above on each arc).414 /// unbounded from above). 415 415 /// 416 416 /// \param map An arc map storing the upper bounds. … … 515 515 /// \ref reset() is called, thus only the modified parameters 516 516 /// have to be set again. See \ref reset() for examples. 517 /// However the underlying digraph must not be modified after this517 /// However, the underlying digraph must not be modified after this 518 518 /// class have been constructed, since it copies and extends the graph. 519 519 /// … … 528 528 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 529 529 /// and infinite upper bound. It means that the objective function 530 /// is unbounded on that arc, however note that it could actually be530 /// is unbounded on that arc, however, note that it could actually be 531 531 /// bounded over the feasible flows, but this algroithm cannot handle 532 532 /// these cases. -
lemon/cost_scaling.h
r810 r812 41 41 /// Default traits class of CostScaling algorithm. 42 42 /// \tparam GR Digraph type. 43 /// \tparam V The valuetype used for flow amounts, capacity bounds43 /// \tparam V The number type used for flow amounts, capacity bounds 44 44 /// and supply values. By default it is \c int. 45 /// \tparam C The valuetype used for costs and potentials.45 /// \tparam C The number type used for costs and potentials. 46 46 /// By default it is the same as \c V. 47 47 #ifdef DOXYGEN … … 102 102 /// 103 103 /// \tparam GR The digraph type the algorithm runs on. 104 /// \tparam V The valuetype used for flow amounts, capacity bounds104 /// \tparam V The number type used for flow amounts, capacity bounds 105 105 /// and supply values in the algorithm. By default it is \c int. 106 /// \tparam C The valuetype used for costs and potentials in the106 /// \tparam C The number type used for costs and potentials in the 107 107 /// algorithm. By default it is the same as \c V. 108 108 /// 109 /// \warning Both valuetypes must be signed and all input data must109 /// \warning Both number types must be signed and all input data must 110 110 /// be integer. 111 111 /// \warning This algorithm does not support negative costs for such … … 158 158 /// The digraph contains an arc of negative cost and infinite 159 159 /// upper bound. It means that the objective function is unbounded 160 /// on that arc, however note that it could actually be bounded160 /// on that arc, however, note that it could actually be bounded 161 161 /// over the feasible flows, but this algroithm cannot handle 162 162 /// these cases. … … 326 326 std::numeric_limits<Value>::max()) 327 327 { 328 // Check the valuetypes328 // Check the number types 329 329 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, 330 330 "The flow type of CostScaling must be signed"); … … 434 434 /// If it is not used before calling \ref run(), the upper bounds 435 435 /// will be set to \ref INF on all arcs (i.e. the flow value will be 436 /// unbounded from above on each arc).436 /// unbounded from above). 437 437 /// 438 438 /// \param map An arc map storing the upper bounds. … … 550 550 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 551 551 /// and infinite upper bound. It means that the objective function 552 /// is unbounded on that arc, however note that it could actually be552 /// is unbounded on that arc, however, note that it could actually be 553 553 /// bounded over the feasible flows, but this algroithm cannot handle 554 554 /// these cases. … … 572 572 /// used, all the parameters given before are kept for the next 573 573 /// \ref run() call. 574 /// However the underlying digraph must not be modified after this574 /// However, the underlying digraph must not be modified after this 575 575 /// class have been constructed, since it copies and extends the graph. 576 576 /// -
lemon/network_simplex.h
r811 r812 44 44 /// \ref amo93networkflows, \ref dantzig63linearprog, 45 45 /// \ref kellyoneill91netsimplex. 46 /// This algorithm is a specialized version of the linear programming47 /// simplex method directly for the minimum cost flow problem.48 /// It is one of the most efficient solution methods.46 /// This algorithm is a highly efficient specialized version of the 47 /// linear programming simplex method directly for the minimum cost 48 /// flow problem. 49 49 /// 50 /// In general this classis the fastest implementation available51 /// in LEMON for th e minimum cost flowproblem.52 /// Moreover it supports both directions of the supply/demand inequality50 /// In general, %NetworkSimplex is the fastest implementation available 51 /// in LEMON for this problem. 52 /// Moreover, it supports both directions of the supply/demand inequality 53 53 /// constraints. For more information, see \ref SupplyType. 54 54 /// … … 59 59 /// 60 60 /// \tparam GR The digraph type the algorithm runs on. 61 /// \tparam V The valuetype used for flow amounts, capacity bounds61 /// \tparam V The number type used for flow amounts, capacity bounds 62 62 /// and supply values in the algorithm. By default, it is \c int. 63 /// \tparam C The valuetype used for costs and potentials in the63 /// \tparam C The number type used for costs and potentials in the 64 64 /// algorithm. By default, it is the same as \c V. 65 65 /// 66 /// \warning Both valuetypes must be signed and all input data must66 /// \warning Both number types must be signed and all input data must 67 67 /// be integer. 68 68 /// … … 127 127 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which 128 128 /// proved to be the most efficient and the most robust on various 129 /// test inputs according to our benchmark tests.129 /// test inputs. 130 130 /// However, another pivot rule can be selected using the \ref run() 131 131 /// function with the proper parameter. … … 638 638 std::numeric_limits<Value>::infinity() : MAX) 639 639 { 640 // Check the valuetypes640 // Check the number types 641 641 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, 642 642 "The flow type of NetworkSimplex must be signed"); … … 730 730 /// If it is not used before calling \ref run(), the upper bounds 731 731 /// will be set to \ref INF on all arcs (i.e. the flow value will be 732 /// unbounded from above on each arc).732 /// unbounded from above). 733 733 /// 734 734 /// \param map An arc map storing the upper bounds.
Note: See TracChangeset
for help on using the changeset viewer.
