- Gamma distributon random variable.
- Test file for random.h
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_CYCLE_CANCELING_H
20 #define LEMON_CYCLE_CANCELING_H
22 /// \ingroup min_cost_flow
25 /// \brief A cycle-canceling algorithm for finding a minimum cost flow.
28 #include <lemon/circulation.h>
29 #include <lemon/graph_adaptor.h>
31 /// \brief The used cycle-canceling method.
32 #define LIMITED_CYCLE_CANCELING
33 //#define MIN_MEAN_CYCLE_CANCELING
35 #ifdef LIMITED_CYCLE_CANCELING
36 #include <lemon/bellman_ford.h>
37 /// \brief The maximum number of iterations for the first execution
38 /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.
39 /// It should be at least 2.
40 #define STARTING_LIMIT 2
41 /// \brief The iteration limit for the
42 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
43 /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
44 /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
46 /// \brief The iteration limit for the
47 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
48 /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
49 /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
52 //#define _ONLY_ONE_CYCLE_
53 //#define _NO_BACK_STEP_
54 //#define _DEBUG_ITER_
57 #ifdef MIN_MEAN_CYCLE_CANCELING
58 #include <lemon/min_mean_cycle.h>
59 #include <lemon/path.h>
64 /// \addtogroup min_cost_flow
67 /// \brief Implementation of a cycle-canceling algorithm for finding
68 /// a minimum cost flow.
70 /// \ref lemon::CycleCanceling "CycleCanceling" implements a
71 /// cycle-canceling algorithm for finding a minimum cost flow.
73 /// \param Graph The directed graph type the algorithm runs on.
74 /// \param LowerMap The type of the lower bound map.
75 /// \param CapacityMap The type of the capacity (upper bound) map.
76 /// \param CostMap The type of the cost (length) map.
77 /// \param SupplyMap The type of the supply map.
80 /// - Edge capacities and costs should be nonnegative integers.
81 /// However \c CostMap::Value should be signed type.
82 /// - Supply values should be integers.
83 /// - \c LowerMap::Value must be convertible to
84 /// \c CapacityMap::Value and \c CapacityMap::Value must be
85 /// convertible to \c SupplyMap::Value.
87 /// \author Peter Kovacs
89 template < typename Graph,
90 typename LowerMap = typename Graph::template EdgeMap<int>,
91 typename CapacityMap = LowerMap,
92 typename CostMap = typename Graph::template EdgeMap<int>,
93 typename SupplyMap = typename Graph::template NodeMap
94 <typename CapacityMap::Value> >
97 typedef typename Graph::Node Node;
98 typedef typename Graph::NodeIt NodeIt;
99 typedef typename Graph::Edge Edge;
100 typedef typename Graph::EdgeIt EdgeIt;
101 typedef typename Graph::InEdgeIt InEdgeIt;
102 typedef typename Graph::OutEdgeIt OutEdgeIt;
104 typedef typename LowerMap::Value Lower;
105 typedef typename CapacityMap::Value Capacity;
106 typedef typename CostMap::Value Cost;
107 typedef typename SupplyMap::Value Supply;
108 typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
109 typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
111 typedef ResGraphAdaptor< const Graph, Capacity,
112 CapacityRefMap, CapacityRefMap > ResGraph;
113 typedef typename ResGraph::Node ResNode;
114 typedef typename ResGraph::NodeIt ResNodeIt;
115 typedef typename ResGraph::Edge ResEdge;
116 typedef typename ResGraph::EdgeIt ResEdgeIt;
120 /// \brief The type of the flow map.
121 typedef CapacityRefMap FlowMap;
125 /// \brief Map adaptor class for handling residual edge costs.
126 class ResCostMap : public MapBase<ResEdge, Cost>
130 const CostMap &cost_map;
134 typedef typename MapBase<ResEdge, Cost>::Value Value;
135 typedef typename MapBase<ResEdge, Cost>::Key Key;
137 ResCostMap(const CostMap &_cost) : cost_map(_cost) {}
139 Value operator[](const Key &e) const {
140 return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
143 }; //class ResCostMap
147 /// \brief The directed graph the algorithm runs on.
149 /// \brief The original lower bound map.
150 const LowerMap *lower;
151 /// \brief The modified capacity map.
152 CapacityRefMap capacity;
153 /// \brief The cost map.
155 /// \brief The modified supply map.
157 /// \brief The sum of supply values equals zero.
160 /// \brief The current flow.
162 /// \brief The residual graph.
164 /// \brief The residual cost map.
169 /// \brief General constructor of the class (with lower bounds).
171 /// General constructor of the class (with lower bounds).
173 /// \param _graph The directed graph the algorithm runs on.
174 /// \param _lower The lower bounds of the edges.
175 /// \param _capacity The capacities (upper bounds) of the edges.
176 /// \param _cost The cost (length) values of the edges.
177 /// \param _supply The supply values of the nodes (signed).
178 CycleCanceling( const Graph &_graph,
179 const LowerMap &_lower,
180 const CapacityMap &_capacity,
181 const CostMap &_cost,
182 const SupplyMap &_supply ) :
183 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
184 supply(_graph), flow(_graph, 0),
185 res_graph(_graph, capacity, flow), res_cost(cost)
187 // Removing nonzero lower bounds
188 capacity = subMap(_capacity, _lower);
190 for (NodeIt n(graph); n != INVALID; ++n) {
191 Supply s = _supply[n];
192 for (InEdgeIt e(graph, n); e != INVALID; ++e)
194 for (OutEdgeIt e(graph, n); e != INVALID; ++e)
196 sum += (supply[n] = s);
198 valid_supply = sum == 0;
201 /// \brief General constructor of the class (without lower bounds).
203 /// General constructor of the class (without lower bounds).
205 /// \param _graph The directed graph the algorithm runs on.
206 /// \param _capacity The capacities (upper bounds) of the edges.
207 /// \param _cost The cost (length) values of the edges.
208 /// \param _supply The supply values of the nodes (signed).
209 CycleCanceling( const Graph &_graph,
210 const CapacityMap &_capacity,
211 const CostMap &_cost,
212 const SupplyMap &_supply ) :
213 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
214 supply(_supply), flow(_graph, 0),
215 res_graph(_graph, capacity, flow), res_cost(cost)
217 // Checking the sum of supply values
219 for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
220 valid_supply = sum == 0;
224 /// \brief Simple constructor of the class (with lower bounds).
226 /// Simple constructor of the class (with lower bounds).
228 /// \param _graph The directed graph the algorithm runs on.
229 /// \param _lower The lower bounds of the edges.
230 /// \param _capacity The capacities (upper bounds) of the edges.
231 /// \param _cost The cost (length) values of the edges.
232 /// \param _s The source node.
233 /// \param _t The target node.
234 /// \param _flow_value The required amount of flow from node \c _s
235 /// to node \c _t (i.e. the supply of \c _s and the demand of
237 CycleCanceling( const Graph &_graph,
238 const LowerMap &_lower,
239 const CapacityMap &_capacity,
240 const CostMap &_cost,
242 Supply _flow_value ) :
243 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
244 supply(_graph), flow(_graph, 0),
245 res_graph(_graph, capacity, flow), res_cost(cost)
247 // Removing nonzero lower bounds
248 capacity = subMap(_capacity, _lower);
249 for (NodeIt n(graph); n != INVALID; ++n) {
251 if (n == _s) s = _flow_value;
252 if (n == _t) s = -_flow_value;
253 for (InEdgeIt e(graph, n); e != INVALID; ++e)
255 for (OutEdgeIt e(graph, n); e != INVALID; ++e)
262 /// \brief Simple constructor of the class (without lower bounds).
264 /// Simple constructor of the class (without lower bounds).
266 /// \param _graph The directed graph the algorithm runs on.
267 /// \param _capacity The capacities (upper bounds) of the edges.
268 /// \param _cost The cost (length) values of the edges.
269 /// \param _s The source node.
270 /// \param _t The target node.
271 /// \param _flow_value The required amount of flow from node \c _s
272 /// to node \c _t (i.e. the supply of \c _s and the demand of
274 CycleCanceling( const Graph &_graph,
275 const CapacityMap &_capacity,
276 const CostMap &_cost,
278 Supply _flow_value ) :
279 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
280 supply(_graph, 0), flow(_graph, 0),
281 res_graph(_graph, capacity, flow), res_cost(cost)
283 supply[_s] = _flow_value;
284 supply[_t] = -_flow_value;
288 /// \brief Returns a const reference to the flow map.
290 /// Returns a const reference to the flow map.
292 /// \pre \ref run() must be called before using this function.
293 const FlowMap& flowMap() const {
297 /// \brief Returns the total cost of the found flow.
299 /// Returns the total cost of the found flow. The complexity of the
300 /// function is \f$ O(e) \f$.
302 /// \pre \ref run() must be called before using this function.
303 Cost totalCost() const {
305 for (EdgeIt e(graph); e != INVALID; ++e)
306 c += flow[e] * cost[e];
310 /// \brief Runs the algorithm.
312 /// Runs the algorithm.
314 /// \return \c true if a feasible flow can be found.
316 return init() && start();
321 /// \brief Initializes the algorithm.
323 // Checking the sum of supply values
325 for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
326 if (sum != 0) return false;
328 // Finding a feasible flow
329 Circulation< Graph, Capacity, FlowMap, ConstMap<Edge, Capacity>,
330 CapacityRefMap, SupplyMap >
331 circulation( graph, constMap<Edge>((Capacity)0),
332 capacity, supply, flow );
333 return circulation.run() == -1;
336 #ifdef LIMITED_CYCLE_CANCELING
337 /// \brief Executes a cycle-canceling algorithm using
338 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited
341 typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph);
342 typename ResGraph::template NodeMap<int> visited(res_graph);
343 std::vector<ResEdge> cycle;
344 int node_num = countNodes(graph);
349 int length_bound = STARTING_LIMIT;
350 bool optimal = false;
352 BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
356 bool cycle_found = false;
357 while (!cycle_found) {
358 #ifdef _NO_BACK_STEP_
359 int curr_iter_num = length_bound <= node_num ?
360 length_bound - iter_num : node_num - iter_num;
362 int curr_iter_num = iter_num + length_bound <= node_num ?
363 length_bound : node_num - iter_num;
365 iter_num += curr_iter_num;
366 int real_iter_num = curr_iter_num;
367 for (int i = 0; i < curr_iter_num; ++i) {
368 if (bf.processNextWeakRound()) {
373 if (real_iter_num < curr_iter_num) {
377 // Searching for node disjoint negative cycles
378 for (ResNodeIt n(res_graph); n != INVALID; ++n)
381 for (ResNodeIt n(res_graph); n != INVALID; ++n) {
382 if (visited[n] > 0) continue;
384 ResNode u = pred[n] == INVALID ?
385 INVALID : res_graph.source(pred[n]);
386 while (u != INVALID && visited[u] == 0) {
388 u = pred[u] == INVALID ?
389 INVALID : res_graph.source(pred[u]);
391 if (u != INVALID && visited[u] == id) {
392 // Finding the negative cycle
397 Capacity d = res_graph.rescap(e);
398 while (res_graph.source(e) != u) {
399 cycle.push_back(e = pred[res_graph.source(e)]);
400 if (res_graph.rescap(e) < d)
401 d = res_graph.rescap(e);
406 // Augmenting along the cycle
407 for (int i = 0; i < cycle.size(); ++i)
408 res_graph.augment(cycle[i], d);
409 #ifdef _ONLY_ONE_CYCLE_
417 length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
422 std::cout << "Limited cycle-canceling algorithm finished. "
423 << "Found " << cycle_num << " negative cycles."
427 // Handling nonzero lower bounds
429 for (EdgeIt e(graph); e != INVALID; ++e)
430 flow[e] += (*lower)[e];
436 #ifdef MIN_MEAN_CYCLE_CANCELING
437 /// \brief Executes the minimum mean cycle-canceling algorithm
438 /// using \ref lemon::MinMeanCycle "MinMeanCycle" class.
440 typedef Path<ResGraph> ResPath;
441 MinMeanCycle<ResGraph, ResCostMap> mmc(res_graph, res_cost);
447 mmc.cyclePath(cycle).init();
448 if (mmc.findMinMean()) {
449 while (mmc.cycleLength() < 0) {
456 // Finding the largest flow amount that can be augmented
459 for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
460 if (delta == 0 || res_graph.rescap(e) < delta)
461 delta = res_graph.rescap(e);
464 // Augmenting along the cycle
465 for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
466 res_graph.augment(e, delta);
468 // Finding the minimum cycle mean for the modified residual
471 if (!mmc.findMinMean()) break;
476 std::cout << "Minimum mean cycle-canceling algorithm finished. "
477 << "Found " << cycle_num << " negative cycles."
481 // Handling nonzero lower bounds
483 for (EdgeIt e(graph); e != INVALID; ++e)
484 flow[e] += (*lower)[e];
490 }; //class CycleCanceling
496 #endif //LEMON_CYCLE_CANCELING_H