1.1 --- a/lemon/capacity_scaling.h Thu Nov 08 14:21:28 2007 +0000
1.2 +++ b/lemon/capacity_scaling.h Wed Nov 14 06:28:08 2007 +0000
1.3 @@ -26,8 +26,8 @@
1.4 /// flow.
1.5
1.6 #include <vector>
1.7 +#include <lemon/graph_adaptor.h>
1.8 #include <lemon/dijkstra.h>
1.9 -#include <lemon/graph_adaptor.h>
1.10
1.11 #define WITH_SCALING
1.12
1.13 @@ -43,10 +43,12 @@
1.14 /// @{
1.15
1.16 /// \brief Implementation of the capacity scaling version of the
1.17 - /// successive shortest path algorithm for finding a minimum cost flow.
1.18 + /// successive shortest path algorithm for finding a minimum cost
1.19 + /// flow.
1.20 ///
1.21 - /// \ref lemon::CapacityScaling "CapacityScaling" implements a
1.22 - /// capacity scaling algorithm for finding a minimum cost flow.
1.23 + /// \ref lemon::CapacityScaling "CapacityScaling" implements the
1.24 + /// capacity scaling version of the successive shortest path
1.25 + /// algorithm for finding a minimum cost flow.
1.26 ///
1.27 /// \param Graph The directed graph type the algorithm runs on.
1.28 /// \param LowerMap The type of the lower bound map.
1.29 @@ -57,7 +59,7 @@
1.30 /// \warning
1.31 /// - Edge capacities and costs should be nonnegative integers.
1.32 /// However \c CostMap::Value should be signed type.
1.33 - /// - Supply values should be integers.
1.34 + /// - Supply values should be signed integers.
1.35 /// - \c LowerMap::Value must be convertible to
1.36 /// \c CapacityMap::Value and \c CapacityMap::Value must be
1.37 /// convertible to \c SupplyMap::Value.
1.38 @@ -113,15 +115,12 @@
1.39
1.40 public:
1.41
1.42 - typedef typename MapBase<ResEdge, Cost>::Value Value;
1.43 - typedef typename MapBase<ResEdge, Cost>::Key Key;
1.44 -
1.45 ReducedCostMap( const ResGraph &_gr,
1.46 const CostMap &_cost,
1.47 const PotentialMap &_pot ) :
1.48 gr(_gr), cost_map(_cost), pot_map(_pot) {}
1.49
1.50 - Value operator[](const Key &e) const {
1.51 + Cost operator[](const ResEdge &e) const {
1.52 return ResGraph::forward(e) ?
1.53 cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)] :
1.54 -cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
1.55 @@ -129,8 +128,8 @@
1.56
1.57 }; //class ReducedCostMap
1.58
1.59 - /// \brief Map adaptor for \ref lemon::Dijkstra "Dijkstra" class to
1.60 - /// update node potentials.
1.61 + /// \brief Map class for the \ref lemon::Dijkstra "Dijkstra"
1.62 + /// algorithm to update node potentials.
1.63 class PotentialUpdateMap : public MapBase<ResNode, Cost>
1.64 {
1.65 private:
1.66 @@ -141,9 +140,6 @@
1.67
1.68 public:
1.69
1.70 - typedef typename MapBase<ResNode, Cost>::Value Value;
1.71 - typedef typename MapBase<ResNode, Cost>::Key Key;
1.72 -
1.73 void potentialMap(PotentialMap &_pot) {
1.74 pot = &_pot;
1.75 }
1.76 @@ -152,7 +148,7 @@
1.77 data.clear();
1.78 }
1.79
1.80 - void set(const Key &n, const Value &v) {
1.81 + void set(const ResNode &n, const Cost &v) {
1.82 data.push_back(Pair(n, v));
1.83 }
1.84
1.85 @@ -185,7 +181,7 @@
1.86 }; //class DeficitBoolMap
1.87
1.88 /// \brief Map adaptor class for filtering edges with at least
1.89 - /// \c delta residual capacity
1.90 + /// \c delta residual capacity.
1.91 class DeltaFilterMap : public MapBase<ResEdge, bool>
1.92 {
1.93 private:
1.94 @@ -195,13 +191,10 @@
1.95
1.96 public:
1.97
1.98 - typedef typename MapBase<ResEdge, Cost>::Value Value;
1.99 - typedef typename MapBase<ResEdge, Cost>::Key Key;
1.100 -
1.101 DeltaFilterMap(const ResGraph &_gr, const Capacity &_delta) :
1.102 gr(_gr), delta(_delta) {}
1.103
1.104 - Value operator[](const Key &e) const {
1.105 + bool operator[](const ResEdge &e) const {
1.106 return gr.rescap(e) >= delta;
1.107 }
1.108
1.109 @@ -298,9 +291,12 @@
1.110
1.111 /// \brief The delta parameter used for capacity scaling.
1.112 Capacity delta;
1.113 - /// \brief Edge filter map.
1.114 + /// \brief Edge filter map for filtering edges with at least
1.115 + /// \c delta residual capacity.
1.116 DeltaFilterMap delta_filter;
1.117 - /// \brief The delta residual graph.
1.118 + /// \brief The delta residual graph (i.e. the subgraph of the
1.119 + /// residual graph consisting of edges with at least \c delta
1.120 + /// residual capacity).
1.121 DeltaResGraph dres_graph;
1.122 /// \brief Map for identifing deficit nodes.
1.123 DeficitBoolMap delta_deficit;
1.124 @@ -573,8 +569,8 @@
1.125 for (DeltaResEdgeIt e(dres_graph); e != INVALID; ++e) {
1.126 if (red_cost[e] < 0) {
1.127 res_graph.augment(e, r = res_graph.rescap(e));
1.128 + imbalance[dres_graph.source(e)] -= r;
1.129 imbalance[dres_graph.target(e)] += r;
1.130 - imbalance[dres_graph.source(e)] -= r;
1.131 }
1.132 }
1.133