[2440] | 1 | /* -*- C++ -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library |
---|
| 4 | * |
---|
| 5 | * Copyright (C) 2003-2007 |
---|
| 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
| 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
| 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
| 19 | #ifndef LEMON_CAPACITY_SCALING_H |
---|
| 20 | #define LEMON_CAPACITY_SCALING_H |
---|
| 21 | |
---|
| 22 | /// \ingroup min_cost_flow |
---|
| 23 | /// |
---|
| 24 | /// \file |
---|
| 25 | /// \brief The capacity scaling algorithm for finding a minimum cost |
---|
| 26 | /// flow. |
---|
| 27 | |
---|
| 28 | #include <vector> |
---|
| 29 | #include <lemon/dijkstra.h> |
---|
| 30 | #include <lemon/graph_adaptor.h> |
---|
| 31 | |
---|
| 32 | #define WITH_SCALING |
---|
| 33 | |
---|
[2471] | 34 | #ifdef WITH_SCALING |
---|
| 35 | #define SCALING_FACTOR 2 |
---|
| 36 | #endif |
---|
| 37 | |
---|
[2457] | 38 | //#define _DEBUG_ITER_ |
---|
| 39 | |
---|
[2440] | 40 | namespace lemon { |
---|
| 41 | |
---|
| 42 | /// \addtogroup min_cost_flow |
---|
| 43 | /// @{ |
---|
| 44 | |
---|
| 45 | /// \brief Implementation of the capacity scaling version of the |
---|
[2457] | 46 | /// successive shortest path algorithm for finding a minimum cost flow. |
---|
[2440] | 47 | /// |
---|
| 48 | /// \ref lemon::CapacityScaling "CapacityScaling" implements a |
---|
| 49 | /// capacity scaling algorithm for finding a minimum cost flow. |
---|
| 50 | /// |
---|
| 51 | /// \param Graph The directed graph type the algorithm runs on. |
---|
| 52 | /// \param LowerMap The type of the lower bound map. |
---|
| 53 | /// \param CapacityMap The type of the capacity (upper bound) map. |
---|
| 54 | /// \param CostMap The type of the cost (length) map. |
---|
| 55 | /// \param SupplyMap The type of the supply map. |
---|
| 56 | /// |
---|
| 57 | /// \warning |
---|
| 58 | /// - Edge capacities and costs should be nonnegative integers. |
---|
| 59 | /// However \c CostMap::Value should be signed type. |
---|
| 60 | /// - Supply values should be integers. |
---|
| 61 | /// - \c LowerMap::Value must be convertible to |
---|
| 62 | /// \c CapacityMap::Value and \c CapacityMap::Value must be |
---|
| 63 | /// convertible to \c SupplyMap::Value. |
---|
| 64 | /// |
---|
| 65 | /// \author Peter Kovacs |
---|
| 66 | |
---|
| 67 | template < typename Graph, |
---|
| 68 | typename LowerMap = typename Graph::template EdgeMap<int>, |
---|
| 69 | typename CapacityMap = LowerMap, |
---|
| 70 | typename CostMap = typename Graph::template EdgeMap<int>, |
---|
| 71 | typename SupplyMap = typename Graph::template NodeMap |
---|
| 72 | <typename CapacityMap::Value> > |
---|
| 73 | class CapacityScaling |
---|
| 74 | { |
---|
| 75 | typedef typename Graph::Node Node; |
---|
| 76 | typedef typename Graph::NodeIt NodeIt; |
---|
| 77 | typedef typename Graph::Edge Edge; |
---|
| 78 | typedef typename Graph::EdgeIt EdgeIt; |
---|
| 79 | typedef typename Graph::InEdgeIt InEdgeIt; |
---|
| 80 | typedef typename Graph::OutEdgeIt OutEdgeIt; |
---|
| 81 | |
---|
| 82 | typedef typename LowerMap::Value Lower; |
---|
| 83 | typedef typename CapacityMap::Value Capacity; |
---|
| 84 | typedef typename CostMap::Value Cost; |
---|
| 85 | typedef typename SupplyMap::Value Supply; |
---|
| 86 | typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap; |
---|
| 87 | typedef typename Graph::template NodeMap<Supply> SupplyRefMap; |
---|
| 88 | |
---|
| 89 | typedef ResGraphAdaptor< const Graph, Capacity, |
---|
| 90 | CapacityRefMap, CapacityRefMap > ResGraph; |
---|
| 91 | typedef typename ResGraph::Node ResNode; |
---|
| 92 | typedef typename ResGraph::NodeIt ResNodeIt; |
---|
| 93 | typedef typename ResGraph::Edge ResEdge; |
---|
| 94 | typedef typename ResGraph::EdgeIt ResEdgeIt; |
---|
| 95 | |
---|
| 96 | public: |
---|
| 97 | |
---|
| 98 | /// \brief The type of the flow map. |
---|
| 99 | typedef CapacityRefMap FlowMap; |
---|
| 100 | /// \brief The type of the potential map. |
---|
| 101 | typedef typename Graph::template NodeMap<Cost> PotentialMap; |
---|
| 102 | |
---|
| 103 | protected: |
---|
| 104 | |
---|
| 105 | /// \brief Map adaptor class for handling reduced edge costs. |
---|
| 106 | class ReducedCostMap : public MapBase<ResEdge, Cost> |
---|
| 107 | { |
---|
| 108 | private: |
---|
| 109 | |
---|
| 110 | const ResGraph &gr; |
---|
| 111 | const CostMap &cost_map; |
---|
| 112 | const PotentialMap &pot_map; |
---|
| 113 | |
---|
| 114 | public: |
---|
| 115 | |
---|
| 116 | typedef typename MapBase<ResEdge, Cost>::Value Value; |
---|
| 117 | typedef typename MapBase<ResEdge, Cost>::Key Key; |
---|
| 118 | |
---|
| 119 | ReducedCostMap( const ResGraph &_gr, |
---|
| 120 | const CostMap &_cost, |
---|
| 121 | const PotentialMap &_pot ) : |
---|
| 122 | gr(_gr), cost_map(_cost), pot_map(_pot) {} |
---|
| 123 | |
---|
| 124 | Value operator[](const Key &e) const { |
---|
| 125 | return ResGraph::forward(e) ? |
---|
| 126 | cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)] : |
---|
| 127 | -cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)]; |
---|
| 128 | } |
---|
| 129 | |
---|
| 130 | }; //class ReducedCostMap |
---|
| 131 | |
---|
| 132 | /// \brief Map adaptor for \ref lemon::Dijkstra "Dijkstra" class to |
---|
| 133 | /// update node potentials. |
---|
| 134 | class PotentialUpdateMap : public MapBase<ResNode, Cost> |
---|
| 135 | { |
---|
| 136 | private: |
---|
| 137 | |
---|
| 138 | PotentialMap *pot; |
---|
| 139 | typedef std::pair<ResNode, Cost> Pair; |
---|
| 140 | std::vector<Pair> data; |
---|
| 141 | |
---|
| 142 | public: |
---|
| 143 | |
---|
| 144 | typedef typename MapBase<ResNode, Cost>::Value Value; |
---|
| 145 | typedef typename MapBase<ResNode, Cost>::Key Key; |
---|
| 146 | |
---|
| 147 | void potentialMap(PotentialMap &_pot) { |
---|
| 148 | pot = &_pot; |
---|
| 149 | } |
---|
| 150 | |
---|
| 151 | void init() { |
---|
| 152 | data.clear(); |
---|
| 153 | } |
---|
| 154 | |
---|
| 155 | void set(const Key &n, const Value &v) { |
---|
| 156 | data.push_back(Pair(n, v)); |
---|
| 157 | } |
---|
| 158 | |
---|
| 159 | void update() { |
---|
| 160 | Cost val = data[data.size()-1].second; |
---|
| 161 | for (int i = 0; i < data.size()-1; ++i) |
---|
| 162 | (*pot)[data[i].first] += val - data[i].second; |
---|
| 163 | } |
---|
| 164 | |
---|
| 165 | }; //class PotentialUpdateMap |
---|
| 166 | |
---|
| 167 | #ifdef WITH_SCALING |
---|
| 168 | /// \brief Map adaptor class for identifing deficit nodes. |
---|
| 169 | class DeficitBoolMap : public MapBase<ResNode, bool> |
---|
| 170 | { |
---|
| 171 | private: |
---|
| 172 | |
---|
| 173 | const SupplyRefMap &imb; |
---|
| 174 | const Capacity δ |
---|
| 175 | |
---|
| 176 | public: |
---|
| 177 | |
---|
| 178 | DeficitBoolMap(const SupplyRefMap &_imb, const Capacity &_delta) : |
---|
| 179 | imb(_imb), delta(_delta) {} |
---|
| 180 | |
---|
| 181 | bool operator[](const ResNode &n) const { |
---|
| 182 | return imb[n] <= -delta; |
---|
| 183 | } |
---|
| 184 | |
---|
| 185 | }; //class DeficitBoolMap |
---|
| 186 | |
---|
| 187 | /// \brief Map adaptor class for filtering edges with at least |
---|
| 188 | /// \c delta residual capacity |
---|
| 189 | class DeltaFilterMap : public MapBase<ResEdge, bool> |
---|
| 190 | { |
---|
| 191 | private: |
---|
| 192 | |
---|
| 193 | const ResGraph &gr; |
---|
| 194 | const Capacity δ |
---|
| 195 | |
---|
| 196 | public: |
---|
| 197 | |
---|
| 198 | typedef typename MapBase<ResEdge, Cost>::Value Value; |
---|
| 199 | typedef typename MapBase<ResEdge, Cost>::Key Key; |
---|
| 200 | |
---|
| 201 | DeltaFilterMap(const ResGraph &_gr, const Capacity &_delta) : |
---|
| 202 | gr(_gr), delta(_delta) {} |
---|
| 203 | |
---|
| 204 | Value operator[](const Key &e) const { |
---|
| 205 | return gr.rescap(e) >= delta; |
---|
| 206 | } |
---|
| 207 | |
---|
| 208 | }; //class DeltaFilterMap |
---|
| 209 | |
---|
| 210 | typedef EdgeSubGraphAdaptor<const ResGraph, const DeltaFilterMap> |
---|
| 211 | DeltaResGraph; |
---|
| 212 | |
---|
| 213 | /// \brief Traits class for \ref lemon::Dijkstra "Dijkstra" class. |
---|
| 214 | class ResDijkstraTraits : |
---|
| 215 | public DijkstraDefaultTraits<DeltaResGraph, ReducedCostMap> |
---|
| 216 | { |
---|
| 217 | public: |
---|
| 218 | |
---|
| 219 | typedef PotentialUpdateMap DistMap; |
---|
| 220 | |
---|
| 221 | static DistMap *createDistMap(const DeltaResGraph&) { |
---|
| 222 | return new DistMap(); |
---|
| 223 | } |
---|
| 224 | |
---|
| 225 | }; //class ResDijkstraTraits |
---|
| 226 | |
---|
| 227 | #else //WITHOUT_CAPACITY_SCALING |
---|
| 228 | /// \brief Map adaptor class for identifing deficit nodes. |
---|
| 229 | class DeficitBoolMap : public MapBase<ResNode, bool> |
---|
| 230 | { |
---|
| 231 | private: |
---|
| 232 | |
---|
| 233 | const SupplyRefMap &imb; |
---|
| 234 | |
---|
| 235 | public: |
---|
| 236 | |
---|
| 237 | DeficitBoolMap(const SupplyRefMap &_imb) : imb(_imb) {} |
---|
| 238 | |
---|
| 239 | bool operator[](const ResNode &n) const { |
---|
| 240 | return imb[n] < 0; |
---|
| 241 | } |
---|
| 242 | |
---|
| 243 | }; //class DeficitBoolMap |
---|
| 244 | |
---|
| 245 | /// \brief Traits class for \ref lemon::Dijkstra "Dijkstra" class. |
---|
| 246 | class ResDijkstraTraits : |
---|
| 247 | public DijkstraDefaultTraits<ResGraph, ReducedCostMap> |
---|
| 248 | { |
---|
| 249 | public: |
---|
| 250 | |
---|
| 251 | typedef PotentialUpdateMap DistMap; |
---|
| 252 | |
---|
| 253 | static DistMap *createDistMap(const ResGraph&) { |
---|
| 254 | return new DistMap(); |
---|
| 255 | } |
---|
| 256 | |
---|
| 257 | }; //class ResDijkstraTraits |
---|
| 258 | #endif |
---|
| 259 | |
---|
| 260 | protected: |
---|
| 261 | |
---|
| 262 | /// \brief The directed graph the algorithm runs on. |
---|
| 263 | const Graph &graph; |
---|
| 264 | /// \brief The original lower bound map. |
---|
| 265 | const LowerMap *lower; |
---|
| 266 | /// \brief The modified capacity map. |
---|
| 267 | CapacityRefMap capacity; |
---|
| 268 | /// \brief The cost map. |
---|
| 269 | const CostMap &cost; |
---|
| 270 | /// \brief The modified supply map. |
---|
| 271 | SupplyRefMap supply; |
---|
| 272 | /// \brief The sum of supply values equals zero. |
---|
| 273 | bool valid_supply; |
---|
| 274 | |
---|
| 275 | /// \brief The edge map of the current flow. |
---|
| 276 | FlowMap flow; |
---|
| 277 | /// \brief The potential node map. |
---|
| 278 | PotentialMap potential; |
---|
| 279 | /// \brief The residual graph. |
---|
| 280 | ResGraph res_graph; |
---|
| 281 | /// \brief The reduced cost map. |
---|
| 282 | ReducedCostMap red_cost; |
---|
| 283 | |
---|
| 284 | /// \brief The imbalance map. |
---|
| 285 | SupplyRefMap imbalance; |
---|
| 286 | /// \brief The excess nodes. |
---|
| 287 | std::vector<ResNode> excess_nodes; |
---|
| 288 | /// \brief The index of the next excess node. |
---|
| 289 | int next_node; |
---|
| 290 | |
---|
| 291 | #ifdef WITH_SCALING |
---|
| 292 | typedef Dijkstra<DeltaResGraph, ReducedCostMap, ResDijkstraTraits> |
---|
| 293 | ResDijkstra; |
---|
| 294 | /// \brief \ref lemon::Dijkstra "Dijkstra" class for finding |
---|
| 295 | /// shortest paths in the residual graph with respect to the |
---|
| 296 | /// reduced edge costs. |
---|
| 297 | ResDijkstra dijkstra; |
---|
| 298 | |
---|
| 299 | /// \brief The delta parameter used for capacity scaling. |
---|
| 300 | Capacity delta; |
---|
| 301 | /// \brief Edge filter map. |
---|
| 302 | DeltaFilterMap delta_filter; |
---|
| 303 | /// \brief The delta residual graph. |
---|
| 304 | DeltaResGraph dres_graph; |
---|
| 305 | /// \brief Map for identifing deficit nodes. |
---|
| 306 | DeficitBoolMap delta_deficit; |
---|
| 307 | |
---|
[2457] | 308 | /// \brief The deficit nodes. |
---|
| 309 | std::vector<ResNode> deficit_nodes; |
---|
| 310 | |
---|
[2440] | 311 | #else //WITHOUT_CAPACITY_SCALING |
---|
| 312 | typedef Dijkstra<ResGraph, ReducedCostMap, ResDijkstraTraits> |
---|
| 313 | ResDijkstra; |
---|
| 314 | /// \brief \ref lemon::Dijkstra "Dijkstra" class for finding |
---|
| 315 | /// shortest paths in the residual graph with respect to the |
---|
| 316 | /// reduced edge costs. |
---|
| 317 | ResDijkstra dijkstra; |
---|
| 318 | /// \brief Map for identifing deficit nodes. |
---|
| 319 | DeficitBoolMap has_deficit; |
---|
| 320 | #endif |
---|
| 321 | |
---|
| 322 | /// \brief Pred map for the \ref lemon::Dijkstra "Dijkstra" class. |
---|
| 323 | typename ResDijkstra::PredMap pred; |
---|
| 324 | /// \brief Dist map for the \ref lemon::Dijkstra "Dijkstra" class to |
---|
| 325 | /// update node potentials. |
---|
| 326 | PotentialUpdateMap updater; |
---|
| 327 | |
---|
| 328 | public : |
---|
| 329 | |
---|
| 330 | /// \brief General constructor of the class (with lower bounds). |
---|
| 331 | /// |
---|
| 332 | /// General constructor of the class (with lower bounds). |
---|
| 333 | /// |
---|
| 334 | /// \param _graph The directed graph the algorithm runs on. |
---|
| 335 | /// \param _lower The lower bounds of the edges. |
---|
| 336 | /// \param _capacity The capacities (upper bounds) of the edges. |
---|
| 337 | /// \param _cost The cost (length) values of the edges. |
---|
| 338 | /// \param _supply The supply values of the nodes (signed). |
---|
| 339 | CapacityScaling( const Graph &_graph, |
---|
| 340 | const LowerMap &_lower, |
---|
| 341 | const CapacityMap &_capacity, |
---|
| 342 | const CostMap &_cost, |
---|
| 343 | const SupplyMap &_supply ) : |
---|
| 344 | graph(_graph), lower(&_lower), capacity(_graph), cost(_cost), |
---|
| 345 | supply(_graph), flow(_graph, 0), potential(_graph, 0), |
---|
| 346 | res_graph(_graph, capacity, flow), |
---|
| 347 | red_cost(res_graph, cost, potential), imbalance(_graph), |
---|
| 348 | #ifdef WITH_SCALING |
---|
| 349 | delta(0), delta_filter(res_graph, delta), |
---|
| 350 | dres_graph(res_graph, delta_filter), |
---|
| 351 | dijkstra(dres_graph, red_cost), pred(dres_graph), |
---|
| 352 | delta_deficit(imbalance, delta) |
---|
| 353 | #else //WITHOUT_CAPACITY_SCALING |
---|
| 354 | dijkstra(res_graph, red_cost), pred(res_graph), |
---|
| 355 | has_deficit(imbalance) |
---|
| 356 | #endif |
---|
| 357 | { |
---|
| 358 | // Removing nonzero lower bounds |
---|
| 359 | capacity = subMap(_capacity, _lower); |
---|
| 360 | Supply sum = 0; |
---|
| 361 | for (NodeIt n(graph); n != INVALID; ++n) { |
---|
| 362 | Supply s = _supply[n]; |
---|
| 363 | for (InEdgeIt e(graph, n); e != INVALID; ++e) |
---|
| 364 | s += _lower[e]; |
---|
| 365 | for (OutEdgeIt e(graph, n); e != INVALID; ++e) |
---|
| 366 | s -= _lower[e]; |
---|
[2507] | 367 | supply[n] = s; |
---|
[2440] | 368 | sum += s; |
---|
| 369 | } |
---|
| 370 | valid_supply = sum == 0; |
---|
| 371 | } |
---|
| 372 | |
---|
| 373 | /// \brief General constructor of the class (without lower bounds). |
---|
| 374 | /// |
---|
| 375 | /// General constructor of the class (without lower bounds). |
---|
| 376 | /// |
---|
| 377 | /// \param _graph The directed graph the algorithm runs on. |
---|
| 378 | /// \param _capacity The capacities (upper bounds) of the edges. |
---|
| 379 | /// \param _cost The cost (length) values of the edges. |
---|
| 380 | /// \param _supply The supply values of the nodes (signed). |
---|
| 381 | CapacityScaling( const Graph &_graph, |
---|
| 382 | const CapacityMap &_capacity, |
---|
| 383 | const CostMap &_cost, |
---|
| 384 | const SupplyMap &_supply ) : |
---|
| 385 | graph(_graph), lower(NULL), capacity(_capacity), cost(_cost), |
---|
| 386 | supply(_supply), flow(_graph, 0), potential(_graph, 0), |
---|
| 387 | res_graph(_graph, capacity, flow), |
---|
| 388 | red_cost(res_graph, cost, potential), imbalance(_graph), |
---|
| 389 | #ifdef WITH_SCALING |
---|
| 390 | delta(0), delta_filter(res_graph, delta), |
---|
| 391 | dres_graph(res_graph, delta_filter), |
---|
| 392 | dijkstra(dres_graph, red_cost), pred(dres_graph), |
---|
| 393 | delta_deficit(imbalance, delta) |
---|
| 394 | #else //WITHOUT_CAPACITY_SCALING |
---|
| 395 | dijkstra(res_graph, red_cost), pred(res_graph), |
---|
| 396 | has_deficit(imbalance) |
---|
| 397 | #endif |
---|
| 398 | { |
---|
| 399 | // Checking the sum of supply values |
---|
| 400 | Supply sum = 0; |
---|
| 401 | for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n]; |
---|
| 402 | valid_supply = sum == 0; |
---|
| 403 | } |
---|
| 404 | |
---|
| 405 | /// \brief Simple constructor of the class (with lower bounds). |
---|
| 406 | /// |
---|
| 407 | /// Simple constructor of the class (with lower bounds). |
---|
| 408 | /// |
---|
| 409 | /// \param _graph The directed graph the algorithm runs on. |
---|
| 410 | /// \param _lower The lower bounds of the edges. |
---|
| 411 | /// \param _capacity The capacities (upper bounds) of the edges. |
---|
| 412 | /// \param _cost The cost (length) values of the edges. |
---|
| 413 | /// \param _s The source node. |
---|
| 414 | /// \param _t The target node. |
---|
| 415 | /// \param _flow_value The required amount of flow from node \c _s |
---|
| 416 | /// to node \c _t (i.e. the supply of \c _s and the demand of |
---|
| 417 | /// \c _t). |
---|
| 418 | CapacityScaling( const Graph &_graph, |
---|
| 419 | const LowerMap &_lower, |
---|
| 420 | const CapacityMap &_capacity, |
---|
| 421 | const CostMap &_cost, |
---|
| 422 | Node _s, Node _t, |
---|
| 423 | Supply _flow_value ) : |
---|
| 424 | graph(_graph), lower(&_lower), capacity(_graph), cost(_cost), |
---|
| 425 | supply(_graph), flow(_graph, 0), potential(_graph, 0), |
---|
| 426 | res_graph(_graph, capacity, flow), |
---|
| 427 | red_cost(res_graph, cost, potential), imbalance(_graph), |
---|
| 428 | #ifdef WITH_SCALING |
---|
| 429 | delta(0), delta_filter(res_graph, delta), |
---|
| 430 | dres_graph(res_graph, delta_filter), |
---|
| 431 | dijkstra(dres_graph, red_cost), pred(dres_graph), |
---|
| 432 | delta_deficit(imbalance, delta) |
---|
| 433 | #else //WITHOUT_CAPACITY_SCALING |
---|
| 434 | dijkstra(res_graph, red_cost), pred(res_graph), |
---|
| 435 | has_deficit(imbalance) |
---|
| 436 | #endif |
---|
| 437 | { |
---|
| 438 | // Removing nonzero lower bounds |
---|
| 439 | capacity = subMap(_capacity, _lower); |
---|
| 440 | for (NodeIt n(graph); n != INVALID; ++n) { |
---|
| 441 | Supply s = 0; |
---|
| 442 | if (n == _s) s = _flow_value; |
---|
| 443 | if (n == _t) s = -_flow_value; |
---|
| 444 | for (InEdgeIt e(graph, n); e != INVALID; ++e) |
---|
| 445 | s += _lower[e]; |
---|
| 446 | for (OutEdgeIt e(graph, n); e != INVALID; ++e) |
---|
| 447 | s -= _lower[e]; |
---|
[2507] | 448 | supply[n] = s; |
---|
[2440] | 449 | } |
---|
| 450 | valid_supply = true; |
---|
| 451 | } |
---|
| 452 | |
---|
| 453 | /// \brief Simple constructor of the class (without lower bounds). |
---|
| 454 | /// |
---|
| 455 | /// Simple constructor of the class (without lower bounds). |
---|
| 456 | /// |
---|
| 457 | /// \param _graph The directed graph the algorithm runs on. |
---|
| 458 | /// \param _capacity The capacities (upper bounds) of the edges. |
---|
| 459 | /// \param _cost The cost (length) values of the edges. |
---|
| 460 | /// \param _s The source node. |
---|
| 461 | /// \param _t The target node. |
---|
| 462 | /// \param _flow_value The required amount of flow from node \c _s |
---|
| 463 | /// to node \c _t (i.e. the supply of \c _s and the demand of |
---|
| 464 | /// \c _t). |
---|
| 465 | CapacityScaling( const Graph &_graph, |
---|
| 466 | const CapacityMap &_capacity, |
---|
| 467 | const CostMap &_cost, |
---|
| 468 | Node _s, Node _t, |
---|
| 469 | Supply _flow_value ) : |
---|
| 470 | graph(_graph), lower(NULL), capacity(_capacity), cost(_cost), |
---|
| 471 | supply(_graph, 0), flow(_graph, 0), potential(_graph, 0), |
---|
| 472 | res_graph(_graph, capacity, flow), |
---|
| 473 | red_cost(res_graph, cost, potential), imbalance(_graph), |
---|
| 474 | #ifdef WITH_SCALING |
---|
| 475 | delta(0), delta_filter(res_graph, delta), |
---|
| 476 | dres_graph(res_graph, delta_filter), |
---|
| 477 | dijkstra(dres_graph, red_cost), pred(dres_graph), |
---|
| 478 | delta_deficit(imbalance, delta) |
---|
| 479 | #else //WITHOUT_CAPACITY_SCALING |
---|
| 480 | dijkstra(res_graph, red_cost), pred(res_graph), |
---|
| 481 | has_deficit(imbalance) |
---|
| 482 | #endif |
---|
| 483 | { |
---|
| 484 | supply[_s] = _flow_value; |
---|
| 485 | supply[_t] = -_flow_value; |
---|
| 486 | valid_supply = true; |
---|
| 487 | } |
---|
| 488 | |
---|
| 489 | /// \brief Returns a const reference to the flow map. |
---|
| 490 | /// |
---|
| 491 | /// Returns a const reference to the flow map. |
---|
| 492 | /// |
---|
| 493 | /// \pre \ref run() must be called before using this function. |
---|
| 494 | const FlowMap& flowMap() const { |
---|
| 495 | return flow; |
---|
| 496 | } |
---|
| 497 | |
---|
| 498 | /// \brief Returns a const reference to the potential map (the dual |
---|
| 499 | /// solution). |
---|
| 500 | /// |
---|
| 501 | /// Returns a const reference to the potential map (the dual |
---|
| 502 | /// solution). |
---|
| 503 | /// |
---|
| 504 | /// \pre \ref run() must be called before using this function. |
---|
| 505 | const PotentialMap& potentialMap() const { |
---|
| 506 | return potential; |
---|
| 507 | } |
---|
| 508 | |
---|
| 509 | /// \brief Returns the total cost of the found flow. |
---|
| 510 | /// |
---|
| 511 | /// Returns the total cost of the found flow. The complexity of the |
---|
| 512 | /// function is \f$ O(e) \f$. |
---|
| 513 | /// |
---|
| 514 | /// \pre \ref run() must be called before using this function. |
---|
| 515 | Cost totalCost() const { |
---|
| 516 | Cost c = 0; |
---|
| 517 | for (EdgeIt e(graph); e != INVALID; ++e) |
---|
| 518 | c += flow[e] * cost[e]; |
---|
| 519 | return c; |
---|
| 520 | } |
---|
| 521 | |
---|
[2457] | 522 | /// \brief Runs the algorithm. |
---|
[2440] | 523 | /// |
---|
[2457] | 524 | /// Runs the algorithm. |
---|
[2440] | 525 | /// |
---|
| 526 | /// \return \c true if a feasible flow can be found. |
---|
| 527 | bool run() { |
---|
| 528 | return init() && start(); |
---|
| 529 | } |
---|
| 530 | |
---|
| 531 | protected: |
---|
| 532 | |
---|
| 533 | /// \brief Initializes the algorithm. |
---|
| 534 | bool init() { |
---|
| 535 | if (!valid_supply) return false; |
---|
[2507] | 536 | imbalance = supply; |
---|
[2440] | 537 | |
---|
| 538 | // Initalizing Dijkstra class |
---|
| 539 | updater.potentialMap(potential); |
---|
| 540 | dijkstra.distMap(updater).predMap(pred); |
---|
| 541 | |
---|
| 542 | #ifdef WITH_SCALING |
---|
| 543 | // Initilaizing delta value |
---|
[2457] | 544 | Supply max_sup = 0, max_dem = 0; |
---|
| 545 | for (NodeIt n(graph); n != INVALID; ++n) { |
---|
| 546 | if (supply[n] > max_sup) max_sup = supply[n]; |
---|
| 547 | if (supply[n] < -max_dem) max_dem = -supply[n]; |
---|
[2440] | 548 | } |
---|
[2457] | 549 | if (max_dem < max_sup) max_sup = max_dem; |
---|
[2471] | 550 | for ( delta = 1; SCALING_FACTOR * delta < max_sup; |
---|
| 551 | delta *= SCALING_FACTOR ) ; |
---|
[2440] | 552 | #endif |
---|
| 553 | return true; |
---|
| 554 | } |
---|
| 555 | |
---|
| 556 | #ifdef WITH_SCALING |
---|
| 557 | /// \brief Executes the capacity scaling version of the successive |
---|
| 558 | /// shortest path algorithm. |
---|
| 559 | bool start() { |
---|
| 560 | typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt; |
---|
| 561 | typedef typename DeltaResGraph::Edge DeltaResEdge; |
---|
[2457] | 562 | #ifdef _DEBUG_ITER_ |
---|
| 563 | int dijk_num = 0; |
---|
| 564 | #endif |
---|
[2440] | 565 | |
---|
| 566 | // Processing capacity scaling phases |
---|
| 567 | ResNode s, t; |
---|
[2471] | 568 | for ( ; delta >= 1; delta = delta < SCALING_FACTOR && delta > 1 ? |
---|
| 569 | 1 : delta / SCALING_FACTOR ) |
---|
[2440] | 570 | { |
---|
| 571 | // Saturating edges not satisfying the optimality condition |
---|
| 572 | Capacity r; |
---|
| 573 | for (DeltaResEdgeIt e(dres_graph); e != INVALID; ++e) { |
---|
| 574 | if (red_cost[e] < 0) { |
---|
| 575 | res_graph.augment(e, r = res_graph.rescap(e)); |
---|
| 576 | imbalance[dres_graph.target(e)] += r; |
---|
| 577 | imbalance[dres_graph.source(e)] -= r; |
---|
| 578 | } |
---|
| 579 | } |
---|
| 580 | |
---|
| 581 | // Finding excess nodes |
---|
| 582 | excess_nodes.clear(); |
---|
[2457] | 583 | deficit_nodes.clear(); |
---|
[2440] | 584 | for (ResNodeIt n(res_graph); n != INVALID; ++n) { |
---|
[2457] | 585 | if (imbalance[n] >= delta) excess_nodes.push_back(n); |
---|
| 586 | if (imbalance[n] <= -delta) deficit_nodes.push_back(n); |
---|
[2440] | 587 | } |
---|
| 588 | next_node = 0; |
---|
| 589 | |
---|
[2457] | 590 | // Finding shortest paths |
---|
[2440] | 591 | while (next_node < excess_nodes.size()) { |
---|
[2457] | 592 | // Checking deficit nodes |
---|
| 593 | if (delta > 1) { |
---|
| 594 | bool delta_def = false; |
---|
| 595 | for (int i = 0; i < deficit_nodes.size(); ++i) { |
---|
| 596 | if (imbalance[deficit_nodes[i]] <= -delta) { |
---|
| 597 | delta_def = true; |
---|
| 598 | break; |
---|
| 599 | } |
---|
| 600 | } |
---|
| 601 | if (!delta_def) break; |
---|
| 602 | } |
---|
| 603 | |
---|
[2440] | 604 | // Running Dijkstra |
---|
| 605 | s = excess_nodes[next_node]; |
---|
| 606 | updater.init(); |
---|
| 607 | dijkstra.init(); |
---|
| 608 | dijkstra.addSource(s); |
---|
[2457] | 609 | #ifdef _DEBUG_ITER_ |
---|
| 610 | ++dijk_num; |
---|
| 611 | #endif |
---|
[2440] | 612 | if ((t = dijkstra.start(delta_deficit)) == INVALID) { |
---|
| 613 | if (delta > 1) { |
---|
| 614 | ++next_node; |
---|
| 615 | continue; |
---|
| 616 | } |
---|
| 617 | return false; |
---|
| 618 | } |
---|
| 619 | |
---|
| 620 | // Updating node potentials |
---|
| 621 | updater.update(); |
---|
| 622 | |
---|
| 623 | // Augment along a shortest path from s to t |
---|
| 624 | Capacity d = imbalance[s] < -imbalance[t] ? |
---|
| 625 | imbalance[s] : -imbalance[t]; |
---|
| 626 | ResNode u = t; |
---|
| 627 | ResEdge e; |
---|
| 628 | if (d > delta) { |
---|
| 629 | while ((e = pred[u]) != INVALID) { |
---|
| 630 | if (res_graph.rescap(e) < d) d = res_graph.rescap(e); |
---|
| 631 | u = dres_graph.source(e); |
---|
| 632 | } |
---|
| 633 | } |
---|
| 634 | u = t; |
---|
| 635 | while ((e = pred[u]) != INVALID) { |
---|
| 636 | res_graph.augment(e, d); |
---|
| 637 | u = dres_graph.source(e); |
---|
| 638 | } |
---|
| 639 | imbalance[s] -= d; |
---|
| 640 | imbalance[t] += d; |
---|
| 641 | if (imbalance[s] < delta) ++next_node; |
---|
| 642 | } |
---|
| 643 | } |
---|
[2457] | 644 | #ifdef _DEBUG_ITER_ |
---|
| 645 | std::cout << "Cost Scaling algorithm finished with running Dijkstra algorithm " |
---|
| 646 | << dijk_num << " times." << std::endl; |
---|
| 647 | #endif |
---|
[2440] | 648 | |
---|
| 649 | // Handling nonzero lower bounds |
---|
| 650 | if (lower) { |
---|
| 651 | for (EdgeIt e(graph); e != INVALID; ++e) |
---|
| 652 | flow[e] += (*lower)[e]; |
---|
| 653 | } |
---|
| 654 | return true; |
---|
| 655 | } |
---|
| 656 | |
---|
| 657 | #else //WITHOUT_CAPACITY_SCALING |
---|
| 658 | /// \brief Executes the successive shortest path algorithm without |
---|
| 659 | /// capacity scaling. |
---|
| 660 | bool start() { |
---|
| 661 | // Finding excess nodes |
---|
| 662 | for (ResNodeIt n(res_graph); n != INVALID; ++n) { |
---|
| 663 | if (imbalance[n] > 0) excess_nodes.push_back(n); |
---|
| 664 | } |
---|
| 665 | if (excess_nodes.size() == 0) return true; |
---|
| 666 | next_node = 0; |
---|
| 667 | |
---|
[2457] | 668 | // Finding shortest paths |
---|
[2440] | 669 | ResNode s, t; |
---|
| 670 | while ( imbalance[excess_nodes[next_node]] > 0 || |
---|
| 671 | ++next_node < excess_nodes.size() ) |
---|
| 672 | { |
---|
| 673 | // Running Dijkstra |
---|
| 674 | s = excess_nodes[next_node]; |
---|
| 675 | updater.init(); |
---|
| 676 | dijkstra.init(); |
---|
| 677 | dijkstra.addSource(s); |
---|
| 678 | if ((t = dijkstra.start(has_deficit)) == INVALID) |
---|
| 679 | return false; |
---|
| 680 | |
---|
| 681 | // Updating node potentials |
---|
| 682 | updater.update(); |
---|
| 683 | |
---|
| 684 | // Augmenting along a shortest path from s to t |
---|
| 685 | Capacity delta = imbalance[s] < -imbalance[t] ? |
---|
| 686 | imbalance[s] : -imbalance[t]; |
---|
| 687 | ResNode u = t; |
---|
| 688 | ResEdge e; |
---|
| 689 | while ((e = pred[u]) != INVALID) { |
---|
| 690 | if (res_graph.rescap(e) < delta) delta = res_graph.rescap(e); |
---|
| 691 | u = res_graph.source(e); |
---|
| 692 | } |
---|
| 693 | u = t; |
---|
| 694 | while ((e = pred[u]) != INVALID) { |
---|
| 695 | res_graph.augment(e, delta); |
---|
| 696 | u = res_graph.source(e); |
---|
| 697 | } |
---|
| 698 | imbalance[s] -= delta; |
---|
| 699 | imbalance[t] += delta; |
---|
| 700 | } |
---|
| 701 | |
---|
| 702 | // Handling nonzero lower bounds |
---|
| 703 | if (lower) { |
---|
| 704 | for (EdgeIt e(graph); e != INVALID; ++e) |
---|
| 705 | flow[e] += (*lower)[e]; |
---|
| 706 | } |
---|
| 707 | return true; |
---|
| 708 | } |
---|
| 709 | #endif |
---|
| 710 | |
---|
| 711 | }; //class CapacityScaling |
---|
| 712 | |
---|
| 713 | ///@} |
---|
| 714 | |
---|
| 715 | } //namespace lemon |
---|
| 716 | |
---|
| 717 | #endif //LEMON_CAPACITY_SCALING_H |
---|