deba@2440
|
1 |
/* -*- C++ -*-
|
deba@2440
|
2 |
*
|
deba@2440
|
3 |
* This file is a part of LEMON, a generic C++ optimization library
|
deba@2440
|
4 |
*
|
alpar@2553
|
5 |
* Copyright (C) 2003-2008
|
deba@2440
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@2440
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@2440
|
8 |
*
|
deba@2440
|
9 |
* Permission to use, modify and distribute this software is granted
|
deba@2440
|
10 |
* provided that this copyright notice appears in all copies. For
|
deba@2440
|
11 |
* precise terms see the accompanying LICENSE file.
|
deba@2440
|
12 |
*
|
deba@2440
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@2440
|
14 |
* express or implied, and with no claim as to its suitability for any
|
deba@2440
|
15 |
* purpose.
|
deba@2440
|
16 |
*
|
deba@2440
|
17 |
*/
|
deba@2440
|
18 |
|
deba@2440
|
19 |
#ifndef LEMON_CYCLE_CANCELING_H
|
deba@2440
|
20 |
#define LEMON_CYCLE_CANCELING_H
|
deba@2440
|
21 |
|
deba@2440
|
22 |
/// \ingroup min_cost_flow
|
deba@2440
|
23 |
///
|
deba@2440
|
24 |
/// \file
|
kpeter@2573
|
25 |
/// \brief Cycle-canceling algorithm for finding a minimum cost flow.
|
deba@2440
|
26 |
|
deba@2440
|
27 |
#include <vector>
|
kpeter@2509
|
28 |
#include <lemon/graph_adaptor.h>
|
kpeter@2573
|
29 |
#include <lemon/path.h>
|
kpeter@2573
|
30 |
|
deba@2440
|
31 |
#include <lemon/circulation.h>
|
kpeter@2573
|
32 |
#include <lemon/bellman_ford.h>
|
kpeter@2573
|
33 |
#include <lemon/min_mean_cycle.h>
|
kpeter@2556
|
34 |
|
deba@2440
|
35 |
namespace lemon {
|
deba@2440
|
36 |
|
deba@2440
|
37 |
/// \addtogroup min_cost_flow
|
deba@2440
|
38 |
/// @{
|
deba@2440
|
39 |
|
kpeter@2556
|
40 |
/// \brief Implementation of a cycle-canceling algorithm for
|
kpeter@2556
|
41 |
/// finding a minimum cost flow.
|
deba@2440
|
42 |
///
|
kpeter@2556
|
43 |
/// \ref CycleCanceling implements a cycle-canceling algorithm for
|
kpeter@2556
|
44 |
/// finding a minimum cost flow.
|
deba@2440
|
45 |
///
|
kpeter@2573
|
46 |
/// \tparam Graph The directed graph type the algorithm runs on.
|
kpeter@2573
|
47 |
/// \tparam LowerMap The type of the lower bound map.
|
kpeter@2573
|
48 |
/// \tparam CapacityMap The type of the capacity (upper bound) map.
|
kpeter@2573
|
49 |
/// \tparam CostMap The type of the cost (length) map.
|
kpeter@2573
|
50 |
/// \tparam SupplyMap The type of the supply map.
|
deba@2440
|
51 |
///
|
deba@2440
|
52 |
/// \warning
|
kpeter@2573
|
53 |
/// - Edge capacities and costs should be \e non-negative \e integers.
|
kpeter@2573
|
54 |
/// - Supply values should be \e signed \e integers.
|
kpeter@2573
|
55 |
/// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
|
kpeter@2573
|
56 |
/// - \c CapacityMap::Value and \c SupplyMap::Value must be
|
kpeter@2573
|
57 |
/// convertible to each other.
|
kpeter@2573
|
58 |
/// - All value types must be convertible to \c CostMap::Value, which
|
kpeter@2573
|
59 |
/// must be signed type.
|
kpeter@2573
|
60 |
///
|
kpeter@2573
|
61 |
/// \note By default the \ref BellmanFord "Bellman-Ford" algorithm is
|
kpeter@2573
|
62 |
/// used for negative cycle detection with limited iteration number.
|
kpeter@2573
|
63 |
/// However \ref CycleCanceling also provides the "Minimum Mean
|
kpeter@2573
|
64 |
/// Cycle-Canceling" algorithm, which is \e strongly \e polynomial,
|
kpeter@2573
|
65 |
/// but rather slower in practice.
|
kpeter@2573
|
66 |
/// To use this version of the algorithm, call \ref run() with \c true
|
kpeter@2573
|
67 |
/// parameter.
|
deba@2440
|
68 |
///
|
deba@2440
|
69 |
/// \author Peter Kovacs
|
deba@2440
|
70 |
|
kpeter@2533
|
71 |
template < typename Graph,
|
kpeter@2533
|
72 |
typename LowerMap = typename Graph::template EdgeMap<int>,
|
kpeter@2573
|
73 |
typename CapacityMap = typename Graph::template EdgeMap<int>,
|
kpeter@2533
|
74 |
typename CostMap = typename Graph::template EdgeMap<int>,
|
kpeter@2573
|
75 |
typename SupplyMap = typename Graph::template NodeMap<int> >
|
deba@2440
|
76 |
class CycleCanceling
|
deba@2440
|
77 |
{
|
kpeter@2556
|
78 |
GRAPH_TYPEDEFS(typename Graph);
|
deba@2440
|
79 |
|
deba@2440
|
80 |
typedef typename CapacityMap::Value Capacity;
|
deba@2440
|
81 |
typedef typename CostMap::Value Cost;
|
deba@2440
|
82 |
typedef typename SupplyMap::Value Supply;
|
kpeter@2556
|
83 |
typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
|
kpeter@2556
|
84 |
typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
|
deba@2440
|
85 |
|
deba@2440
|
86 |
typedef ResGraphAdaptor< const Graph, Capacity,
|
kpeter@2556
|
87 |
CapacityEdgeMap, CapacityEdgeMap > ResGraph;
|
deba@2440
|
88 |
typedef typename ResGraph::Node ResNode;
|
deba@2440
|
89 |
typedef typename ResGraph::NodeIt ResNodeIt;
|
deba@2440
|
90 |
typedef typename ResGraph::Edge ResEdge;
|
deba@2440
|
91 |
typedef typename ResGraph::EdgeIt ResEdgeIt;
|
deba@2440
|
92 |
|
deba@2440
|
93 |
public:
|
deba@2440
|
94 |
|
kpeter@2556
|
95 |
/// The type of the flow map.
|
kpeter@2556
|
96 |
typedef typename Graph::template EdgeMap<Capacity> FlowMap;
|
deba@2440
|
97 |
|
kpeter@2573
|
98 |
private:
|
deba@2440
|
99 |
|
kpeter@2573
|
100 |
/// \brief Map adaptor class for handling residual edge costs.
|
kpeter@2573
|
101 |
///
|
kpeter@2573
|
102 |
/// \ref ResidualCostMap is a map adaptor class for handling
|
kpeter@2573
|
103 |
/// residual edge costs.
|
kpeter@2573
|
104 |
class ResidualCostMap : public MapBase<ResEdge, Cost>
|
deba@2440
|
105 |
{
|
deba@2440
|
106 |
private:
|
deba@2440
|
107 |
|
kpeter@2573
|
108 |
const CostMap &_cost_map;
|
deba@2440
|
109 |
|
deba@2440
|
110 |
public:
|
deba@2440
|
111 |
|
kpeter@2573
|
112 |
///\e
|
kpeter@2573
|
113 |
ResidualCostMap(const CostMap &cost_map) : _cost_map(cost_map) {}
|
deba@2440
|
114 |
|
kpeter@2573
|
115 |
///\e
|
kpeter@2509
|
116 |
Cost operator[](const ResEdge &e) const {
|
kpeter@2573
|
117 |
return ResGraph::forward(e) ? _cost_map[e] : -_cost_map[e];
|
deba@2440
|
118 |
}
|
deba@2440
|
119 |
|
kpeter@2573
|
120 |
}; //class ResidualCostMap
|
deba@2440
|
121 |
|
kpeter@2573
|
122 |
private:
|
deba@2440
|
123 |
|
kpeter@2573
|
124 |
// The maximum number of iterations for the first execution of the
|
kpeter@2573
|
125 |
// Bellman-Ford algorithm. It should be at least 2.
|
kpeter@2573
|
126 |
static const int BF_FIRST_LIMIT = 2;
|
kpeter@2573
|
127 |
// The iteration limit for the Bellman-Ford algorithm is multiplied
|
kpeter@2573
|
128 |
// by BF_ALPHA in every round.
|
kpeter@2573
|
129 |
static const double BF_ALPHA = 1.5;
|
deba@2440
|
130 |
|
kpeter@2573
|
131 |
private:
|
deba@2440
|
132 |
|
kpeter@2573
|
133 |
// The directed graph the algorithm runs on
|
kpeter@2573
|
134 |
const Graph &_graph;
|
kpeter@2573
|
135 |
// The original lower bound map
|
kpeter@2573
|
136 |
const LowerMap *_lower;
|
kpeter@2573
|
137 |
// The modified capacity map
|
kpeter@2573
|
138 |
CapacityEdgeMap _capacity;
|
kpeter@2573
|
139 |
// The original cost map
|
kpeter@2573
|
140 |
const CostMap &_cost;
|
kpeter@2573
|
141 |
// The modified supply map
|
kpeter@2573
|
142 |
SupplyNodeMap _supply;
|
kpeter@2573
|
143 |
bool _valid_supply;
|
kpeter@2573
|
144 |
|
kpeter@2573
|
145 |
// Edge map of the current flow
|
kpeter@2573
|
146 |
FlowMap _flow;
|
kpeter@2573
|
147 |
|
kpeter@2573
|
148 |
// The residual graph
|
kpeter@2573
|
149 |
ResGraph _res_graph;
|
kpeter@2573
|
150 |
// The residual cost map
|
kpeter@2573
|
151 |
ResidualCostMap _res_cost;
|
kpeter@2573
|
152 |
|
kpeter@2573
|
153 |
public:
|
deba@2440
|
154 |
|
deba@2440
|
155 |
/// \brief General constructor of the class (with lower bounds).
|
deba@2440
|
156 |
///
|
deba@2440
|
157 |
/// General constructor of the class (with lower bounds).
|
deba@2440
|
158 |
///
|
kpeter@2573
|
159 |
/// \param graph The directed graph the algorithm runs on.
|
kpeter@2573
|
160 |
/// \param lower The lower bounds of the edges.
|
kpeter@2573
|
161 |
/// \param capacity The capacities (upper bounds) of the edges.
|
kpeter@2573
|
162 |
/// \param cost The cost (length) values of the edges.
|
kpeter@2573
|
163 |
/// \param supply The supply values of the nodes (signed).
|
kpeter@2573
|
164 |
CycleCanceling( const Graph &graph,
|
kpeter@2573
|
165 |
const LowerMap &lower,
|
kpeter@2573
|
166 |
const CapacityMap &capacity,
|
kpeter@2573
|
167 |
const CostMap &cost,
|
kpeter@2573
|
168 |
const SupplyMap &supply ) :
|
kpeter@2573
|
169 |
_graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
|
kpeter@2573
|
170 |
_supply(graph), _flow(graph, 0),
|
kpeter@2573
|
171 |
_res_graph(graph, _capacity, _flow), _res_cost(_cost)
|
deba@2440
|
172 |
{
|
kpeter@2556
|
173 |
// Removing non-zero lower bounds
|
kpeter@2573
|
174 |
_capacity = subMap(capacity, lower);
|
deba@2440
|
175 |
Supply sum = 0;
|
kpeter@2573
|
176 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
kpeter@2573
|
177 |
Supply s = supply[n];
|
kpeter@2573
|
178 |
for (InEdgeIt e(_graph, n); e != INVALID; ++e)
|
kpeter@2573
|
179 |
s += lower[e];
|
kpeter@2573
|
180 |
for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
|
kpeter@2573
|
181 |
s -= lower[e];
|
kpeter@2573
|
182 |
sum += (_supply[n] = s);
|
deba@2440
|
183 |
}
|
kpeter@2573
|
184 |
_valid_supply = sum == 0;
|
deba@2440
|
185 |
}
|
deba@2440
|
186 |
|
deba@2440
|
187 |
/// \brief General constructor of the class (without lower bounds).
|
deba@2440
|
188 |
///
|
deba@2440
|
189 |
/// General constructor of the class (without lower bounds).
|
deba@2440
|
190 |
///
|
kpeter@2573
|
191 |
/// \param graph The directed graph the algorithm runs on.
|
kpeter@2573
|
192 |
/// \param capacity The capacities (upper bounds) of the edges.
|
kpeter@2573
|
193 |
/// \param cost The cost (length) values of the edges.
|
kpeter@2573
|
194 |
/// \param supply The supply values of the nodes (signed).
|
kpeter@2573
|
195 |
CycleCanceling( const Graph &graph,
|
kpeter@2573
|
196 |
const CapacityMap &capacity,
|
kpeter@2573
|
197 |
const CostMap &cost,
|
kpeter@2573
|
198 |
const SupplyMap &supply ) :
|
kpeter@2573
|
199 |
_graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
|
kpeter@2573
|
200 |
_supply(supply), _flow(graph, 0),
|
kpeter@2573
|
201 |
_res_graph(graph, _capacity, _flow), _res_cost(_cost)
|
deba@2440
|
202 |
{
|
deba@2440
|
203 |
// Checking the sum of supply values
|
deba@2440
|
204 |
Supply sum = 0;
|
kpeter@2573
|
205 |
for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
|
kpeter@2573
|
206 |
_valid_supply = sum == 0;
|
deba@2440
|
207 |
}
|
deba@2440
|
208 |
|
deba@2440
|
209 |
/// \brief Simple constructor of the class (with lower bounds).
|
deba@2440
|
210 |
///
|
deba@2440
|
211 |
/// Simple constructor of the class (with lower bounds).
|
deba@2440
|
212 |
///
|
kpeter@2573
|
213 |
/// \param graph The directed graph the algorithm runs on.
|
kpeter@2573
|
214 |
/// \param lower The lower bounds of the edges.
|
kpeter@2573
|
215 |
/// \param capacity The capacities (upper bounds) of the edges.
|
kpeter@2573
|
216 |
/// \param cost The cost (length) values of the edges.
|
kpeter@2573
|
217 |
/// \param s The source node.
|
kpeter@2573
|
218 |
/// \param t The target node.
|
kpeter@2573
|
219 |
/// \param flow_value The required amount of flow from node \c s
|
kpeter@2573
|
220 |
/// to node \c t (i.e. the supply of \c s and the demand of \c t).
|
kpeter@2573
|
221 |
CycleCanceling( const Graph &graph,
|
kpeter@2573
|
222 |
const LowerMap &lower,
|
kpeter@2573
|
223 |
const CapacityMap &capacity,
|
kpeter@2573
|
224 |
const CostMap &cost,
|
kpeter@2573
|
225 |
Node s, Node t,
|
kpeter@2573
|
226 |
Supply flow_value ) :
|
kpeter@2573
|
227 |
_graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
|
kpeter@2573
|
228 |
_supply(graph), _flow(graph, 0),
|
kpeter@2573
|
229 |
_res_graph(graph, _capacity, _flow), _res_cost(_cost)
|
deba@2440
|
230 |
{
|
kpeter@2556
|
231 |
// Removing non-zero lower bounds
|
kpeter@2573
|
232 |
_capacity = subMap(capacity, lower);
|
kpeter@2573
|
233 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
kpeter@2573
|
234 |
Supply sum = 0;
|
kpeter@2573
|
235 |
if (n == s) sum = flow_value;
|
kpeter@2573
|
236 |
if (n == t) sum = -flow_value;
|
kpeter@2573
|
237 |
for (InEdgeIt e(_graph, n); e != INVALID; ++e)
|
kpeter@2573
|
238 |
sum += lower[e];
|
kpeter@2573
|
239 |
for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
|
kpeter@2573
|
240 |
sum -= lower[e];
|
kpeter@2573
|
241 |
_supply[n] = sum;
|
deba@2440
|
242 |
}
|
kpeter@2573
|
243 |
_valid_supply = true;
|
deba@2440
|
244 |
}
|
deba@2440
|
245 |
|
deba@2440
|
246 |
/// \brief Simple constructor of the class (without lower bounds).
|
deba@2440
|
247 |
///
|
deba@2440
|
248 |
/// Simple constructor of the class (without lower bounds).
|
deba@2440
|
249 |
///
|
kpeter@2573
|
250 |
/// \param graph The directed graph the algorithm runs on.
|
kpeter@2573
|
251 |
/// \param capacity The capacities (upper bounds) of the edges.
|
kpeter@2573
|
252 |
/// \param cost The cost (length) values of the edges.
|
kpeter@2573
|
253 |
/// \param s The source node.
|
kpeter@2573
|
254 |
/// \param t The target node.
|
kpeter@2573
|
255 |
/// \param flow_value The required amount of flow from node \c s
|
kpeter@2573
|
256 |
/// to node \c t (i.e. the supply of \c s and the demand of \c t).
|
kpeter@2573
|
257 |
CycleCanceling( const Graph &graph,
|
kpeter@2573
|
258 |
const CapacityMap &capacity,
|
kpeter@2573
|
259 |
const CostMap &cost,
|
kpeter@2573
|
260 |
Node s, Node t,
|
kpeter@2573
|
261 |
Supply flow_value ) :
|
kpeter@2573
|
262 |
_graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
|
kpeter@2573
|
263 |
_supply(graph, 0), _flow(graph, 0),
|
kpeter@2573
|
264 |
_res_graph(graph, _capacity, _flow), _res_cost(_cost)
|
deba@2440
|
265 |
{
|
kpeter@2573
|
266 |
_supply[s] = flow_value;
|
kpeter@2573
|
267 |
_supply[t] = -flow_value;
|
kpeter@2573
|
268 |
_valid_supply = true;
|
deba@2440
|
269 |
}
|
deba@2440
|
270 |
|
kpeter@2556
|
271 |
/// \brief Runs the algorithm.
|
kpeter@2556
|
272 |
///
|
kpeter@2556
|
273 |
/// Runs the algorithm.
|
kpeter@2556
|
274 |
///
|
kpeter@2573
|
275 |
/// \param min_mean_cc Set this parameter to \c true to run the
|
kpeter@2573
|
276 |
/// "Minimum Mean Cycle-Canceling" algorithm, which is strongly
|
kpeter@2573
|
277 |
/// polynomial, but rather slower in practice.
|
kpeter@2573
|
278 |
///
|
kpeter@2556
|
279 |
/// \return \c true if a feasible flow can be found.
|
kpeter@2573
|
280 |
bool run(bool min_mean_cc = false) {
|
kpeter@2573
|
281 |
return init() && start(min_mean_cc);
|
kpeter@2556
|
282 |
}
|
kpeter@2556
|
283 |
|
kpeter@2573
|
284 |
/// \brief Returns a const reference to the edge map storing the
|
kpeter@2573
|
285 |
/// found flow.
|
deba@2440
|
286 |
///
|
kpeter@2573
|
287 |
/// Returns a const reference to the edge map storing the found flow.
|
deba@2440
|
288 |
///
|
deba@2440
|
289 |
/// \pre \ref run() must be called before using this function.
|
deba@2440
|
290 |
const FlowMap& flowMap() const {
|
kpeter@2573
|
291 |
return _flow;
|
deba@2440
|
292 |
}
|
deba@2440
|
293 |
|
deba@2440
|
294 |
/// \brief Returns the total cost of the found flow.
|
deba@2440
|
295 |
///
|
deba@2440
|
296 |
/// Returns the total cost of the found flow. The complexity of the
|
deba@2440
|
297 |
/// function is \f$ O(e) \f$.
|
deba@2440
|
298 |
///
|
deba@2440
|
299 |
/// \pre \ref run() must be called before using this function.
|
deba@2440
|
300 |
Cost totalCost() const {
|
deba@2440
|
301 |
Cost c = 0;
|
kpeter@2573
|
302 |
for (EdgeIt e(_graph); e != INVALID; ++e)
|
kpeter@2573
|
303 |
c += _flow[e] * _cost[e];
|
deba@2440
|
304 |
return c;
|
deba@2440
|
305 |
}
|
deba@2440
|
306 |
|
kpeter@2573
|
307 |
private:
|
deba@2440
|
308 |
|
kpeter@2556
|
309 |
/// Initializes the algorithm.
|
deba@2440
|
310 |
bool init() {
|
kpeter@2573
|
311 |
if (!_valid_supply) return false;
|
deba@2440
|
312 |
|
kpeter@2573
|
313 |
// Finding a feasible flow using Circulation
|
kpeter@2556
|
314 |
Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
|
kpeter@2556
|
315 |
SupplyMap >
|
kpeter@2573
|
316 |
circulation( _graph, constMap<Edge>((Capacity)0), _capacity,
|
kpeter@2573
|
317 |
_supply );
|
kpeter@2573
|
318 |
return circulation.flowMap(_flow).run();
|
deba@2440
|
319 |
}
|
deba@2440
|
320 |
|
kpeter@2573
|
321 |
bool start(bool min_mean_cc) {
|
kpeter@2573
|
322 |
if (min_mean_cc)
|
kpeter@2573
|
323 |
return startMinMean();
|
kpeter@2573
|
324 |
else
|
kpeter@2573
|
325 |
return start();
|
kpeter@2573
|
326 |
}
|
kpeter@2573
|
327 |
|
kpeter@2573
|
328 |
/// \brief Executes the algorithm using \ref BellmanFord.
|
kpeter@2573
|
329 |
///
|
kpeter@2573
|
330 |
/// Executes the algorithm using the \ref BellmanFord
|
kpeter@2573
|
331 |
/// "Bellman-Ford" algorithm for negative cycle detection with
|
kpeter@2573
|
332 |
/// successively larger limit for the number of iterations.
|
deba@2440
|
333 |
bool start() {
|
kpeter@2573
|
334 |
typename BellmanFord<ResGraph, ResidualCostMap>::PredMap pred(_res_graph);
|
kpeter@2573
|
335 |
typename ResGraph::template NodeMap<int> visited(_res_graph);
|
deba@2440
|
336 |
std::vector<ResEdge> cycle;
|
kpeter@2573
|
337 |
int node_num = countNodes(_graph);
|
deba@2440
|
338 |
|
kpeter@2573
|
339 |
int length_bound = BF_FIRST_LIMIT;
|
deba@2440
|
340 |
bool optimal = false;
|
deba@2440
|
341 |
while (!optimal) {
|
kpeter@2573
|
342 |
BellmanFord<ResGraph, ResidualCostMap> bf(_res_graph, _res_cost);
|
kpeter@2556
|
343 |
bf.predMap(pred);
|
kpeter@2556
|
344 |
bf.init(0);
|
kpeter@2556
|
345 |
int iter_num = 0;
|
kpeter@2556
|
346 |
bool cycle_found = false;
|
kpeter@2556
|
347 |
while (!cycle_found) {
|
kpeter@2556
|
348 |
int curr_iter_num = iter_num + length_bound <= node_num ?
|
kpeter@2556
|
349 |
length_bound : node_num - iter_num;
|
kpeter@2556
|
350 |
iter_num += curr_iter_num;
|
kpeter@2556
|
351 |
int real_iter_num = curr_iter_num;
|
kpeter@2556
|
352 |
for (int i = 0; i < curr_iter_num; ++i) {
|
kpeter@2556
|
353 |
if (bf.processNextWeakRound()) {
|
kpeter@2556
|
354 |
real_iter_num = i;
|
kpeter@2556
|
355 |
break;
|
kpeter@2556
|
356 |
}
|
kpeter@2556
|
357 |
}
|
kpeter@2556
|
358 |
if (real_iter_num < curr_iter_num) {
|
kpeter@2556
|
359 |
optimal = true;
|
kpeter@2556
|
360 |
break;
|
kpeter@2556
|
361 |
} else {
|
kpeter@2556
|
362 |
// Searching for node disjoint negative cycles
|
kpeter@2573
|
363 |
for (ResNodeIt n(_res_graph); n != INVALID; ++n)
|
kpeter@2556
|
364 |
visited[n] = 0;
|
kpeter@2556
|
365 |
int id = 0;
|
kpeter@2573
|
366 |
for (ResNodeIt n(_res_graph); n != INVALID; ++n) {
|
kpeter@2556
|
367 |
if (visited[n] > 0) continue;
|
kpeter@2556
|
368 |
visited[n] = ++id;
|
kpeter@2556
|
369 |
ResNode u = pred[n] == INVALID ?
|
kpeter@2573
|
370 |
INVALID : _res_graph.source(pred[n]);
|
kpeter@2556
|
371 |
while (u != INVALID && visited[u] == 0) {
|
kpeter@2556
|
372 |
visited[u] = id;
|
kpeter@2556
|
373 |
u = pred[u] == INVALID ?
|
kpeter@2573
|
374 |
INVALID : _res_graph.source(pred[u]);
|
kpeter@2556
|
375 |
}
|
kpeter@2556
|
376 |
if (u != INVALID && visited[u] == id) {
|
kpeter@2556
|
377 |
// Finding the negative cycle
|
kpeter@2556
|
378 |
cycle_found = true;
|
kpeter@2556
|
379 |
cycle.clear();
|
kpeter@2556
|
380 |
ResEdge e = pred[u];
|
kpeter@2556
|
381 |
cycle.push_back(e);
|
kpeter@2573
|
382 |
Capacity d = _res_graph.rescap(e);
|
kpeter@2573
|
383 |
while (_res_graph.source(e) != u) {
|
kpeter@2573
|
384 |
cycle.push_back(e = pred[_res_graph.source(e)]);
|
kpeter@2573
|
385 |
if (_res_graph.rescap(e) < d)
|
kpeter@2573
|
386 |
d = _res_graph.rescap(e);
|
kpeter@2556
|
387 |
}
|
kpeter@2573
|
388 |
|
kpeter@2556
|
389 |
// Augmenting along the cycle
|
kpeter@2573
|
390 |
for (int i = 0; i < int(cycle.size()); ++i)
|
kpeter@2573
|
391 |
_res_graph.augment(cycle[i], d);
|
kpeter@2556
|
392 |
}
|
kpeter@2556
|
393 |
}
|
kpeter@2556
|
394 |
}
|
deba@2440
|
395 |
|
kpeter@2556
|
396 |
if (!cycle_found)
|
kpeter@2573
|
397 |
length_bound = int(length_bound * BF_ALPHA);
|
kpeter@2556
|
398 |
}
|
deba@2440
|
399 |
}
|
deba@2440
|
400 |
|
kpeter@2556
|
401 |
// Handling non-zero lower bounds
|
kpeter@2573
|
402 |
if (_lower) {
|
kpeter@2573
|
403 |
for (EdgeIt e(_graph); e != INVALID; ++e)
|
kpeter@2573
|
404 |
_flow[e] += (*_lower)[e];
|
deba@2440
|
405 |
}
|
deba@2440
|
406 |
return true;
|
deba@2440
|
407 |
}
|
deba@2440
|
408 |
|
kpeter@2573
|
409 |
/// \brief Executes the algorithm using \ref MinMeanCycle.
|
kpeter@2573
|
410 |
///
|
kpeter@2573
|
411 |
/// Executes the algorithm using \ref MinMeanCycle for negative
|
kpeter@2573
|
412 |
/// cycle detection.
|
kpeter@2573
|
413 |
bool startMinMean() {
|
deba@2440
|
414 |
typedef Path<ResGraph> ResPath;
|
kpeter@2573
|
415 |
MinMeanCycle<ResGraph, ResidualCostMap> mmc(_res_graph, _res_cost);
|
deba@2440
|
416 |
ResPath cycle;
|
deba@2440
|
417 |
|
deba@2440
|
418 |
mmc.cyclePath(cycle).init();
|
deba@2440
|
419 |
if (mmc.findMinMean()) {
|
kpeter@2556
|
420 |
while (mmc.cycleLength() < 0) {
|
kpeter@2556
|
421 |
// Finding the cycle
|
kpeter@2556
|
422 |
mmc.findCycle();
|
deba@2440
|
423 |
|
kpeter@2556
|
424 |
// Finding the largest flow amount that can be augmented
|
kpeter@2556
|
425 |
// along the cycle
|
kpeter@2556
|
426 |
Capacity delta = 0;
|
kpeter@2556
|
427 |
for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
|
kpeter@2573
|
428 |
if (delta == 0 || _res_graph.rescap(e) < delta)
|
kpeter@2573
|
429 |
delta = _res_graph.rescap(e);
|
kpeter@2556
|
430 |
}
|
deba@2440
|
431 |
|
kpeter@2556
|
432 |
// Augmenting along the cycle
|
kpeter@2556
|
433 |
for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
|
kpeter@2573
|
434 |
_res_graph.augment(e, delta);
|
deba@2440
|
435 |
|
kpeter@2556
|
436 |
// Finding the minimum cycle mean for the modified residual
|
kpeter@2556
|
437 |
// graph
|
kpeter@2556
|
438 |
mmc.reset();
|
kpeter@2556
|
439 |
if (!mmc.findMinMean()) break;
|
kpeter@2556
|
440 |
}
|
deba@2440
|
441 |
}
|
deba@2440
|
442 |
|
kpeter@2556
|
443 |
// Handling non-zero lower bounds
|
kpeter@2573
|
444 |
if (_lower) {
|
kpeter@2573
|
445 |
for (EdgeIt e(_graph); e != INVALID; ++e)
|
kpeter@2573
|
446 |
_flow[e] += (*_lower)[e];
|
deba@2440
|
447 |
}
|
deba@2440
|
448 |
return true;
|
deba@2440
|
449 |
}
|
deba@2440
|
450 |
|
deba@2440
|
451 |
}; //class CycleCanceling
|
deba@2440
|
452 |
|
deba@2440
|
453 |
///@}
|
deba@2440
|
454 |
|
deba@2440
|
455 |
} //namespace lemon
|
deba@2440
|
456 |
|
deba@2440
|
457 |
#endif //LEMON_CYCLE_CANCELING_H
|