r807:78071e00de00
Thu, 12 Nov 2009 23:27:21
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -28,12 +28,39 @@ |
| 28 | 28 |
#include <limits> |
| 29 | 29 |
#include <lemon/core.h> |
| 30 | 30 |
#include <lemon/bin_heap.h> |
| 31 | 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 |
/// @{
|
| 36 | 63 |
|
| 37 | 64 |
/// \brief Implementation of the Capacity Scaling algorithm for |
| 38 | 65 |
/// finding a \ref min_cost_flow "minimum cost flow". |
| 39 | 66 |
/// |
| ... | ... |
@@ -54,21 +81,34 @@ |
| 54 | 81 |
/// algorithm. By default it is the same as \c V. |
| 55 | 82 |
/// |
| 56 | 83 |
/// \warning Both value types must be signed and all input data must |
| 57 | 84 |
/// be integer. |
| 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: |
| 71 | 111 |
|
| 72 | 112 |
/// \brief Problem type constants for the \c run() function. |
| 73 | 113 |
/// |
| 74 | 114 |
/// Enum type containing the problem type constants that can be |
| ... | ... |
@@ -89,14 +129,12 @@ |
| 89 | 129 |
}; |
| 90 | 130 |
|
| 91 | 131 |
private: |
| 92 | 132 |
|
| 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; |
| 99 | 137 |
typedef std::vector<Value> ValueVector; |
| 100 | 138 |
typedef std::vector<Cost> CostVector; |
| 101 | 139 |
|
| 102 | 140 |
private: |
| ... | ... |
@@ -152,15 +190,12 @@ |
| 152 | 190 |
// Special implementation of the Dijkstra algorithm for finding |
| 153 | 191 |
// shortest paths in the residual network of the digraph with |
| 154 | 192 |
// respect to the reduced arc costs and modifying the node |
| 155 | 193 |
// potentials according to the found distance labels. |
| 156 | 194 |
class ResidualDijkstra |
| 157 | 195 |
{
|
| 158 |
typedef RangeMap<int> HeapCrossRef; |
|
| 159 |
typedef BinHeap<Cost, HeapCrossRef> Heap; |
|
| 160 |
|
|
| 161 | 196 |
private: |
| 162 | 197 |
|
| 163 | 198 |
int _node_num; |
| 164 | 199 |
const IntVector &_first_out; |
| 165 | 200 |
const IntVector &_target; |
| 166 | 201 |
const CostVector &_cost; |
| ... | ... |
@@ -179,13 +214,13 @@ |
| 179 | 214 |
_target(cs._target), _cost(cs._cost), _res_cap(cs._res_cap), |
| 180 | 215 |
_excess(cs._excess), _pi(cs._pi), _pred(cs._pred), |
| 181 | 216 |
_dist(cs._node_num) |
| 182 | 217 |
{}
|
| 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); |
| 188 | 223 |
_pred[s] = -1; |
| 189 | 224 |
_proc_nodes.clear(); |
| 190 | 225 |
|
| 191 | 226 |
// Process nodes |
| ... | ... |
@@ -230,12 +265,38 @@ |
| 230 | 265 |
} |
| 231 | 266 |
|
| 232 | 267 |
}; //class ResidualDijkstra |
| 233 | 268 |
|
| 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 |
/// |
| 238 | 299 |
/// The constructor of the class. |
| 239 | 300 |
/// |
| 240 | 301 |
/// \param graph The digraph the algorithm runs on. |
| 241 | 302 |
CapacityScaling(const GR& graph) : |
| ... | ... |
@@ -428,12 +489,13 @@ |
| 428 | 489 |
return *this; |
| 429 | 490 |
} |
| 430 | 491 |
|
| 431 | 492 |
/// @} |
| 432 | 493 |
|
| 433 | 494 |
/// \name Execution control |
| 495 |
/// The algorithm can be executed using \ref run(). |
|
| 434 | 496 |
|
| 435 | 497 |
/// @{
|
| 436 | 498 |
|
| 437 | 499 |
/// \brief Run the algorithm. |
| 438 | 500 |
/// |
| 439 | 501 |
/// This function runs the algorithm. |
| ... | ... |
@@ -744,13 +806,13 @@ |
| 744 | 806 |
|
| 745 | 807 |
return pt; |
| 746 | 808 |
} |
| 747 | 809 |
|
| 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; |
| 753 | 815 |
int factor = 4; |
| 754 | 816 |
ResidualDijkstra _dijkstra(*this); |
| 755 | 817 |
while (true) {
|
| 756 | 818 |
// Saturate all arcs not satisfying the optimality condition |
0 comments (0 inline)