lemon-0.x: comparison lemon/cycle

equal deleted inserted replaced

-:8eb62b97ed3e
+:3de895e36f2d
 #define LEMON_CYCLE_CANCELING_H
 /// \ingroup min_cost_flow
 ///
 /// \file
-/// \brief A cycle canceling algorithm for finding a minimum cost flow.
+/// \brief A cycle-canceling algorithm for finding a minimum cost flow.
 #include <vector>
 #include <lemon/circulation.h>
 #include <lemon/graph_adaptor.h>
-/// \brief The used cycle canceling method.
+/// \brief The used cycle-canceling method.
 #define LIMITED_CYCLE_CANCELING
 //#define MIN_MEAN_CYCLE_CANCELING
 #ifdef LIMITED_CYCLE_CANCELING
 #include <lemon/bellman_ford.h>
 /// \brief The maximum number of iterations for the first execution
 /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.
+/// It should be at least 2.
 #define STARTING_LIMIT	2
 /// \brief The iteration limit for the
 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
-/// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.
+/// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
+/// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
 #define ALPHA_MUL		3
 /// \brief The iteration limit for the
 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
-/// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.
+/// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
+/// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
 #define ALPHA_DIV		2
 //#define _ONLY_ONE_CYCLE_
+//#define _NO_BACK_STEP_
 //#define _DEBUG_ITER_
 #endif
 #ifdef MIN_MEAN_CYCLE_CANCELING
 #include <lemon/min_mean_cycle.h>
 namespace lemon {
 /// \addtogroup min_cost_flow
 /// @{
-/// \brief Implementation of a cycle canceling algorithm for finding
+/// \brief Implementation of a cycle-canceling algorithm for finding
 /// a minimum cost flow.
 ///
-/// \ref lemon::CycleCanceling "CycleCanceling" implements a cycle
+/// \ref lemon::CycleCanceling "CycleCanceling" implements a
-/// canceling algorithm for finding a minimum cost flow.
+/// cycle-canceling algorithm for finding a minimum cost flow.
 ///
 /// \param Graph The directed graph type the algorithm runs on.
 /// \param LowerMap The type of the lower bound map.
 /// \param CapacityMap The type of the capacity (upper bound) map.
 /// \param CostMap The type of the cost (length) map.
 /// \brief The type of the flow map.
 typedef CapacityRefMap FlowMap;
 protected:
-/// \brief Map adaptor class for demand map.
-class DemandMap : public MapBase<Node, Supply>
-{
-private:
-const SupplyMap *map;
-public:
-typedef typename MapBase<Node, Supply>::Value Value;
-typedef typename MapBase<Node, Supply>::Key Key;
-DemandMap(const SupplyMap &_map) : map(&_map) {}
-Value operator[](const Key &e) const {
-	return -(*map)[e];
-}
-}; //class DemandMap
 /// \brief Map adaptor class for handling residual edge costs.
 class ResCostMap : public MapBase<ResEdge, Cost>
 {
 private:
 CapacityRefMap capacity;
 /// \brief The cost map.
 const CostMap &cost;
 /// \brief The modified supply map.
 SupplyRefMap supply;
-/// \brief The modified demand map.
-DemandMap demand;
 /// \brief The sum of supply values equals zero.
 bool valid_supply;
 /// \brief The current flow.
 FlowMap flow;
 		    const LowerMap &_lower,
 		    const CapacityMap &_capacity,
 		    const CostMap &_cost,
 		    const SupplyMap &_supply ) :
 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
-supply(_graph), demand(supply), flow(_graph, 0),
+supply(_graph), flow(_graph, 0),
 res_graph(_graph, capacity, flow), res_cost(cost)
 {
 // Removing nonzero lower bounds
 capacity = subMap(_capacity, _lower);
 Supply sum = 0;
 CycleCanceling( const Graph &_graph,
 		    const CapacityMap &_capacity,
 		    const CostMap &_cost,
 		    const SupplyMap &_supply ) :
 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
-supply(_supply), demand(supply), flow(_graph, 0),
+supply(_supply), flow(_graph, 0),
 res_graph(_graph, capacity, flow), res_cost(cost)
 {
 // Checking the sum of supply values
 Supply sum = 0;
 for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
 		    const CapacityMap &_capacity,
 		    const CostMap &_cost,
 		    Node _s, Node _t,
 		    Supply _flow_value ) :
 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
-supply(_graph), demand(supply), flow(_graph, 0),
+supply(_graph), flow(_graph, 0),
 res_graph(_graph, capacity, flow), res_cost(cost)
 {
 // Removing nonzero lower bounds
 capacity = subMap(_capacity, _lower);
 for (NodeIt n(graph); n != INVALID; ++n) {
 		    const CapacityMap &_capacity,
 		    const CostMap &_cost,
 		    Node _s, Node _t,
 		    Supply _flow_value ) :
 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
-supply(_graph, 0), demand(supply), flow(_graph, 0),
+supply(_graph, 0), flow(_graph, 0),
 res_graph(_graph, capacity, flow), res_cost(cost)
 {
 supply[_s] =  _flow_value;
 supply[_t] = -_flow_value;
 valid_supply = true;
 for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
 if (sum != 0) return false;
 // Finding a feasible flow
 Circulation< Graph, Capacity, FlowMap, ConstMap<Edge, Capacity>,
-		   CapacityRefMap, DemandMap >
+		   CapacityRefMap, SupplyMap >
 	circulation( graph, constMap<Edge>((Capacity)0),
-		     capacity, demand, flow );
+		     capacity, supply, flow );
 return circulation.run() == -1;
 }
 #ifdef LIMITED_CYCLE_CANCELING
-/// \brief Executes a cycle canceling algorithm using
+/// \brief Executes a cycle-canceling algorithm using
 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited
 /// iteration count.
 bool start() {
 typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph);
 typename ResGraph::template NodeMap<int> visited(res_graph);
 	bf.predMap(pred);
 	bf.init(0);
 	int iter_num = 0;
 	bool cycle_found = false;
 	while (!cycle_found) {
+#ifdef _NO_BACK_STEP_
+	  int curr_iter_num = length_bound <= node_num ?
+			      length_bound - iter_num : node_num - iter_num;
+#else
 	  int curr_iter_num = iter_num + length_bound <= node_num ?
 			      length_bound : node_num - iter_num;
+#endif
 	  iter_num += curr_iter_num;
 	  int real_iter_num = curr_iter_num;
 	  for (int i = 0; i < curr_iter_num; ++i) {
 	    if (bf.processNextWeakRound()) {
 	      real_iter_num = i;
 	    length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
 	}
 }
 #ifdef _DEBUG_ITER_
-std::cout << "Limited cycle canceling algorithm finished. "
+std::cout << "Limited cycle-canceling algorithm finished. "
 		<< "Found " << cycle_num << " negative cycles."
 		<< std::endl;
 #endif
 // Handling nonzero lower bounds
 return true;
 }
 #endif
 #ifdef MIN_MEAN_CYCLE_CANCELING
-/// \brief Executes the minimum mean cycle canceling algorithm
+/// \brief Executes the minimum mean cycle-canceling algorithm
 /// using \ref lemon::MinMeanCycle "MinMeanCycle" class.
 bool start() {
 typedef Path<ResGraph> ResPath;
 MinMeanCycle<ResGraph, ResCostMap> mmc(res_graph, res_cost);
 ResPath cycle;
 	  if (!mmc.findMinMean()) break;
 	}
 }
 #ifdef _DEBUG_ITER_
-std::cout << "Minimum mean cycle canceling algorithm finished. "
+std::cout << "Minimum mean cycle-canceling algorithm finished. "
 		<< "Found " << cycle_num << " negative cycles."
 		<< std::endl;
 #endif
 // Handling nonzero lower bounds

changeset 2462	7a096a6bf53a
parent 2440	c9218405595b
child 2509	a8081c9cd96a