Cleanup in the minimum cost flow files.
The changes only affects the documentation and the look of the source codes.
1.1 --- a/lemon/capacity_scaling.h Sun Jan 13 10:26:55 2008 +0000
1.2 +++ b/lemon/capacity_scaling.h Sun Jan 13 10:32:14 2008 +0000
1.3 @@ -22,8 +22,7 @@
1.4 /// \ingroup min_cost_flow
1.5 ///
1.6 /// \file
1.7 -/// \brief The capacity scaling algorithm for finding a minimum cost
1.8 -/// flow.
1.9 +/// \brief The capacity scaling algorithm for finding a minimum cost flow.
1.10
1.11 #include <lemon/graph_adaptor.h>
1.12 #include <lemon/bin_heap.h>
1.13 @@ -49,7 +48,7 @@
1.14 /// \param SupplyMap The type of the supply map.
1.15 ///
1.16 /// \warning
1.17 - /// - Edge capacities and costs should be nonnegative integers.
1.18 + /// - Edge capacities and costs should be non-negative integers.
1.19 /// However \c CostMap::Value should be signed type.
1.20 /// - Supply values should be signed integers.
1.21 /// - \c LowerMap::Value must be convertible to
1.22 @@ -66,32 +65,27 @@
1.23 <typename CapacityMap::Value> >
1.24 class CapacityScaling
1.25 {
1.26 - typedef typename Graph::Node Node;
1.27 - typedef typename Graph::NodeIt NodeIt;
1.28 - typedef typename Graph::Edge Edge;
1.29 - typedef typename Graph::EdgeIt EdgeIt;
1.30 - typedef typename Graph::InEdgeIt InEdgeIt;
1.31 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.32 + GRAPH_TYPEDEFS(typename Graph);
1.33
1.34 typedef typename LowerMap::Value Lower;
1.35 typedef typename CapacityMap::Value Capacity;
1.36 typedef typename CostMap::Value Cost;
1.37 typedef typename SupplyMap::Value Supply;
1.38 - typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
1.39 - typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
1.40 + typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
1.41 + typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
1.42 typedef typename Graph::template NodeMap<Edge> PredMap;
1.43
1.44 public:
1.45
1.46 - /// \brief Type to enable or disable capacity scaling.
1.47 + /// Type to enable or disable capacity scaling.
1.48 enum ScalingEnum {
1.49 WITH_SCALING = 0,
1.50 WITHOUT_SCALING = -1
1.51 };
1.52
1.53 - /// \brief The type of the flow map.
1.54 - typedef CapacityRefMap FlowMap;
1.55 - /// \brief The type of the potential map.
1.56 + /// The type of the flow map.
1.57 + typedef typename Graph::template EdgeMap<Capacity> FlowMap;
1.58 + /// The type of the potential map.
1.59 typedef typename Graph::template NodeMap<Cost> PotentialMap;
1.60
1.61 protected:
1.62 @@ -110,34 +104,34 @@
1.63
1.64 protected:
1.65
1.66 - /// \brief The directed graph the algorithm runs on.
1.67 + /// The directed graph the algorithm runs on.
1.68 const Graph &graph;
1.69
1.70 - /// \brief The flow map.
1.71 + /// The flow map.
1.72 const FlowMap &flow;
1.73 - /// \brief The residual capacity map.
1.74 - const CapacityRefMap &res_cap;
1.75 - /// \brief The cost map.
1.76 + /// The residual capacity map.
1.77 + const CapacityEdgeMap &res_cap;
1.78 + /// The cost map.
1.79 const CostMap &cost;
1.80 - /// \brief The excess map.
1.81 - const SupplyRefMap &excess;
1.82 + /// The excess map.
1.83 + const SupplyNodeMap &excess;
1.84
1.85 - /// \brief The potential map.
1.86 + /// The potential map.
1.87 PotentialMap &potential;
1.88
1.89 - /// \brief The distance map.
1.90 + /// The distance map.
1.91 CostNodeMap dist;
1.92 - /// \brief The map of predecessors edges.
1.93 + /// The map of predecessors edges.
1.94 PredMap &pred;
1.95 - /// \brief The processed (i.e. permanently labeled) nodes.
1.96 + /// The processed (i.e. permanently labeled) nodes.
1.97 std::vector<Node> proc_nodes;
1.98
1.99 public:
1.100
1.101 - /// \brief The constructor of the class.
1.102 + /// The constructor of the class.
1.103 ResidualDijkstra( const Graph &_graph,
1.104 const FlowMap &_flow,
1.105 - const CapacityRefMap &_res_cap,
1.106 + const CapacityEdgeMap &_res_cap,
1.107 const CostMap &_cost,
1.108 const SupplyMap &_excess,
1.109 PotentialMap &_potential,
1.110 @@ -147,7 +141,7 @@
1.111 pred(_pred)
1.112 {}
1.113
1.114 - /// \brief Runs the algorithm from the given source node.
1.115 + /// Runs the algorithm from the given source node.
1.116 Node run(Node s, Capacity delta) {
1.117 HeapCrossRef heap_cross_ref(graph, Heap::PRE_HEAP);
1.118 Heap heap(heap_cross_ref);
1.119 @@ -222,46 +216,43 @@
1.120
1.121 protected:
1.122
1.123 - /// \brief The directed graph the algorithm runs on.
1.124 + /// The directed graph the algorithm runs on.
1.125 const Graph &graph;
1.126 - /// \brief The original lower bound map.
1.127 + /// The original lower bound map.
1.128 const LowerMap *lower;
1.129 - /// \brief The modified capacity map.
1.130 - CapacityRefMap capacity;
1.131 - /// \brief The cost map.
1.132 + /// The modified capacity map.
1.133 + CapacityEdgeMap capacity;
1.134 + /// The cost map.
1.135 const CostMap &cost;
1.136 - /// \brief The modified supply map.
1.137 - SupplyRefMap supply;
1.138 - /// \brief The sum of supply values equals zero.
1.139 + /// The modified supply map.
1.140 + SupplyNodeMap supply;
1.141 bool valid_supply;
1.142
1.143 - /// \brief The edge map of the current flow.
1.144 + /// The edge map of the current flow.
1.145 FlowMap flow;
1.146 - /// \brief The potential node map.
1.147 + /// The potential node map.
1.148 PotentialMap potential;
1.149
1.150 - /// \brief The residual capacity map.
1.151 - CapacityRefMap res_cap;
1.152 - /// \brief The excess map.
1.153 - SupplyRefMap excess;
1.154 - /// \brief The excess nodes (i.e. nodes with positive excess).
1.155 + /// The residual capacity map.
1.156 + CapacityEdgeMap res_cap;
1.157 + /// The excess map.
1.158 + SupplyNodeMap excess;
1.159 + /// The excess nodes (i.e. the nodes with positive excess).
1.160 std::vector<Node> excess_nodes;
1.161 - /// \brief The index of the next excess node.
1.162 - int next_node;
1.163 + /// The deficit nodes (i.e. the nodes with negative excess).
1.164 + std::vector<Node> deficit_nodes;
1.165
1.166 - /// \brief The scaling status (enabled or disabled).
1.167 + /// The scaling status (enabled or disabled).
1.168 ScalingEnum scaling;
1.169 - /// \brief The delta parameter used for capacity scaling.
1.170 + /// The \c delta parameter used for capacity scaling.
1.171 Capacity delta;
1.172 - /// \brief The maximum number of phases.
1.173 - Capacity phase_num;
1.174 - /// \brief The deficit nodes.
1.175 - std::vector<Node> deficit_nodes;
1.176 + /// The maximum number of phases.
1.177 + int phase_num;
1.178
1.179 /// \brief Implementation of the \ref Dijkstra algorithm for
1.180 /// finding augmenting shortest paths in the residual network.
1.181 ResidualDijkstra dijkstra;
1.182 - /// \brief The map of predecessors edges.
1.183 + /// The map of predecessors edges.
1.184 PredMap pred;
1.185
1.186 public :
1.187 @@ -285,7 +276,7 @@
1.188 res_cap(_graph), excess(_graph), pred(_graph),
1.189 dijkstra(graph, flow, res_cap, cost, excess, potential, pred)
1.190 {
1.191 - // Removing nonzero lower bounds
1.192 + // Removing non-zero lower bounds
1.193 capacity = subMap(_capacity, _lower);
1.194 res_cap = capacity;
1.195 Supply sum = 0;
1.196 @@ -335,8 +326,7 @@
1.197 /// \param _s The source node.
1.198 /// \param _t The target node.
1.199 /// \param _flow_value The required amount of flow from node \c _s
1.200 - /// to node \c _t (i.e. the supply of \c _s and the demand of
1.201 - /// \c _t).
1.202 + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
1.203 CapacityScaling( const Graph &_graph,
1.204 const LowerMap &_lower,
1.205 const CapacityMap &_capacity,
1.206 @@ -348,7 +338,7 @@
1.207 res_cap(_graph), excess(_graph), pred(_graph),
1.208 dijkstra(graph, flow, res_cap, cost, excess, potential)
1.209 {
1.210 - // Removing nonzero lower bounds
1.211 + // Removing non-zero lower bounds
1.212 capacity = subMap(_capacity, _lower);
1.213 res_cap = capacity;
1.214 for (NodeIt n(graph); n != INVALID; ++n) {
1.215 @@ -374,8 +364,7 @@
1.216 /// \param _s The source node.
1.217 /// \param _t The target node.
1.218 /// \param _flow_value The required amount of flow from node \c _s
1.219 - /// to node \c _t (i.e. the supply of \c _s and the demand of
1.220 - /// \c _t).
1.221 + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
1.222 CapacityScaling( const Graph &_graph,
1.223 const CapacityMap &_capacity,
1.224 const CostMap &_cost,
1.225 @@ -391,6 +380,22 @@
1.226 valid_supply = true;
1.227 }
1.228
1.229 + /// \brief Runs the algorithm.
1.230 + ///
1.231 + /// Runs the algorithm.
1.232 + ///
1.233 + /// \param scaling_mode The scaling mode. In case of WITH_SCALING
1.234 + /// capacity scaling is enabled in the algorithm (this is the
1.235 + /// default) otherwise it is disabled.
1.236 + /// If the maximum edge capacity and/or the amount of total supply
1.237 + /// is small, the algorithm could be slightly faster without
1.238 + /// scaling.
1.239 + ///
1.240 + /// \return \c true if a feasible flow can be found.
1.241 + bool run(int scaling_mode = WITH_SCALING) {
1.242 + return init(scaling_mode) && start();
1.243 + }
1.244 +
1.245 /// \brief Returns a const reference to the flow map.
1.246 ///
1.247 /// Returns a const reference to the flow map.
1.248 @@ -424,24 +429,9 @@
1.249 return c;
1.250 }
1.251
1.252 - /// \brief Runs the algorithm.
1.253 - ///
1.254 - /// Runs the algorithm.
1.255 - ///
1.256 - /// \param scaling_mode The scaling mode. In case of WITH_SCALING
1.257 - /// capacity scaling is enabled in the algorithm (this is the
1.258 - /// default value) otherwise it is disabled.
1.259 - /// If the maximum edge capacity and/or the amount of total supply
1.260 - /// is small, the algorithm could be faster without scaling.
1.261 - ///
1.262 - /// \return \c true if a feasible flow can be found.
1.263 - bool run(int scaling_mode = WITH_SCALING) {
1.264 - return init(scaling_mode) && start();
1.265 - }
1.266 -
1.267 protected:
1.268
1.269 - /// \brief Initializes the algorithm.
1.270 + /// Initializes the algorithm.
1.271 bool init(int scaling_mode) {
1.272 if (!valid_supply) return false;
1.273 excess = supply;
1.274 @@ -465,7 +455,7 @@
1.275 return true;
1.276 }
1.277
1.278 - /// \brief Executes the algorithm.
1.279 + /// Executes the algorithm.
1.280 bool start() {
1.281 if (delta > 1)
1.282 return startWithScaling();
1.283 @@ -506,7 +496,7 @@
1.284 if (excess[n] >= delta) excess_nodes.push_back(n);
1.285 if (excess[n] <= -delta) deficit_nodes.push_back(n);
1.286 }
1.287 - next_node = 0;
1.288 + int next_node = 0;
1.289
1.290 // Finding augmenting shortest paths
1.291 while (next_node < excess_nodes.size()) {
1.292 @@ -572,7 +562,7 @@
1.293 delta = delta <= factor ? 1 : delta / factor;
1.294 }
1.295
1.296 - // Handling nonzero lower bounds
1.297 + // Handling non-zero lower bounds
1.298 if (lower) {
1.299 for (EdgeIt e(graph); e != INVALID; ++e)
1.300 flow[e] += (*lower)[e];
1.301 @@ -584,11 +574,10 @@
1.302 /// capacity scaling.
1.303 bool startWithoutScaling() {
1.304 // Finding excess nodes
1.305 - for (NodeIt n(graph); n != INVALID; ++n) {
1.306 + for (NodeIt n(graph); n != INVALID; ++n)
1.307 if (excess[n] > 0) excess_nodes.push_back(n);
1.308 - }
1.309 if (excess_nodes.size() == 0) return true;
1.310 - next_node = 0;
1.311 + int next_node = 0;
1.312
1.313 // Finding shortest paths
1.314 Node s, t;
1.315 @@ -631,7 +620,7 @@
1.316 excess[t] += d;
1.317 }
1.318
1.319 - // Handling nonzero lower bounds
1.320 + // Handling non-zero lower bounds
1.321 if (lower) {
1.322 for (EdgeIt e(graph); e != INVALID; ++e)
1.323 flow[e] += (*lower)[e];
2.1 --- a/lemon/cycle_canceling.h Sun Jan 13 10:26:55 2008 +0000
2.2 +++ b/lemon/cycle_canceling.h Sun Jan 13 10:32:14 2008 +0000
2.3 @@ -34,24 +34,17 @@
2.4
2.5 #ifdef LIMITED_CYCLE_CANCELING
2.6 #include <lemon/bellman_ford.h>
2.7 - /// \brief The maximum number of iterations for the first execution
2.8 - /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.
2.9 - /// It should be at least 2.
2.10 - #define STARTING_LIMIT 2
2.11 - /// \brief The iteration limit for the
2.12 - /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
2.13 - /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
2.14 - /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
2.15 - #define ALPHA_MUL 3
2.16 - /// \brief The iteration limit for the
2.17 - /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
2.18 - /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
2.19 - /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
2.20 - #define ALPHA_DIV 2
2.21 + // The maximum number of iterations for the first execution of the
2.22 + // Bellman-Ford algorithm. It should be at least 2.
2.23 + #define STARTING_LIMIT 2
2.24 + // The iteration limit for the Bellman-Ford algorithm is multiplied by
2.25 + // <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
2.26 + // <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
2.27 + #define ALPHA_MUL 3
2.28 + #define ALPHA_DIV 2
2.29
2.30 //#define _ONLY_ONE_CYCLE_
2.31 //#define _NO_BACK_STEP_
2.32 -//#define _DEBUG_ITER_
2.33 #endif
2.34
2.35 #ifdef MIN_MEAN_CYCLE_CANCELING
2.36 @@ -59,16 +52,18 @@
2.37 #include <lemon/path.h>
2.38 #endif
2.39
2.40 +//#define _DEBUG_ITER_
2.41 +
2.42 namespace lemon {
2.43
2.44 /// \addtogroup min_cost_flow
2.45 /// @{
2.46
2.47 - /// \brief Implementation of a cycle-canceling algorithm for finding
2.48 - /// a minimum cost flow.
2.49 + /// \brief Implementation of a cycle-canceling algorithm for
2.50 + /// finding a minimum cost flow.
2.51 ///
2.52 - /// \ref lemon::CycleCanceling "CycleCanceling" implements a
2.53 - /// cycle-canceling algorithm for finding a minimum cost flow.
2.54 + /// \ref CycleCanceling implements a cycle-canceling algorithm for
2.55 + /// finding a minimum cost flow.
2.56 ///
2.57 /// \param Graph The directed graph type the algorithm runs on.
2.58 /// \param LowerMap The type of the lower bound map.
2.59 @@ -77,12 +72,12 @@
2.60 /// \param SupplyMap The type of the supply map.
2.61 ///
2.62 /// \warning
2.63 - /// - Edge capacities and costs should be nonnegative integers.
2.64 - /// However \c CostMap::Value should be signed type.
2.65 + /// - Edge capacities and costs should be non-negative integers.
2.66 + /// However \c CostMap::Value should be signed type.
2.67 /// - Supply values should be signed integers.
2.68 /// - \c LowerMap::Value must be convertible to
2.69 - /// \c CapacityMap::Value and \c CapacityMap::Value must be
2.70 - /// convertible to \c SupplyMap::Value.
2.71 + /// \c CapacityMap::Value and \c CapacityMap::Value must be
2.72 + /// convertible to \c SupplyMap::Value.
2.73 ///
2.74 /// \author Peter Kovacs
2.75
2.76 @@ -94,22 +89,17 @@
2.77 <typename CapacityMap::Value> >
2.78 class CycleCanceling
2.79 {
2.80 - typedef typename Graph::Node Node;
2.81 - typedef typename Graph::NodeIt NodeIt;
2.82 - typedef typename Graph::Edge Edge;
2.83 - typedef typename Graph::EdgeIt EdgeIt;
2.84 - typedef typename Graph::InEdgeIt InEdgeIt;
2.85 - typedef typename Graph::OutEdgeIt OutEdgeIt;
2.86 + GRAPH_TYPEDEFS(typename Graph);
2.87
2.88 typedef typename LowerMap::Value Lower;
2.89 typedef typename CapacityMap::Value Capacity;
2.90 typedef typename CostMap::Value Cost;
2.91 typedef typename SupplyMap::Value Supply;
2.92 - typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
2.93 - typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
2.94 + typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
2.95 + typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
2.96
2.97 typedef ResGraphAdaptor< const Graph, Capacity,
2.98 - CapacityRefMap, CapacityRefMap > ResGraph;
2.99 + CapacityEdgeMap, CapacityEdgeMap > ResGraph;
2.100 typedef typename ResGraph::Node ResNode;
2.101 typedef typename ResGraph::NodeIt ResNodeIt;
2.102 typedef typename ResGraph::Edge ResEdge;
2.103 @@ -117,12 +107,12 @@
2.104
2.105 public:
2.106
2.107 - /// \brief The type of the flow map.
2.108 - typedef CapacityRefMap FlowMap;
2.109 + /// The type of the flow map.
2.110 + typedef typename Graph::template EdgeMap<Capacity> FlowMap;
2.111
2.112 protected:
2.113
2.114 - /// \brief Map adaptor class for handling residual edge costs.
2.115 + /// Map adaptor class for handling residual edge costs.
2.116 class ResCostMap : public MapBase<ResEdge, Cost>
2.117 {
2.118 private:
2.119 @@ -134,31 +124,30 @@
2.120 ResCostMap(const CostMap &_cost) : cost_map(_cost) {}
2.121
2.122 Cost operator[](const ResEdge &e) const {
2.123 - return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
2.124 + return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
2.125 }
2.126
2.127 }; //class ResCostMap
2.128
2.129 protected:
2.130
2.131 - /// \brief The directed graph the algorithm runs on.
2.132 + /// The directed graph the algorithm runs on.
2.133 const Graph &graph;
2.134 - /// \brief The original lower bound map.
2.135 + /// The original lower bound map.
2.136 const LowerMap *lower;
2.137 - /// \brief The modified capacity map.
2.138 - CapacityRefMap capacity;
2.139 - /// \brief The cost map.
2.140 + /// The modified capacity map.
2.141 + CapacityEdgeMap capacity;
2.142 + /// The cost map.
2.143 const CostMap &cost;
2.144 - /// \brief The modified supply map.
2.145 - SupplyRefMap supply;
2.146 - /// \brief The sum of supply values equals zero.
2.147 + /// The modified supply map.
2.148 + SupplyNodeMap supply;
2.149 bool valid_supply;
2.150
2.151 - /// \brief The current flow.
2.152 + /// The current flow.
2.153 FlowMap flow;
2.154 - /// \brief The residual graph.
2.155 + /// The residual graph.
2.156 ResGraph res_graph;
2.157 - /// \brief The residual cost map.
2.158 + /// The residual cost map.
2.159 ResCostMap res_cost;
2.160
2.161 public :
2.162 @@ -173,24 +162,24 @@
2.163 /// \param _cost The cost (length) values of the edges.
2.164 /// \param _supply The supply values of the nodes (signed).
2.165 CycleCanceling( const Graph &_graph,
2.166 - const LowerMap &_lower,
2.167 - const CapacityMap &_capacity,
2.168 - const CostMap &_cost,
2.169 - const SupplyMap &_supply ) :
2.170 + const LowerMap &_lower,
2.171 + const CapacityMap &_capacity,
2.172 + const CostMap &_cost,
2.173 + const SupplyMap &_supply ) :
2.174 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
2.175 supply(_graph), flow(_graph, 0),
2.176 res_graph(_graph, capacity, flow), res_cost(cost)
2.177 {
2.178 - // Removing nonzero lower bounds
2.179 + // Removing non-zero lower bounds
2.180 capacity = subMap(_capacity, _lower);
2.181 Supply sum = 0;
2.182 for (NodeIt n(graph); n != INVALID; ++n) {
2.183 - Supply s = _supply[n];
2.184 - for (InEdgeIt e(graph, n); e != INVALID; ++e)
2.185 - s += _lower[e];
2.186 - for (OutEdgeIt e(graph, n); e != INVALID; ++e)
2.187 - s -= _lower[e];
2.188 - sum += (supply[n] = s);
2.189 + Supply s = _supply[n];
2.190 + for (InEdgeIt e(graph, n); e != INVALID; ++e)
2.191 + s += _lower[e];
2.192 + for (OutEdgeIt e(graph, n); e != INVALID; ++e)
2.193 + s -= _lower[e];
2.194 + sum += (supply[n] = s);
2.195 }
2.196 valid_supply = sum == 0;
2.197 }
2.198 @@ -204,9 +193,9 @@
2.199 /// \param _cost The cost (length) values of the edges.
2.200 /// \param _supply The supply values of the nodes (signed).
2.201 CycleCanceling( const Graph &_graph,
2.202 - const CapacityMap &_capacity,
2.203 - const CostMap &_cost,
2.204 - const SupplyMap &_supply ) :
2.205 + const CapacityMap &_capacity,
2.206 + const CostMap &_cost,
2.207 + const SupplyMap &_supply ) :
2.208 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
2.209 supply(_supply), flow(_graph, 0),
2.210 res_graph(_graph, capacity, flow), res_cost(cost)
2.211 @@ -217,7 +206,6 @@
2.212 valid_supply = sum == 0;
2.213 }
2.214
2.215 -
2.216 /// \brief Simple constructor of the class (with lower bounds).
2.217 ///
2.218 /// Simple constructor of the class (with lower bounds).
2.219 @@ -229,29 +217,28 @@
2.220 /// \param _s The source node.
2.221 /// \param _t The target node.
2.222 /// \param _flow_value The required amount of flow from node \c _s
2.223 - /// to node \c _t (i.e. the supply of \c _s and the demand of
2.224 - /// \c _t).
2.225 + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
2.226 CycleCanceling( const Graph &_graph,
2.227 - const LowerMap &_lower,
2.228 - const CapacityMap &_capacity,
2.229 - const CostMap &_cost,
2.230 - Node _s, Node _t,
2.231 - Supply _flow_value ) :
2.232 + const LowerMap &_lower,
2.233 + const CapacityMap &_capacity,
2.234 + const CostMap &_cost,
2.235 + Node _s, Node _t,
2.236 + Supply _flow_value ) :
2.237 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
2.238 supply(_graph), flow(_graph, 0),
2.239 res_graph(_graph, capacity, flow), res_cost(cost)
2.240 {
2.241 - // Removing nonzero lower bounds
2.242 + // Removing non-zero lower bounds
2.243 capacity = subMap(_capacity, _lower);
2.244 for (NodeIt n(graph); n != INVALID; ++n) {
2.245 - Supply s = 0;
2.246 - if (n == _s) s = _flow_value;
2.247 - if (n == _t) s = -_flow_value;
2.248 - for (InEdgeIt e(graph, n); e != INVALID; ++e)
2.249 - s += _lower[e];
2.250 - for (OutEdgeIt e(graph, n); e != INVALID; ++e)
2.251 - s -= _lower[e];
2.252 - supply[n] = s;
2.253 + Supply s = 0;
2.254 + if (n == _s) s = _flow_value;
2.255 + if (n == _t) s = -_flow_value;
2.256 + for (InEdgeIt e(graph, n); e != INVALID; ++e)
2.257 + s += _lower[e];
2.258 + for (OutEdgeIt e(graph, n); e != INVALID; ++e)
2.259 + s -= _lower[e];
2.260 + supply[n] = s;
2.261 }
2.262 valid_supply = true;
2.263 }
2.264 @@ -266,13 +253,12 @@
2.265 /// \param _s The source node.
2.266 /// \param _t The target node.
2.267 /// \param _flow_value The required amount of flow from node \c _s
2.268 - /// to node \c _t (i.e. the supply of \c _s and the demand of
2.269 - /// \c _t).
2.270 + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
2.271 CycleCanceling( const Graph &_graph,
2.272 - const CapacityMap &_capacity,
2.273 - const CostMap &_cost,
2.274 - Node _s, Node _t,
2.275 - Supply _flow_value ) :
2.276 + const CapacityMap &_capacity,
2.277 + const CostMap &_cost,
2.278 + Node _s, Node _t,
2.279 + Supply _flow_value ) :
2.280 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
2.281 supply(_graph, 0), flow(_graph, 0),
2.282 res_graph(_graph, capacity, flow), res_cost(cost)
2.283 @@ -282,6 +268,15 @@
2.284 valid_supply = true;
2.285 }
2.286
2.287 + /// \brief Runs the algorithm.
2.288 + ///
2.289 + /// Runs the algorithm.
2.290 + ///
2.291 + /// \return \c true if a feasible flow can be found.
2.292 + bool run() {
2.293 + return init() && start();
2.294 + }
2.295 +
2.296 /// \brief Returns a const reference to the flow map.
2.297 ///
2.298 /// Returns a const reference to the flow map.
2.299 @@ -300,22 +295,13 @@
2.300 Cost totalCost() const {
2.301 Cost c = 0;
2.302 for (EdgeIt e(graph); e != INVALID; ++e)
2.303 - c += flow[e] * cost[e];
2.304 + c += flow[e] * cost[e];
2.305 return c;
2.306 }
2.307
2.308 - /// \brief Runs the algorithm.
2.309 - ///
2.310 - /// Runs the algorithm.
2.311 - ///
2.312 - /// \return \c true if a feasible flow can be found.
2.313 - bool run() {
2.314 - return init() && start();
2.315 - }
2.316 -
2.317 protected:
2.318
2.319 - /// \brief Initializes the algorithm.
2.320 + /// Initializes the algorithm.
2.321 bool init() {
2.322 // Checking the sum of supply values
2.323 Supply sum = 0;
2.324 @@ -323,18 +309,17 @@
2.325 if (sum != 0) return false;
2.326
2.327 // Finding a feasible flow
2.328 - Circulation< Graph, ConstMap<Edge, Capacity>, CapacityRefMap,
2.329 - SupplyMap >
2.330 - circulation( graph, constMap<Edge>((Capacity)0), capacity,
2.331 - supply );
2.332 + Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
2.333 + SupplyMap >
2.334 + circulation( graph, constMap<Edge>((Capacity)0), capacity,
2.335 + supply );
2.336 circulation.flowMap(flow);
2.337 return circulation.run();
2.338 }
2.339
2.340 #ifdef LIMITED_CYCLE_CANCELING
2.341 /// \brief Executes a cycle-canceling algorithm using
2.342 - /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited
2.343 - /// iteration count.
2.344 + /// \ref Bellman-Ford algorithm with limited iteration count.
2.345 bool start() {
2.346 typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph);
2.347 typename ResGraph::template NodeMap<int> visited(res_graph);
2.348 @@ -347,85 +332,85 @@
2.349 int length_bound = STARTING_LIMIT;
2.350 bool optimal = false;
2.351 while (!optimal) {
2.352 - BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
2.353 - bf.predMap(pred);
2.354 - bf.init(0);
2.355 - int iter_num = 0;
2.356 - bool cycle_found = false;
2.357 - while (!cycle_found) {
2.358 + BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
2.359 + bf.predMap(pred);
2.360 + bf.init(0);
2.361 + int iter_num = 0;
2.362 + bool cycle_found = false;
2.363 + while (!cycle_found) {
2.364 #ifdef _NO_BACK_STEP_
2.365 - int curr_iter_num = length_bound <= node_num ?
2.366 - length_bound - iter_num : node_num - iter_num;
2.367 + int curr_iter_num = length_bound <= node_num ?
2.368 + length_bound - iter_num : node_num - iter_num;
2.369 #else
2.370 - int curr_iter_num = iter_num + length_bound <= node_num ?
2.371 - length_bound : node_num - iter_num;
2.372 + int curr_iter_num = iter_num + length_bound <= node_num ?
2.373 + length_bound : node_num - iter_num;
2.374 #endif
2.375 - iter_num += curr_iter_num;
2.376 - int real_iter_num = curr_iter_num;
2.377 - for (int i = 0; i < curr_iter_num; ++i) {
2.378 - if (bf.processNextWeakRound()) {
2.379 - real_iter_num = i;
2.380 - break;
2.381 - }
2.382 - }
2.383 - if (real_iter_num < curr_iter_num) {
2.384 - optimal = true;
2.385 - break;
2.386 - } else {
2.387 - // Searching for node disjoint negative cycles
2.388 - for (ResNodeIt n(res_graph); n != INVALID; ++n)
2.389 - visited[n] = 0;
2.390 - int id = 0;
2.391 - for (ResNodeIt n(res_graph); n != INVALID; ++n) {
2.392 - if (visited[n] > 0) continue;
2.393 - visited[n] = ++id;
2.394 - ResNode u = pred[n] == INVALID ?
2.395 - INVALID : res_graph.source(pred[n]);
2.396 - while (u != INVALID && visited[u] == 0) {
2.397 - visited[u] = id;
2.398 - u = pred[u] == INVALID ?
2.399 - INVALID : res_graph.source(pred[u]);
2.400 - }
2.401 - if (u != INVALID && visited[u] == id) {
2.402 - // Finding the negative cycle
2.403 - cycle_found = true;
2.404 - cycle.clear();
2.405 - ResEdge e = pred[u];
2.406 - cycle.push_back(e);
2.407 - Capacity d = res_graph.rescap(e);
2.408 - while (res_graph.source(e) != u) {
2.409 - cycle.push_back(e = pred[res_graph.source(e)]);
2.410 - if (res_graph.rescap(e) < d)
2.411 - d = res_graph.rescap(e);
2.412 - }
2.413 + iter_num += curr_iter_num;
2.414 + int real_iter_num = curr_iter_num;
2.415 + for (int i = 0; i < curr_iter_num; ++i) {
2.416 + if (bf.processNextWeakRound()) {
2.417 + real_iter_num = i;
2.418 + break;
2.419 + }
2.420 + }
2.421 + if (real_iter_num < curr_iter_num) {
2.422 + optimal = true;
2.423 + break;
2.424 + } else {
2.425 + // Searching for node disjoint negative cycles
2.426 + for (ResNodeIt n(res_graph); n != INVALID; ++n)
2.427 + visited[n] = 0;
2.428 + int id = 0;
2.429 + for (ResNodeIt n(res_graph); n != INVALID; ++n) {
2.430 + if (visited[n] > 0) continue;
2.431 + visited[n] = ++id;
2.432 + ResNode u = pred[n] == INVALID ?
2.433 + INVALID : res_graph.source(pred[n]);
2.434 + while (u != INVALID && visited[u] == 0) {
2.435 + visited[u] = id;
2.436 + u = pred[u] == INVALID ?
2.437 + INVALID : res_graph.source(pred[u]);
2.438 + }
2.439 + if (u != INVALID && visited[u] == id) {
2.440 + // Finding the negative cycle
2.441 + cycle_found = true;
2.442 + cycle.clear();
2.443 + ResEdge e = pred[u];
2.444 + cycle.push_back(e);
2.445 + Capacity d = res_graph.rescap(e);
2.446 + while (res_graph.source(e) != u) {
2.447 + cycle.push_back(e = pred[res_graph.source(e)]);
2.448 + if (res_graph.rescap(e) < d)
2.449 + d = res_graph.rescap(e);
2.450 + }
2.451 #ifdef _DEBUG_ITER_
2.452 - ++cycle_num;
2.453 + ++cycle_num;
2.454 #endif
2.455 - // Augmenting along the cycle
2.456 - for (int i = 0; i < cycle.size(); ++i)
2.457 - res_graph.augment(cycle[i], d);
2.458 + // Augmenting along the cycle
2.459 + for (int i = 0; i < cycle.size(); ++i)
2.460 + res_graph.augment(cycle[i], d);
2.461 #ifdef _ONLY_ONE_CYCLE_
2.462 - break;
2.463 + break;
2.464 #endif
2.465 - }
2.466 - }
2.467 - }
2.468 + }
2.469 + }
2.470 + }
2.471
2.472 - if (!cycle_found)
2.473 - length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
2.474 - }
2.475 + if (!cycle_found)
2.476 + length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
2.477 + }
2.478 }
2.479
2.480 #ifdef _DEBUG_ITER_
2.481 std::cout << "Limited cycle-canceling algorithm finished. "
2.482 - << "Found " << cycle_num << " negative cycles."
2.483 - << std::endl;
2.484 + << "Found " << cycle_num << " negative cycles."
2.485 + << std::endl;
2.486 #endif
2.487
2.488 - // Handling nonzero lower bounds
2.489 + // Handling non-zero lower bounds
2.490 if (lower) {
2.491 - for (EdgeIt e(graph); e != INVALID; ++e)
2.492 - flow[e] += (*lower)[e];
2.493 + for (EdgeIt e(graph); e != INVALID; ++e)
2.494 + flow[e] += (*lower)[e];
2.495 }
2.496 return true;
2.497 }
2.498 @@ -433,7 +418,7 @@
2.499
2.500 #ifdef MIN_MEAN_CYCLE_CANCELING
2.501 /// \brief Executes the minimum mean cycle-canceling algorithm
2.502 - /// using \ref lemon::MinMeanCycle "MinMeanCycle" class.
2.503 + /// using \ref MinMeanCycle.
2.504 bool start() {
2.505 typedef Path<ResGraph> ResPath;
2.506 MinMeanCycle<ResGraph, ResCostMap> mmc(res_graph, res_cost);
2.507 @@ -444,42 +429,42 @@
2.508 #endif
2.509 mmc.cyclePath(cycle).init();
2.510 if (mmc.findMinMean()) {
2.511 - while (mmc.cycleLength() < 0) {
2.512 + while (mmc.cycleLength() < 0) {
2.513 #ifdef _DEBUG_ITER_
2.514 - ++iter;
2.515 + ++cycle_num;
2.516 #endif
2.517 - // Finding the cycle
2.518 - mmc.findCycle();
2.519 + // Finding the cycle
2.520 + mmc.findCycle();
2.521
2.522 - // Finding the largest flow amount that can be augmented
2.523 - // along the cycle
2.524 - Capacity delta = 0;
2.525 - for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
2.526 - if (delta == 0 || res_graph.rescap(e) < delta)
2.527 - delta = res_graph.rescap(e);
2.528 - }
2.529 + // Finding the largest flow amount that can be augmented
2.530 + // along the cycle
2.531 + Capacity delta = 0;
2.532 + for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
2.533 + if (delta == 0 || res_graph.rescap(e) < delta)
2.534 + delta = res_graph.rescap(e);
2.535 + }
2.536
2.537 - // Augmenting along the cycle
2.538 - for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
2.539 - res_graph.augment(e, delta);
2.540 + // Augmenting along the cycle
2.541 + for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
2.542 + res_graph.augment(e, delta);
2.543
2.544 - // Finding the minimum cycle mean for the modified residual
2.545 - // graph
2.546 - mmc.reset();
2.547 - if (!mmc.findMinMean()) break;
2.548 - }
2.549 + // Finding the minimum cycle mean for the modified residual
2.550 + // graph
2.551 + mmc.reset();
2.552 + if (!mmc.findMinMean()) break;
2.553 + }
2.554 }
2.555
2.556 #ifdef _DEBUG_ITER_
2.557 std::cout << "Minimum mean cycle-canceling algorithm finished. "
2.558 - << "Found " << cycle_num << " negative cycles."
2.559 - << std::endl;
2.560 + << "Found " << cycle_num << " negative cycles."
2.561 + << std::endl;
2.562 #endif
2.563
2.564 - // Handling nonzero lower bounds
2.565 + // Handling non-zero lower bounds
2.566 if (lower) {
2.567 - for (EdgeIt e(graph); e != INVALID; ++e)
2.568 - flow[e] += (*lower)[e];
2.569 + for (EdgeIt e(graph); e != INVALID; ++e)
2.570 + flow[e] += (*lower)[e];
2.571 }
2.572 return true;
2.573 }
3.1 --- a/lemon/min_cost_flow.h Sun Jan 13 10:26:55 2008 +0000
3.2 +++ b/lemon/min_cost_flow.h Sun Jan 13 10:32:14 2008 +0000
3.3 @@ -33,19 +33,22 @@
3.4
3.5 /// \brief An efficient algorithm for finding a minimum cost flow.
3.6 ///
3.7 - /// \ref lemon::MinCostFlow "MinCostFlow" implements an efficient
3.8 - /// algorithm for finding a minimum cost flow.
3.9 + /// \ref MinCostFlow provides an efficient algorithm for finding
3.10 + /// a minimum cost flow.
3.11 ///
3.12 - /// \note \ref lemon::MinCostFlow "MinCostFlow" is just an alias for
3.13 - /// \ref lemon::NetworkSimplex "NetworkSimplex", wich is the most
3.14 - /// efficient implementation for the minimum cost flow problem in the
3.15 - /// LEMON library according to our benchmark tests.
3.16 + /// \note \ref MinCostFlow is just an alias for \ref NetworkSimplex,
3.17 + /// which is the most efficient implementation for the minimum cost
3.18 + /// flow problem in the LEMON library according to our benchmark
3.19 + /// tests.
3.20 ///
3.21 /// \note There are three implementations for the minimum cost flow
3.22 - /// problem, that can be used in the same way.
3.23 - /// - \ref lemon::CapacityScaling "CapacityScaling"
3.24 - /// - \ref lemon::CycleCanceling "CycleCanceling"
3.25 - /// - \ref lemon::NetworkSimplex "NetworkSimplex"
3.26 + /// problem, that can be used exactly the same way.
3.27 + /// - \ref CapacityScaling
3.28 + /// - \ref CycleCanceling
3.29 + /// - \ref NetworkSimplex
3.30 + ///
3.31 + /// \note For the detailed documentation of this class see
3.32 + /// \ref NetworkSimplex.
3.33 ///
3.34 /// \param Graph The directed graph type the algorithm runs on.
3.35 /// \param LowerMap The type of the lower bound map.
3.36 @@ -54,12 +57,12 @@
3.37 /// \param SupplyMap The type of the supply map.
3.38 ///
3.39 /// \warning
3.40 - /// - Edge capacities and costs should be nonnegative integers.
3.41 - /// However \c CostMap::Value should be signed type.
3.42 + /// - Edge capacities and costs should be non-negative integers.
3.43 + /// However \c CostMap::Value should be signed type.
3.44 /// - Supply values should be signed integers.
3.45 /// - \c LowerMap::Value must be convertible to
3.46 - /// \c CapacityMap::Value and \c CapacityMap::Value must be
3.47 - /// convertible to \c SupplyMap::Value.
3.48 + /// \c CapacityMap::Value and \c CapacityMap::Value must be
3.49 + /// convertible to \c SupplyMap::Value.
3.50 ///
3.51 /// \author Peter Kovacs
3.52
3.53 @@ -70,53 +73,49 @@
3.54 typename SupplyMap = typename Graph::template NodeMap
3.55 <typename CapacityMap::Value> >
3.56 class MinCostFlow :
3.57 - public NetworkSimplex< Graph,
3.58 - LowerMap,
3.59 - CapacityMap,
3.60 - CostMap,
3.61 - SupplyMap >
3.62 + public NetworkSimplex< Graph, LowerMap, CapacityMap,
3.63 + CostMap, SupplyMap >
3.64 {
3.65 typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
3.66 - CostMap, SupplyMap >
3.67 - MinCostFlowImpl;
3.68 + CostMap, SupplyMap > MinCostFlowImpl;
3.69 typedef typename Graph::Node Node;
3.70 typedef typename SupplyMap::Value Supply;
3.71
3.72 public:
3.73
3.74 - /// \brief General constructor of the class (with lower bounds).
3.75 - MinCostFlow( const Graph &_graph,
3.76 - const LowerMap &_lower,
3.77 - const CapacityMap &_capacity,
3.78 - const CostMap &_cost,
3.79 - const SupplyMap &_supply ) :
3.80 - MinCostFlowImpl(_graph, _lower, _capacity, _cost, _supply) {}
3.81 + /// General constructor of the class (with lower bounds).
3.82 + MinCostFlow( const Graph &graph,
3.83 + const LowerMap &lower,
3.84 + const CapacityMap &capacity,
3.85 + const CostMap &cost,
3.86 + const SupplyMap &supply ) :
3.87 + MinCostFlowImpl(graph, lower, capacity, cost, supply) {}
3.88
3.89 - /// \brief General constructor of the class (without lower bounds).
3.90 - MinCostFlow( const Graph &_graph,
3.91 - const CapacityMap &_capacity,
3.92 - const CostMap &_cost,
3.93 - const SupplyMap &_supply ) :
3.94 - MinCostFlowImpl(_graph, _capacity, _cost, _supply) {}
3.95 + /// General constructor of the class (without lower bounds).
3.96 + MinCostFlow( const Graph &graph,
3.97 + const CapacityMap &capacity,
3.98 + const CostMap &_ost,
3.99 + const SupplyMap &supply ) :
3.100 + MinCostFlowImpl(graph, capacity, cost, supply) {}
3.101
3.102 - /// \brief Simple constructor of the class (with lower bounds).
3.103 - MinCostFlow( const Graph &_graph,
3.104 - const LowerMap &_lower,
3.105 - const CapacityMap &_capacity,
3.106 - const CostMap &_cost,
3.107 - Node _s, Node _t,
3.108 - Supply _flow_value ) :
3.109 - MinCostFlowImpl( _graph, _lower, _capacity, _cost,
3.110 - _s, _t, _flow_value ) {}
3.111 + /// Simple constructor of the class (with lower bounds).
3.112 + MinCostFlow( const Graph &graph,
3.113 + const LowerMap &lower,
3.114 + const CapacityMap &capacity,
3.115 + const CostMap &_ost,
3.116 + Node s, Node t,
3.117 + Supply flow_value ) :
3.118 + MinCostFlowImpl( graph, lower, capacity, cost,
3.119 + s, t, flow_value ) {}
3.120
3.121 - /// \brief Simple constructor of the class (without lower bounds).
3.122 - MinCostFlow( const Graph &_graph,
3.123 - const CapacityMap &_capacity,
3.124 - const CostMap &_cost,
3.125 - Node _s, Node _t,
3.126 - Supply _flow_value ) :
3.127 - MinCostFlowImpl( _graph, _capacity, _cost,
3.128 - _s, _t, _flow_value ) {}
3.129 + /// Simple constructor of the class (without lower bounds).
3.130 + MinCostFlow( const Graph &graph,
3.131 + const CapacityMap &capacity,
3.132 + const CostMap &cost,
3.133 + Node s, Node t,
3.134 + Supply flow_value ) :
3.135 + MinCostFlowImpl( graph, capacity, cost,
3.136 + s, t, flow_value ) {}
3.137
3.138 }; //class MinCostFlow
3.139
4.1 --- a/lemon/min_cost_max_flow.h Sun Jan 13 10:26:55 2008 +0000
4.2 +++ b/lemon/min_cost_max_flow.h Sun Jan 13 10:32:14 2008 +0000
4.3 @@ -22,8 +22,7 @@
4.4 /// \ingroup min_cost_flow
4.5 ///
4.6 /// \file
4.7 -/// \brief An efficient algorithm for finding a minimum cost maximum
4.8 -/// flow.
4.9 +/// \brief An efficient algorithm for finding a minimum cost maximum flow.
4.10
4.11 #include <lemon/preflow.h>
4.12 #include <lemon/network_simplex.h>
4.13 @@ -34,68 +33,65 @@
4.14 /// \addtogroup min_cost_flow
4.15 /// @{
4.16
4.17 - /// \brief An efficient algorithm for finding a minimum cost maximum
4.18 - /// flow.
4.19 + /// \brief An efficient algorithm for finding a minimum cost
4.20 + /// maximum flow.
4.21 ///
4.22 - /// \ref lemon::MinCostFlow "MinCostMaxFlow" implements an efficient
4.23 - /// algorithm for finding a maximum flow having minimal total cost
4.24 - /// from a given source node to a given target node in a directed
4.25 - /// graph.
4.26 + /// \ref MinCostMaxFlow implements an efficient algorithm for
4.27 + /// finding a maximum flow having minimal total cost from a given
4.28 + /// source node to a given target node in a directed graph.
4.29 ///
4.30 - /// \note \ref lemon::MinCostMaxFlow "MinCostMaxFlow" uses
4.31 - /// \ref lemon::Preflow "Preflow" algorithm for finding the maximum
4.32 - /// flow value and \ref lemon::NetworkSimplex "NetworkSimplex"
4.33 - /// algorithm for finding a minimum cost flow of that value.
4.34 + /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding
4.35 + /// the maximum flow value and \ref NetworkSimplex algorithm for
4.36 + /// finding a minimum cost flow of that value.
4.37 ///
4.38 /// \param Graph The directed graph type the algorithm runs on.
4.39 /// \param CapacityMap The type of the capacity (upper bound) map.
4.40 /// \param CostMap The type of the cost (length) map.
4.41 ///
4.42 /// \warning
4.43 - /// - Edge capacities and costs should be nonnegative integers.
4.44 - /// However \c CostMap::Value should be signed type.
4.45 + /// - Edge capacities and costs should be non-negative integers.
4.46 + /// However \c CostMap::Value should be signed type.
4.47 ///
4.48 /// \author Peter Kovacs
4.49
4.50 template < typename Graph,
4.51 - typename CapacityMap = typename Graph::template EdgeMap<int>,
4.52 - typename CostMap = typename Graph::template EdgeMap<int> >
4.53 + typename CapacityMap = typename Graph::template EdgeMap<int>,
4.54 + typename CostMap = typename Graph::template EdgeMap<int> >
4.55 class MinCostMaxFlow
4.56 {
4.57 typedef typename Graph::Node Node;
4.58 typedef typename Graph::Edge Edge;
4.59
4.60 typedef typename CapacityMap::Value Capacity;
4.61 + typedef typename CostMap::Value Cost;
4.62 typedef typename Graph::template NodeMap<Capacity> SupplyMap;
4.63 typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
4.64 - CostMap, SupplyMap >
4.65 + CostMap, SupplyMap >
4.66 MinCostFlowImpl;
4.67
4.68 public:
4.69
4.70 - /// \brief The type of the flow map.
4.71 + /// The type of the flow map.
4.72 typedef typename Graph::template EdgeMap<Capacity> FlowMap;
4.73 - typedef typename CostMap::Value Cost;
4.74
4.75 private:
4.76
4.77 - /// \brief The directed graph the algorithm runs on.
4.78 + /// The directed graph the algorithm runs on.
4.79 const Graph &graph;
4.80 - /// \brief The modified capacity map.
4.81 + /// The modified capacity map.
4.82 const CapacityMap &capacity;
4.83 - /// \brief The cost map.
4.84 + /// The cost map.
4.85 const CostMap &cost;
4.86 - /// \brief The source node.
4.87 + /// The edge map of the found flow.
4.88 + FlowMap flow;
4.89 + /// The source node.
4.90 Node source;
4.91 - /// \brief The target node.
4.92 + /// The target node.
4.93 Node target;
4.94 - /// \brief The edge map of the found flow.
4.95 - FlowMap flow;
4.96
4.97 - typedef Preflow<Graph, CapacityMap> PreflowImpl;
4.98 - /// \brief \ref lemon::Preflow "Preflow" class for finding the
4.99 - /// maximum flow value.
4.100 - PreflowImpl preflow;
4.101 + typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
4.102 + /// \brief \ref Preflow class for finding the maximum flow value.
4.103 + MaxFlowImpl preflow;
4.104
4.105 public:
4.106
4.107 @@ -109,9 +105,9 @@
4.108 /// \param _s The source node.
4.109 /// \param _t The target node.
4.110 MinCostMaxFlow( const Graph &_graph,
4.111 - const CapacityMap &_capacity,
4.112 - const CostMap &_cost,
4.113 - Node _s, Node _t ) :
4.114 + const CapacityMap &_capacity,
4.115 + const CostMap &_cost,
4.116 + Node _s, Node _t ) :
4.117 graph(_graph), capacity(_capacity), cost(_cost),
4.118 source(_s), target(_t), flow(_graph),
4.119 preflow(_graph, _capacity, _s, _t)
4.120 @@ -135,7 +131,7 @@
4.121 Cost totalCost() const {
4.122 Cost c = 0;
4.123 for (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
4.124 - c += flow[e] * cost[e];
4.125 + c += flow[e] * cost[e];
4.126 return c;
4.127 }
4.128
4.129 @@ -144,7 +140,7 @@
4.130 preflow.flowMap(flow);
4.131 preflow.runMinCut();
4.132 MinCostFlowImpl mcf_impl( graph, capacity, cost,
4.133 - source, target, preflow.flowValue() );
4.134 + source, target, preflow.flowValue() );
4.135 mcf_impl.run();
4.136 flow = mcf_impl.flowMap();
4.137 }
5.1 --- a/lemon/network_simplex.h Sun Jan 13 10:26:55 2008 +0000
5.2 +++ b/lemon/network_simplex.h Sun Jan 13 10:32:14 2008 +0000
5.3 @@ -22,8 +22,7 @@
5.4 /// \ingroup min_cost_flow
5.5 ///
5.6 /// \file
5.7 -/// \brief The network simplex algorithm for finding a minimum cost
5.8 -/// flow.
5.9 +/// \brief The network simplex algorithm for finding a minimum cost flow.
5.10
5.11 #include <limits>
5.12 #include <lemon/graph_adaptor.h>
5.13 @@ -40,30 +39,29 @@
5.14 //#define _DEBUG_ITER_
5.15
5.16
5.17 -/// \brief State constant for edges at their lower bounds.
5.18 -#define LOWER 1
5.19 -/// \brief State constant for edges in the spanning tree.
5.20 -#define TREE 0
5.21 -/// \brief State constant for edges at their upper bounds.
5.22 -#define UPPER -1
5.23 +// State constant for edges at their lower bounds.
5.24 +#define LOWER 1
5.25 +// State constant for edges in the spanning tree.
5.26 +#define TREE 0
5.27 +// State constant for edges at their upper bounds.
5.28 +#define UPPER -1
5.29
5.30 #ifdef EDGE_BLOCK_PIVOT
5.31 #include <cmath>
5.32 - /// \brief Lower bound for the size of blocks.
5.33 - #define MIN_BLOCK_SIZE 10
5.34 + #define MIN_BLOCK_SIZE 10
5.35 #endif
5.36
5.37 #ifdef CANDIDATE_LIST_PIVOT
5.38 #include <vector>
5.39 - #define LIST_LENGTH_DIV 50
5.40 - #define MINOR_LIMIT_DIV 200
5.41 + #define LIST_LENGTH_DIV 50
5.42 + #define MINOR_LIMIT_DIV 200
5.43 #endif
5.44
5.45 #ifdef SORTED_LIST_PIVOT
5.46 #include <vector>
5.47 #include <algorithm>
5.48 #define LIST_LENGTH_DIV 100
5.49 - #define LOWER_DIV 4
5.50 + #define LOWER_DIV 4
5.51 #endif
5.52
5.53 namespace lemon {
5.54 @@ -74,8 +72,8 @@
5.55 /// \brief Implementation of the network simplex algorithm for
5.56 /// finding a minimum cost flow.
5.57 ///
5.58 - /// \ref lemon::NetworkSimplex "NetworkSimplex" implements the
5.59 - /// network simplex algorithm for finding a minimum cost flow.
5.60 + /// \ref NetworkSimplex implements the network simplex algorithm for
5.61 + /// finding a minimum cost flow.
5.62 ///
5.63 /// \param Graph The directed graph type the algorithm runs on.
5.64 /// \param LowerMap The type of the lower bound map.
5.65 @@ -84,12 +82,12 @@
5.66 /// \param SupplyMap The type of the supply map.
5.67 ///
5.68 /// \warning
5.69 - /// - Edge capacities and costs should be nonnegative integers.
5.70 - /// However \c CostMap::Value should be signed type.
5.71 + /// - Edge capacities and costs should be non-negative integers.
5.72 + /// However \c CostMap::Value should be signed type.
5.73 /// - Supply values should be signed integers.
5.74 /// - \c LowerMap::Value must be convertible to
5.75 - /// \c CapacityMap::Value and \c CapacityMap::Value must be
5.76 - /// convertible to \c SupplyMap::Value.
5.77 + /// \c CapacityMap::Value and \c CapacityMap::Value must be
5.78 + /// convertible to \c SupplyMap::Value.
5.79 ///
5.80 /// \author Peter Kovacs
5.81
5.82 @@ -107,12 +105,7 @@
5.83 typedef typename SupplyMap::Value Supply;
5.84
5.85 typedef SmartGraph SGraph;
5.86 - typedef typename SGraph::Node Node;
5.87 - typedef typename SGraph::NodeIt NodeIt;
5.88 - typedef typename SGraph::Edge Edge;
5.89 - typedef typename SGraph::EdgeIt EdgeIt;
5.90 - typedef typename SGraph::InEdgeIt InEdgeIt;
5.91 - typedef typename SGraph::OutEdgeIt OutEdgeIt;
5.92 + GRAPH_TYPEDEFS(typename SGraph);
5.93
5.94 typedef typename SGraph::template EdgeMap<Lower> SLowerMap;
5.95 typedef typename SGraph::template EdgeMap<Capacity> SCapacityMap;
5.96 @@ -131,14 +124,14 @@
5.97
5.98 public:
5.99
5.100 - /// \brief The type of the flow map.
5.101 + /// The type of the flow map.
5.102 typedef typename Graph::template EdgeMap<Capacity> FlowMap;
5.103 - /// \brief The type of the potential map.
5.104 + /// The type of the potential map.
5.105 typedef typename Graph::template NodeMap<Cost> PotentialMap;
5.106
5.107 protected:
5.108
5.109 - /// \brief Map adaptor class for handling reduced edge costs.
5.110 + /// Map adaptor class for handling reduced edge costs.
5.111 class ReducedCostMap : public MapBase<Edge, Cost>
5.112 {
5.113 private:
5.114 @@ -150,65 +143,73 @@
5.115 public:
5.116
5.117 ReducedCostMap( const SGraph &_gr,
5.118 - const SCostMap &_cm,
5.119 - const SPotentialMap &_pm ) :
5.120 - gr(_gr), cost_map(_cm), pot_map(_pm) {}
5.121 + const SCostMap &_cm,
5.122 + const SPotentialMap &_pm ) :
5.123 + gr(_gr), cost_map(_cm), pot_map(_pm) {}
5.124
5.125 Cost operator[](const Edge &e) const {
5.126 - return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
5.127 + return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
5.128 }
5.129
5.130 }; //class ReducedCostMap
5.131
5.132 protected:
5.133
5.134 - /// \brief The directed graph the algorithm runs on.
5.135 + /// The directed graph the algorithm runs on.
5.136 SGraph graph;
5.137 - /// \brief The original graph.
5.138 + /// The original graph.
5.139 const Graph &graph_ref;
5.140 - /// \brief The original lower bound map.
5.141 + /// The original lower bound map.
5.142 const LowerMap *lower;
5.143 - /// \brief The capacity map.
5.144 + /// The capacity map.
5.145 SCapacityMap capacity;
5.146 - /// \brief The cost map.
5.147 + /// The cost map.
5.148 SCostMap cost;
5.149 - /// \brief The supply map.
5.150 + /// The supply map.
5.151 SSupplyMap supply;
5.152 - /// \brief The reduced cost map.
5.153 + /// The reduced cost map.
5.154 ReducedCostMap red_cost;
5.155 - /// \brief The sum of supply values equals zero.
5.156 bool valid_supply;
5.157
5.158 - /// \brief The edge map of the current flow.
5.159 + /// The edge map of the current flow.
5.160 SCapacityMap flow;
5.161 - /// \brief The edge map of the found flow on the original graph.
5.162 + /// The potential node map.
5.163 + SPotentialMap potential;
5.164 FlowMap flow_result;
5.165 - /// \brief The potential node map.
5.166 - SPotentialMap potential;
5.167 - /// \brief The potential node map on the original graph.
5.168 PotentialMap potential_result;
5.169
5.170 - /// \brief Node reference for the original graph.
5.171 + /// Node reference for the original graph.
5.172 NodeRefMap node_ref;
5.173 - /// \brief Edge reference for the original graph.
5.174 + /// Edge reference for the original graph.
5.175 EdgeRefMap edge_ref;
5.176
5.177 - /// \brief The depth node map of the spanning tree structure.
5.178 + /// The \c depth node map of the spanning tree structure.
5.179 IntNodeMap depth;
5.180 - /// \brief The parent node map of the spanning tree structure.
5.181 + /// The \c parent node map of the spanning tree structure.
5.182 NodeNodeMap parent;
5.183 - /// \brief The pred_edge node map of the spanning tree structure.
5.184 + /// The \c pred_edge node map of the spanning tree structure.
5.185 EdgeNodeMap pred_edge;
5.186 - /// \brief The thread node map of the spanning tree structure.
5.187 + /// The \c thread node map of the spanning tree structure.
5.188 NodeNodeMap thread;
5.189 - /// \brief The forward node map of the spanning tree structure.
5.190 + /// The \c forward node map of the spanning tree structure.
5.191 BoolNodeMap forward;
5.192 - /// \brief The state edge map.
5.193 + /// The state edge map.
5.194 IntEdgeMap state;
5.195 + /// The root node of the starting spanning tree.
5.196 + Node root;
5.197
5.198 + // The entering edge of the current pivot iteration.
5.199 + Edge in_edge;
5.200 + // Temporary nodes used in the current pivot iteration.
5.201 + Node join, u_in, v_in, u_out, v_out;
5.202 + Node right, first, second, last;
5.203 + Node stem, par_stem, new_stem;
5.204 + // The maximum augment amount along the found cycle in the current
5.205 + // pivot iteration.
5.206 + Capacity delta;
5.207
5.208 #ifdef EDGE_BLOCK_PIVOT
5.209 - /// \brief The size of blocks for the "Edge Block" pivot rule.
5.210 + /// The size of blocks for the "Edge Block" pivot rule.
5.211 int block_size;
5.212 #endif
5.213 #ifdef CANDIDATE_LIST_PIVOT
5.214 @@ -234,18 +235,6 @@
5.215 int list_index;
5.216 #endif
5.217
5.218 - // Root node of the starting spanning tree.
5.219 - Node root;
5.220 - // The entering edge of the current pivot iteration.
5.221 - Edge in_edge;
5.222 - // Temporary nodes used in the current pivot iteration.
5.223 - Node join, u_in, v_in, u_out, v_out;
5.224 - Node right, first, second, last;
5.225 - Node stem, par_stem, new_stem;
5.226 - // The maximum augment amount along the cycle in the current pivot
5.227 - // iteration.
5.228 - Capacity delta;
5.229 -
5.230 public :
5.231
5.232 /// \brief General constructor of the class (with lower bounds).
5.233 @@ -258,10 +247,10 @@
5.234 /// \param _cost The cost (length) values of the edges.
5.235 /// \param _supply The supply values of the nodes (signed).
5.236 NetworkSimplex( const Graph &_graph,
5.237 - const LowerMap &_lower,
5.238 - const CapacityMap &_capacity,
5.239 - const CostMap &_cost,
5.240 - const SupplyMap &_supply ) :
5.241 + const LowerMap &_lower,
5.242 + const CapacityMap &_capacity,
5.243 + const CostMap &_cost,
5.244 + const SupplyMap &_supply ) :
5.245 graph_ref(_graph), lower(&_lower), capacity(graph), cost(graph),
5.246 supply(graph), flow(graph), flow_result(_graph), potential(graph),
5.247 potential_result(_graph), depth(graph), parent(graph),
5.248 @@ -272,29 +261,29 @@
5.249 // Checking the sum of supply values
5.250 Supply sum = 0;
5.251 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
5.252 - sum += _supply[n];
5.253 + sum += _supply[n];
5.254 if (!(valid_supply = sum == 0)) return;
5.255
5.256 // Copying graph_ref to graph
5.257 graph.reserveNode(countNodes(graph_ref) + 1);
5.258 graph.reserveEdge(countEdges(graph_ref) + countNodes(graph_ref));
5.259 copyGraph(graph, graph_ref)
5.260 - .edgeMap(cost, _cost)
5.261 - .nodeRef(node_ref)
5.262 - .edgeRef(edge_ref)
5.263 - .run();
5.264 + .edgeMap(cost, _cost)
5.265 + .nodeRef(node_ref)
5.266 + .edgeRef(edge_ref)
5.267 + .run();
5.268
5.269 - // Removing nonzero lower bounds
5.270 + // Removing non-zero lower bounds
5.271 for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) {
5.272 - capacity[edge_ref[e]] = _capacity[e] - _lower[e];
5.273 + capacity[edge_ref[e]] = _capacity[e] - _lower[e];
5.274 }
5.275 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) {
5.276 - Supply s = _supply[n];
5.277 - for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
5.278 - s += _lower[e];
5.279 - for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
5.280 - s -= _lower[e];
5.281 - supply[node_ref[n]] = s;
5.282 + Supply s = _supply[n];
5.283 + for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
5.284 + s += _lower[e];
5.285 + for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
5.286 + s -= _lower[e];
5.287 + supply[node_ref[n]] = s;
5.288 }
5.289 }
5.290
5.291 @@ -307,9 +296,9 @@
5.292 /// \param _cost The cost (length) values of the edges.
5.293 /// \param _supply The supply values of the nodes (signed).
5.294 NetworkSimplex( const Graph &_graph,
5.295 - const CapacityMap &_capacity,
5.296 - const CostMap &_cost,
5.297 - const SupplyMap &_supply ) :
5.298 + const CapacityMap &_capacity,
5.299 + const CostMap &_cost,
5.300 + const SupplyMap &_supply ) :
5.301 graph_ref(_graph), lower(NULL), capacity(graph), cost(graph),
5.302 supply(graph), flow(graph), flow_result(_graph), potential(graph),
5.303 potential_result(_graph), depth(graph), parent(graph),
5.304 @@ -320,17 +309,17 @@
5.305 // Checking the sum of supply values
5.306 Supply sum = 0;
5.307 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
5.308 - sum += _supply[n];
5.309 + sum += _supply[n];
5.310 if (!(valid_supply = sum == 0)) return;
5.311
5.312 // Copying graph_ref to graph
5.313 copyGraph(graph, graph_ref)
5.314 - .edgeMap(capacity, _capacity)
5.315 - .edgeMap(cost, _cost)
5.316 - .nodeMap(supply, _supply)
5.317 - .nodeRef(node_ref)
5.318 - .edgeRef(edge_ref)
5.319 - .run();
5.320 + .edgeMap(capacity, _capacity)
5.321 + .edgeMap(cost, _cost)
5.322 + .nodeMap(supply, _supply)
5.323 + .nodeRef(node_ref)
5.324 + .edgeRef(edge_ref)
5.325 + .run();
5.326 }
5.327
5.328 /// \brief Simple constructor of the class (with lower bounds).
5.329 @@ -344,15 +333,14 @@
5.330 /// \param _s The source node.
5.331 /// \param _t The target node.
5.332 /// \param _flow_value The required amount of flow from node \c _s
5.333 - /// to node \c _t (i.e. the supply of \c _s and the demand of
5.334 - /// \c _t).
5.335 + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
5.336 NetworkSimplex( const Graph &_graph,
5.337 - const LowerMap &_lower,
5.338 - const CapacityMap &_capacity,
5.339 - const CostMap &_cost,
5.340 - typename Graph::Node _s,
5.341 - typename Graph::Node _t,
5.342 - typename SupplyMap::Value _flow_value ) :
5.343 + const LowerMap &_lower,
5.344 + const CapacityMap &_capacity,
5.345 + const CostMap &_cost,
5.346 + typename Graph::Node _s,
5.347 + typename Graph::Node _t,
5.348 + typename SupplyMap::Value _flow_value ) :
5.349 graph_ref(_graph), lower(&_lower), capacity(graph), cost(graph),
5.350 supply(graph), flow(graph), flow_result(_graph), potential(graph),
5.351 potential_result(_graph), depth(graph), parent(graph),
5.352 @@ -362,24 +350,24 @@
5.353 {
5.354 // Copying graph_ref to graph
5.355 copyGraph(graph, graph_ref)
5.356 - .edgeMap(cost, _cost)
5.357 - .nodeRef(node_ref)
5.358 - .edgeRef(edge_ref)
5.359 - .run();
5.360 + .edgeMap(cost, _cost)
5.361 + .nodeRef(node_ref)
5.362 + .edgeRef(edge_ref)
5.363 + .run();
5.364
5.365 - // Removing nonzero lower bounds
5.366 + // Removing non-zero lower bounds
5.367 for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) {
5.368 - capacity[edge_ref[e]] = _capacity[e] - _lower[e];
5.369 + capacity[edge_ref[e]] = _capacity[e] - _lower[e];
5.370 }
5.371 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) {
5.372 - Supply s = 0;
5.373 - if (n == _s) s = _flow_value;
5.374 - if (n == _t) s = -_flow_value;
5.375 - for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
5.376 - s += _lower[e];
5.377 - for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
5.378 - s -= _lower[e];
5.379 - supply[node_ref[n]] = s;
5.380 + Supply s = 0;
5.381 + if (n == _s) s = _flow_value;
5.382 + if (n == _t) s = -_flow_value;
5.383 + for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e)
5.384 + s += _lower[e];
5.385 + for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e)
5.386 + s -= _lower[e];
5.387 + supply[node_ref[n]] = s;
5.388 }
5.389 valid_supply = true;
5.390 }
5.391 @@ -394,14 +382,13 @@
5.392 /// \param _s The source node.
5.393 /// \param _t The target node.
5.394 /// \param _flow_value The required amount of flow from node \c _s
5.395 - /// to node \c _t (i.e. the supply of \c _s and the demand of
5.396 - /// \c _t).
5.397 + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
5.398 NetworkSimplex( const Graph &_graph,
5.399 - const CapacityMap &_capacity,
5.400 - const CostMap &_cost,
5.401 - typename Graph::Node _s,
5.402 - typename Graph::Node _t,
5.403 - typename SupplyMap::Value _flow_value ) :
5.404 + const CapacityMap &_capacity,
5.405 + const CostMap &_cost,
5.406 + typename Graph::Node _s,
5.407 + typename Graph::Node _t,
5.408 + typename SupplyMap::Value _flow_value ) :
5.409 graph_ref(_graph), lower(NULL), capacity(graph), cost(graph),
5.410 supply(graph, 0), flow(graph), flow_result(_graph), potential(graph),
5.411 potential_result(_graph), depth(graph), parent(graph),
5.412 @@ -411,16 +398,25 @@
5.413 {
5.414 // Copying graph_ref to graph
5.415 copyGraph(graph, graph_ref)
5.416 - .edgeMap(capacity, _capacity)
5.417 - .edgeMap(cost, _cost)
5.418 - .nodeRef(node_ref)
5.419 - .edgeRef(edge_ref)
5.420 - .run();
5.421 + .edgeMap(capacity, _capacity)
5.422 + .edgeMap(cost, _cost)
5.423 + .nodeRef(node_ref)
5.424 + .edgeRef(edge_ref)
5.425 + .run();
5.426 supply[node_ref[_s]] = _flow_value;
5.427 supply[node_ref[_t]] = -_flow_value;
5.428 valid_supply = true;
5.429 }
5.430
5.431 + /// \brief Runs the algorithm.
5.432 + ///
5.433 + /// Runs the algorithm.
5.434 + ///
5.435 + /// \return \c true if a feasible flow can be found.
5.436 + bool run() {
5.437 + return init() && start();
5.438 + }
5.439 +
5.440 /// \brief Returns a const reference to the flow map.
5.441 ///
5.442 /// Returns a const reference to the flow map.
5.443 @@ -450,19 +446,10 @@
5.444 Cost totalCost() const {
5.445 Cost c = 0;
5.446 for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
5.447 - c += flow_result[e] * cost[edge_ref[e]];
5.448 + c += flow_result[e] * cost[edge_ref[e]];
5.449 return c;
5.450 }
5.451
5.452 - /// \brief Runs the algorithm.
5.453 - ///
5.454 - /// Runs the algorithm.
5.455 - ///
5.456 - /// \return \c true if a feasible flow can be found.
5.457 - bool run() {
5.458 - return init() && start();
5.459 - }
5.460 -
5.461 protected:
5.462
5.463 /// \brief Extends the underlaying graph and initializes all the
5.464 @@ -472,8 +459,8 @@
5.465
5.466 // Initializing state and flow maps
5.467 for (EdgeIt e(graph); e != INVALID; ++e) {
5.468 - flow[e] = 0;
5.469 - state[e] = LOWER;
5.470 + flow[e] = 0;
5.471 + state[e] = LOWER;
5.472 }
5.473
5.474 // Adding an artificial root node to the graph
5.475 @@ -491,27 +478,27 @@
5.476 Edge e;
5.477 Cost max_cost = std::numeric_limits<Cost>::max() / 4;
5.478 for (NodeIt u(graph); u != INVALID; ++u) {
5.479 - if (u == root) continue;
5.480 - thread[last] = u;
5.481 - last = u;
5.482 - parent[u] = root;
5.483 - depth[u] = 1;
5.484 - sum += supply[u];
5.485 - if (supply[u] >= 0) {
5.486 - e = graph.addEdge(u, root);
5.487 - flow[e] = supply[u];
5.488 - forward[u] = true;
5.489 - potential[u] = max_cost;
5.490 - } else {
5.491 - e = graph.addEdge(root, u);
5.492 - flow[e] = -supply[u];
5.493 - forward[u] = false;
5.494 - potential[u] = -max_cost;
5.495 - }
5.496 - cost[e] = max_cost;
5.497 - capacity[e] = std::numeric_limits<Capacity>::max();
5.498 - state[e] = TREE;
5.499 - pred_edge[u] = e;
5.500 + if (u == root) continue;
5.501 + thread[last] = u;
5.502 + last = u;
5.503 + parent[u] = root;
5.504 + depth[u] = 1;
5.505 + sum += supply[u];
5.506 + if (supply[u] >= 0) {
5.507 + e = graph.addEdge(u, root);
5.508 + flow[e] = supply[u];
5.509 + forward[u] = true;
5.510 + potential[u] = max_cost;
5.511 + } else {
5.512 + e = graph.addEdge(root, u);
5.513 + flow[e] = -supply[u];
5.514 + forward[u] = false;
5.515 + potential[u] = -max_cost;
5.516 + }
5.517 + cost[e] = max_cost;
5.518 + capacity[e] = std::numeric_limits<Capacity>::max();
5.519 + state[e] = TREE;
5.520 + pred_edge[u] = e;
5.521 }
5.522 thread[last] = root;
5.523
5.524 @@ -520,8 +507,6 @@
5.525 int edge_num = countEdges(graph);
5.526 block_size = 2 * int(sqrt(countEdges(graph)));
5.527 if (block_size < MIN_BLOCK_SIZE) block_size = MIN_BLOCK_SIZE;
5.528 -// block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
5.529 -// edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
5.530 #endif
5.531 #ifdef CANDIDATE_LIST_PIVOT
5.532 int edge_num = countEdges(graph);
5.533 @@ -543,18 +528,18 @@
5.534 /// pivot rule.
5.535 bool findEnteringEdge(EdgeIt &next_edge) {
5.536 for (EdgeIt e = next_edge; e != INVALID; ++e) {
5.537 - if (state[e] * red_cost[e] < 0) {
5.538 - in_edge = e;
5.539 - next_edge = ++e;
5.540 - return true;
5.541 - }
5.542 + if (state[e] * red_cost[e] < 0) {
5.543 + in_edge = e;
5.544 + next_edge = ++e;
5.545 + return true;
5.546 + }
5.547 }
5.548 for (EdgeIt e(graph); e != next_edge; ++e) {
5.549 - if (state[e] * red_cost[e] < 0) {
5.550 - in_edge = e;
5.551 - next_edge = ++e;
5.552 - return true;
5.553 - }
5.554 + if (state[e] * red_cost[e] < 0) {
5.555 + in_edge = e;
5.556 + next_edge = ++e;
5.557 + return true;
5.558 + }
5.559 }
5.560 return false;
5.561 }
5.562 @@ -566,10 +551,10 @@
5.563 bool findEnteringEdge() {
5.564 Cost min = 0;
5.565 for (EdgeIt e(graph); e != INVALID; ++e) {
5.566 - if (state[e] * red_cost[e] < min) {
5.567 - min = state[e] * red_cost[e];
5.568 - in_edge = e;
5.569 - }
5.570 + if (state[e] * red_cost[e] < min) {
5.571 + min = state[e] * red_cost[e];
5.572 + in_edge = e;
5.573 + }
5.574 }
5.575 return min < 0;
5.576 }
5.577 @@ -584,30 +569,30 @@
5.578 EdgeIt min_edge(graph);
5.579 int cnt = 0;
5.580 for (EdgeIt e = next_edge; e != INVALID; ++e) {
5.581 - if ((curr = state[e] * red_cost[e]) < min) {
5.582 - min = curr;
5.583 - min_edge = e;
5.584 - }
5.585 - if (++cnt == block_size) {
5.586 - if (min < 0) break;
5.587 - cnt = 0;
5.588 - }
5.589 + if ((curr = state[e] * red_cost[e]) < min) {
5.590 + min = curr;
5.591 + min_edge = e;
5.592 + }
5.593 + if (++cnt == block_size) {
5.594 + if (min < 0) break;
5.595 + cnt = 0;
5.596 + }
5.597 }
5.598 if (!(min < 0)) {
5.599 - for (EdgeIt e(graph); e != next_edge; ++e) {
5.600 - if ((curr = state[e] * red_cost[e]) < min) {
5.601 - min = curr;
5.602 - min_edge = e;
5.603 - }
5.604 - if (++cnt == block_size) {
5.605 - if (min < 0) break;
5.606 - cnt = 0;
5.607 - }
5.608 - }
5.609 + for (EdgeIt e(graph); e != next_edge; ++e) {
5.610 + if ((curr = state[e] * red_cost[e]) < min) {
5.611 + min = curr;
5.612 + min_edge = e;
5.613 + }
5.614 + if (++cnt == block_size) {
5.615 + if (min < 0) break;
5.616 + cnt = 0;
5.617 + }
5.618 + }
5.619 }
5.620 in_edge = min_edge;
5.621 if ((next_edge = ++min_edge) == INVALID)
5.622 - next_edge = EdgeIt(graph);
5.623 + next_edge = EdgeIt(graph);
5.624 return min < 0;
5.625 }
5.626 #endif
5.627 @@ -619,15 +604,15 @@
5.628 typedef typename std::vector<Edge>::iterator ListIt;
5.629
5.630 if (minor_count >= minor_limit || candidates.size() == 0) {
5.631 - // Major iteration
5.632 - candidates.clear();
5.633 - for (EdgeIt e(graph); e != INVALID; ++e) {
5.634 - if (state[e] * red_cost[e] < 0) {
5.635 - candidates.push_back(e);
5.636 - if (candidates.size() == list_length) break;
5.637 - }
5.638 - }
5.639 - if (candidates.size() == 0) return false;
5.640 + // Major iteration
5.641 + candidates.clear();
5.642 + for (EdgeIt e(graph); e != INVALID; ++e) {
5.643 + if (state[e] * red_cost[e] < 0) {
5.644 + candidates.push_back(e);
5.645 + if (candidates.size() == list_length) break;
5.646 + }
5.647 + }
5.648 + if (candidates.size() == 0) return false;
5.649 }
5.650
5.651 // Minor iteration
5.652 @@ -636,10 +621,10 @@
5.653 Edge e;
5.654 for (int i = 0; i < candidates.size(); ++i) {
5.655 e = candidates[i];
5.656 - if (state[e] * red_cost[e] < min) {
5.657 - min = state[e] * red_cost[e];
5.658 - in_edge = e;
5.659 - }
5.660 + if (state[e] * red_cost[e] < min) {
5.661 + min = state[e] * red_cost[e];
5.662 + in_edge = e;
5.663 + }
5.664 }
5.665 return true;
5.666 }
5.667 @@ -655,9 +640,9 @@
5.668 const ReducedCostMap &rc;
5.669 public:
5.670 SortFunc(const IntEdgeMap &_st, const ReducedCostMap &_rc) :
5.671 - st(_st), rc(_rc) {}
5.672 + st(_st), rc(_rc) {}
5.673 bool operator()(const Edge &e1, const Edge &e2) {
5.674 - return st[e1] * rc[e1] < st[e2] * rc[e2];
5.675 + return st[e1] * rc[e1] < st[e2] * rc[e2];
5.676 }
5.677 };
5.678
5.679 @@ -668,19 +653,19 @@
5.680
5.681 // Minor iteration
5.682 while (list_index < candidates.size()) {
5.683 - in_edge = candidates[list_index++];
5.684 - if (state[in_edge] * red_cost[in_edge] < 0) return true;
5.685 + in_edge = candidates[list_index++];
5.686 + if (state[in_edge] * red_cost[in_edge] < 0) return true;
5.687 }
5.688
5.689 // Major iteration
5.690 candidates.clear();
5.691 Cost curr, min = 0;
5.692 for (EdgeIt e(graph); e != INVALID; ++e) {
5.693 - if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) {
5.694 - candidates.push_back(e);
5.695 - if (curr < min) min = curr;
5.696 - if (candidates.size() == list_length) break;
5.697 - }
5.698 + if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) {
5.699 + candidates.push_back(e);
5.700 + if (curr < min) min = curr;
5.701 + if (candidates.size() == list_length) break;
5.702 + }
5.703 }
5.704 if (candidates.size() == 0) return false;
5.705 sort(candidates.begin(), candidates.end(), sort_func);
5.706 @@ -696,12 +681,12 @@
5.707 Node u = graph.source(in_edge);
5.708 Node v = graph.target(in_edge);
5.709 while (u != v) {
5.710 - if (depth[u] == depth[v]) {
5.711 - u = parent[u];
5.712 - v = parent[v];
5.713 - }
5.714 - else if (depth[u] > depth[v]) u = parent[u];
5.715 - else v = parent[v];
5.716 + if (depth[u] == depth[v]) {
5.717 + u = parent[u];
5.718 + v = parent[v];
5.719 + }
5.720 + else if (depth[u] > depth[v]) u = parent[u];
5.721 + else v = parent[v];
5.722 }
5.723 return u;
5.724 }
5.725 @@ -712,11 +697,11 @@
5.726 // Initializing first and second nodes according to the direction
5.727 // of the cycle
5.728 if (state[in_edge] == LOWER) {
5.729 - first = graph.source(in_edge);
5.730 - second = graph.target(in_edge);
5.731 + first = graph.source(in_edge);
5.732 + second = graph.target(in_edge);
5.733 } else {
5.734 - first = graph.target(in_edge);
5.735 - second = graph.source(in_edge);
5.736 + first = graph.target(in_edge);
5.737 + second = graph.source(in_edge);
5.738 }
5.739 delta = capacity[in_edge];
5.740 bool result = false;
5.741 @@ -726,56 +711,56 @@
5.742 // Searching the cycle along the path form the first node to the
5.743 // root node
5.744 for (Node u = first; u != join; u = parent[u]) {
5.745 - e = pred_edge[u];
5.746 - d = forward[u] ? flow[e] : capacity[e] - flow[e];
5.747 - if (d < delta) {
5.748 - delta = d;
5.749 - u_out = u;
5.750 - u_in = first;
5.751 - v_in = second;
5.752 - result = true;
5.753 - }
5.754 + e = pred_edge[u];
5.755 + d = forward[u] ? flow[e] : capacity[e] - flow[e];
5.756 + if (d < delta) {
5.757 + delta = d;
5.758 + u_out = u;
5.759 + u_in = first;
5.760 + v_in = second;
5.761 + result = true;
5.762 + }
5.763 }
5.764 // Searching the cycle along the path form the second node to the
5.765 // root node
5.766 for (Node u = second; u != join; u = parent[u]) {
5.767 - e = pred_edge[u];
5.768 - d = forward[u] ? capacity[e] - flow[e] : flow[e];
5.769 - if (d <= delta) {
5.770 - delta = d;
5.771 - u_out = u;
5.772 - u_in = second;
5.773 - v_in = first;
5.774 - result = true;
5.775 - }
5.776 + e = pred_edge[u];
5.777 + d = forward[u] ? capacity[e] - flow[e] : flow[e];
5.778 + if (d <= delta) {
5.779 + delta = d;
5.780 + u_out = u;
5.781 + u_in = second;
5.782 + v_in = first;
5.783 + result = true;
5.784 + }
5.785 }
5.786 return result;
5.787 }
5.788
5.789 - /// \brief Changes flow and state edge maps.
5.790 + /// \brief Changes \c flow and \c state edge maps.
5.791 void changeFlows(bool change) {
5.792 // Augmenting along the cycle
5.793 if (delta > 0) {
5.794 - Capacity val = state[in_edge] * delta;
5.795 - flow[in_edge] += val;
5.796 - for (Node u = graph.source(in_edge); u != join; u = parent[u]) {
5.797 - flow[pred_edge[u]] += forward[u] ? -val : val;
5.798 - }
5.799 - for (Node u = graph.target(in_edge); u != join; u = parent[u]) {
5.800 - flow[pred_edge[u]] += forward[u] ? val : -val;
5.801 - }
5.802 + Capacity val = state[in_edge] * delta;
5.803 + flow[in_edge] += val;
5.804 + for (Node u = graph.source(in_edge); u != join; u = parent[u]) {
5.805 + flow[pred_edge[u]] += forward[u] ? -val : val;
5.806 + }
5.807 + for (Node u = graph.target(in_edge); u != join; u = parent[u]) {
5.808 + flow[pred_edge[u]] += forward[u] ? val : -val;
5.809 + }
5.810 }
5.811 // Updating the state of the entering and leaving edges
5.812 if (change) {
5.813 - state[in_edge] = TREE;
5.814 - state[pred_edge[u_out]] =
5.815 - (flow[pred_edge[u_out]] == 0) ? LOWER : UPPER;
5.816 + state[in_edge] = TREE;
5.817 + state[pred_edge[u_out]] =
5.818 + (flow[pred_edge[u_out]] == 0) ? LOWER : UPPER;
5.819 } else {
5.820 - state[in_edge] = -state[in_edge];
5.821 + state[in_edge] = -state[in_edge];
5.822 }
5.823 }
5.824
5.825 - /// \brief Updates thread and parent node maps.
5.826 + /// \brief Updates \c thread and \c parent node maps.
5.827 void updateThreadParent() {
5.828 Node u;
5.829 v_out = parent[u_out];
5.830 @@ -783,12 +768,12 @@
5.831 // Handling the case when join and v_out coincide
5.832 bool par_first = false;
5.833 if (join == v_out) {
5.834 - for (u = join; u != u_in && u != v_in; u = thread[u]) ;
5.835 - if (u == v_in) {
5.836 - par_first = true;
5.837 - while (thread[u] != u_out) u = thread[u];
5.838 - first = u;
5.839 - }
5.840 + for (u = join; u != u_in && u != v_in; u = thread[u]) ;
5.841 + if (u == v_in) {
5.842 + par_first = true;
5.843 + while (thread[u] != u_out) u = thread[u];
5.844 + first = u;
5.845 + }
5.846 }
5.847
5.848 // Finding the last successor of u_in (u) and the node after it
5.849 @@ -796,8 +781,8 @@
5.850 for (u = u_in; depth[thread[u]] > depth[u_in]; u = thread[u]) ;
5.851 right = thread[u];
5.852 if (thread[v_in] == u_out) {
5.853 - for (last = u; depth[last] > depth[u_out]; last = thread[last]) ;
5.854 - if (last == u_out) last = thread[last];
5.855 + for (last = u; depth[last] > depth[u_out]; last = thread[last]) ;
5.856 + if (last == u_out) last = thread[last];
5.857 }
5.858 else last = thread[v_in];
5.859
5.860 @@ -805,65 +790,65 @@
5.861 thread[v_in] = stem = u_in;
5.862 par_stem = v_in;
5.863 while (stem != u_out) {
5.864 - thread[u] = new_stem = parent[stem];
5.865 + thread[u] = new_stem = parent[stem];
5.866
5.867 - // Finding the node just before the stem node (u) according to
5.868 - // the original thread index
5.869 - for (u = new_stem; thread[u] != stem; u = thread[u]) ;
5.870 - thread[u] = right;
5.871 + // Finding the node just before the stem node (u) according to
5.872 + // the original thread index
5.873 + for (u = new_stem; thread[u] != stem; u = thread[u]) ;
5.874 + thread[u] = right;
5.875
5.876 - // Changing the parent node of stem and shifting stem and
5.877 - // par_stem nodes
5.878 - parent[stem] = par_stem;
5.879 - par_stem = stem;
5.880 - stem = new_stem;
5.881 + // Changing the parent node of stem and shifting stem and
5.882 + // par_stem nodes
5.883 + parent[stem] = par_stem;
5.884 + par_stem = stem;
5.885 + stem = new_stem;
5.886
5.887 - // Finding the last successor of stem (u) and the node after it
5.888 - // (right) according to the thread index
5.889 - for (u = stem; depth[thread[u]] > depth[stem]; u = thread[u]) ;
5.890 - right = thread[u];
5.891 + // Finding the last successor of stem (u) and the node after it
5.892 + // (right) according to the thread index
5.893 + for (u = stem; depth[thread[u]] > depth[stem]; u = thread[u]) ;
5.894 + right = thread[u];
5.895 }
5.896 parent[u_out] = par_stem;
5.897 thread[u] = last;
5.898
5.899 if (join == v_out && par_first) {
5.900 - if (first != v_in) thread[first] = right;
5.901 + if (first != v_in) thread[first] = right;
5.902 } else {
5.903 - for (u = v_out; thread[u] != u_out; u = thread[u]) ;
5.904 - thread[u] = right;
5.905 + for (u = v_out; thread[u] != u_out; u = thread[u]) ;
5.906 + thread[u] = right;
5.907 }
5.908 }
5.909
5.910 - /// \brief Updates pred_edge and forward node maps.
5.911 + /// \brief Updates \c pred_edge and \c forward node maps.
5.912 void updatePredEdge() {
5.913 Node u = u_out, v;
5.914 while (u != u_in) {
5.915 - v = parent[u];
5.916 - pred_edge[u] = pred_edge[v];
5.917 - forward[u] = !forward[v];
5.918 - u = v;
5.919 + v = parent[u];
5.920 + pred_edge[u] = pred_edge[v];
5.921 + forward[u] = !forward[v];
5.922 + u = v;
5.923 }
5.924 pred_edge[u_in] = in_edge;
5.925 forward[u_in] = (u_in == graph.source(in_edge));
5.926 }
5.927
5.928 - /// \brief Updates depth and potential node maps.
5.929 + /// \brief Updates \c depth and \c potential node maps.
5.930 void updateDepthPotential() {
5.931 depth[u_in] = depth[v_in] + 1;
5.932 potential[u_in] = forward[u_in] ?
5.933 - potential[v_in] + cost[pred_edge[u_in]] :
5.934 - potential[v_in] - cost[pred_edge[u_in]];
5.935 + potential[v_in] + cost[pred_edge[u_in]] :
5.936 + potential[v_in] - cost[pred_edge[u_in]];
5.937
5.938 Node u = thread[u_in], v;
5.939 while (true) {
5.940 - v = parent[u];
5.941 - if (v == INVALID) break;
5.942 - depth[u] = depth[v] + 1;
5.943 - potential[u] = forward[u] ?
5.944 - potential[v] + cost[pred_edge[u]] :
5.945 - potential[v] - cost[pred_edge[u]];
5.946 - if (depth[u] <= depth[v_in]) break;
5.947 - u = thread[u];
5.948 + v = parent[u];
5.949 + if (v == INVALID) break;
5.950 + depth[u] = depth[v] + 1;
5.951 + potential[u] = forward[u] ?
5.952 + potential[v] + cost[pred_edge[u]] :
5.953 + potential[v] - cost[pred_edge[u]];
5.954 + if (depth[u] <= depth[v_in]) break;
5.955 + u = thread[u];
5.956 }
5.957 }
5.958
5.959 @@ -880,42 +865,42 @@
5.960 while (findEnteringEdge())
5.961 #endif
5.962 {
5.963 - join = findJoinNode();
5.964 - bool change = findLeavingEdge();
5.965 - changeFlows(change);
5.966 - if (change) {
5.967 - updateThreadParent();
5.968 - updatePredEdge();
5.969 - updateDepthPotential();
5.970 - }
5.971 + join = findJoinNode();
5.972 + bool change = findLeavingEdge();
5.973 + changeFlows(change);
5.974 + if (change) {
5.975 + updateThreadParent();
5.976 + updatePredEdge();
5.977 + updateDepthPotential();
5.978 + }
5.979 #ifdef _DEBUG_ITER_
5.980 - ++iter_num;
5.981 + ++iter_num;
5.982 #endif
5.983 }
5.984
5.985 #ifdef _DEBUG_ITER_
5.986 std::cout << "Network Simplex algorithm finished. " << iter_num
5.987 - << " pivot iterations performed." << std::endl;
5.988 + << " pivot iterations performed." << std::endl;
5.989 #endif
5.990
5.991 // Checking if the flow amount equals zero on all the
5.992 // artificial edges
5.993 for (InEdgeIt e(graph, root); e != INVALID; ++e)
5.994 - if (flow[e] > 0) return false;
5.995 + if (flow[e] > 0) return false;
5.996 for (OutEdgeIt e(graph, root); e != INVALID; ++e)
5.997 - if (flow[e] > 0) return false;
5.998 + if (flow[e] > 0) return false;
5.999
5.1000 // Copying flow values to flow_result
5.1001 if (lower) {
5.1002 - for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
5.1003 - flow_result[e] = (*lower)[e] + flow[edge_ref[e]];
5.1004 + for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
5.1005 + flow_result[e] = (*lower)[e] + flow[edge_ref[e]];
5.1006 } else {
5.1007 - for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
5.1008 - flow_result[e] = flow[edge_ref[e]];
5.1009 + for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e)
5.1010 + flow_result[e] = flow[edge_ref[e]];
5.1011 }
5.1012 // Copying potential values to potential_result
5.1013 for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n)
5.1014 - potential_result[n] = potential[node_ref[n]];
5.1015 + potential_result[n] = potential[node_ref[n]];
5.1016
5.1017 return true;
5.1018 }