r873:78071e00de00
Thu, 12 Nov 2009 23:27:21
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -32,4 +32,31 @@ |
| 32 | 32 |
namespace lemon {
|
| 33 | 33 |
|
| 34 |
/// \brief Default traits class of CapacityScaling algorithm. |
|
| 35 |
/// |
|
| 36 |
/// Default traits class of CapacityScaling algorithm. |
|
| 37 |
/// \tparam GR Digraph type. |
|
| 38 |
/// \tparam V The value type used for flow amounts, capacity bounds |
|
| 39 |
/// and supply values. By default it is \c int. |
|
| 40 |
/// \tparam C The value type used for costs and potentials. |
|
| 41 |
/// By default it is the same as \c V. |
|
| 42 |
template <typename GR, typename V = int, typename C = V> |
|
| 43 |
struct CapacityScalingDefaultTraits |
|
| 44 |
{
|
|
| 45 |
/// The type of the digraph |
|
| 46 |
typedef GR Digraph; |
|
| 47 |
/// The type of the flow amounts, capacity bounds and supply values |
|
| 48 |
typedef V Value; |
|
| 49 |
/// The type of the arc costs |
|
| 50 |
typedef C Cost; |
|
| 51 |
|
|
| 52 |
/// \brief The type of the heap used for internal Dijkstra computations. |
|
| 53 |
/// |
|
| 54 |
/// The type of the heap used for internal Dijkstra computations. |
|
| 55 |
/// It must conform to the \ref lemon::concepts::Heap "Heap" concept, |
|
| 56 |
/// its priority type must be \c Cost and its cross reference type |
|
| 57 |
/// must be \ref RangeMap "RangeMap<int>". |
|
| 58 |
typedef BinHeap<Cost, RangeMap<int> > Heap; |
|
| 59 |
}; |
|
| 60 |
|
|
| 34 | 61 |
/// \addtogroup min_cost_flow_algs |
| 35 | 62 |
/// @{
|
| ... | ... |
@@ -58,13 +85,26 @@ |
| 58 | 85 |
/// \warning This algorithm does not support negative costs for such |
| 59 | 86 |
/// arcs that have infinite upper bound. |
| 60 |
|
|
| 87 |
#ifdef DOXYGEN |
|
| 88 |
template <typename GR, typename V, typename C, typename TR> |
|
| 89 |
#else |
|
| 90 |
template < typename GR, typename V = int, typename C = V, |
|
| 91 |
typename TR = CapacityScalingDefaultTraits<GR, V, C> > |
|
| 92 |
#endif |
|
| 61 | 93 |
class CapacityScaling |
| 62 | 94 |
{
|
| 63 | 95 |
public: |
| 64 | 96 |
|
| 97 |
/// The type of the digraph |
|
| 98 |
typedef typename TR::Digraph Digraph; |
|
| 65 | 99 |
/// The type of the flow amounts, capacity bounds and supply values |
| 66 |
typedef |
|
| 100 |
typedef typename TR::Value Value; |
|
| 67 | 101 |
/// The type of the arc costs |
| 68 |
typedef |
|
| 102 |
typedef typename TR::Cost Cost; |
|
| 103 |
|
|
| 104 |
/// The type of the heap used for internal Dijkstra computations |
|
| 105 |
typedef typename TR::Heap Heap; |
|
| 106 |
|
|
| 107 |
/// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm |
|
| 108 |
typedef TR Traits; |
|
| 69 | 109 |
|
| 70 | 110 |
public: |
| ... | ... |
@@ -93,6 +133,4 @@ |
| 93 | 133 |
TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
| 94 | 134 |
|
| 95 |
typedef std::vector<Arc> ArcVector; |
|
| 96 |
typedef std::vector<Node> NodeVector; |
|
| 97 | 135 |
typedef std::vector<int> IntVector; |
| 98 | 136 |
typedef std::vector<bool> BoolVector; |
| ... | ... |
@@ -156,7 +194,4 @@ |
| 156 | 194 |
class ResidualDijkstra |
| 157 | 195 |
{
|
| 158 |
typedef RangeMap<int> HeapCrossRef; |
|
| 159 |
typedef BinHeap<Cost, HeapCrossRef> Heap; |
|
| 160 |
|
|
| 161 | 196 |
private: |
| 162 | 197 |
|
| ... | ... |
@@ -183,5 +218,5 @@ |
| 183 | 218 |
|
| 184 | 219 |
int run(int s, Value delta = 1) {
|
| 185 |
|
|
| 220 |
RangeMap<int> heap_cross_ref(_node_num, Heap::PRE_HEAP); |
|
| 186 | 221 |
Heap heap(heap_cross_ref); |
| 187 | 222 |
heap.push(s, 0); |
| ... | ... |
@@ -234,4 +269,30 @@ |
| 234 | 269 |
public: |
| 235 | 270 |
|
| 271 |
/// \name Named Template Parameters |
|
| 272 |
/// @{
|
|
| 273 |
|
|
| 274 |
template <typename T> |
|
| 275 |
struct SetHeapTraits : public Traits {
|
|
| 276 |
typedef T Heap; |
|
| 277 |
}; |
|
| 278 |
|
|
| 279 |
/// \brief \ref named-templ-param "Named parameter" for setting |
|
| 280 |
/// \c Heap type. |
|
| 281 |
/// |
|
| 282 |
/// \ref named-templ-param "Named parameter" for setting \c Heap |
|
| 283 |
/// type, which is used for internal Dijkstra computations. |
|
| 284 |
/// It must conform to the \ref lemon::concepts::Heap "Heap" concept, |
|
| 285 |
/// its priority type must be \c Cost and its cross reference type |
|
| 286 |
/// must be \ref RangeMap "RangeMap<int>". |
|
| 287 |
template <typename T> |
|
| 288 |
struct SetHeap |
|
| 289 |
: public CapacityScaling<GR, V, C, SetHeapTraits<T> > {
|
|
| 290 |
typedef CapacityScaling<GR, V, C, SetHeapTraits<T> > Create; |
|
| 291 |
}; |
|
| 292 |
|
|
| 293 |
/// @} |
|
| 294 |
|
|
| 295 |
public: |
|
| 296 |
|
|
| 236 | 297 |
/// \brief Constructor. |
| 237 | 298 |
/// |
| ... | ... |
@@ -432,4 +493,5 @@ |
| 432 | 493 |
|
| 433 | 494 |
/// \name Execution control |
| 495 |
/// The algorithm can be executed using \ref run(). |
|
| 434 | 496 |
|
| 435 | 497 |
/// @{
|
| ... | ... |
@@ -748,5 +810,5 @@ |
| 748 | 810 |
// Execute the capacity scaling algorithm |
| 749 | 811 |
ProblemType startWithScaling() {
|
| 750 |
// |
|
| 812 |
// Perform capacity scaling phases |
|
| 751 | 813 |
int s, t; |
| 752 | 814 |
int phase_cnt = 0; |
0 comments (0 inline)