lemon-0.x: comparison lemon/cycle

equal deleted inserted replaced

-:6333c8397bbe
+:0d2cdd5860bc
 #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
+// The maximum number of iterations for the first execution of the
-/// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.
+// Bellman-Ford algorithm. It should be at least 2.
-/// It should be at least 2.
+#define STARTING_LIMIT        2
-#define STARTING_LIMIT	2
+// The iteration limit for the Bellman-Ford algorithm is multiplied by
-/// \brief The iteration limit for the
+// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
-/// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
+// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
-/// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
+#define ALPHA_MUL             3
-/// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
+#define ALPHA_DIV             2
-#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> 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>
 #include <lemon/path.h>
 #endif
+//#define _DEBUG_ITER_
 namespace lemon {
 /// \addtogroup min_cost_flow
 /// @{
-/// \brief Implementation of a cycle-canceling algorithm for finding
+/// \brief Implementation of a cycle-canceling algorithm for
-/// a minimum cost flow.
+/// finding a minimum cost flow.
 ///
-/// \ref lemon::CycleCanceling "CycleCanceling" implements a
+/// \ref CycleCanceling implements a cycle-canceling algorithm for
-/// cycle-canceling algorithm for finding a minimum cost flow.
+/// 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.
 /// \param SupplyMap The type of the supply map.
 ///
 /// \warning
-/// - Edge capacities and costs should be nonnegative integers.
+/// - Edge capacities and costs should be non-negative integers.
-///	However \c CostMap::Value should be signed type.
+///   However \c CostMap::Value should be signed type.
 /// - Supply values should be signed integers.
 /// - \c LowerMap::Value must be convertible to
-///	\c CapacityMap::Value and \c CapacityMap::Value must be
+///   \c CapacityMap::Value and \c CapacityMap::Value must be
-///	convertible to \c SupplyMap::Value.
+///   convertible to \c SupplyMap::Value.
 ///
 /// \author Peter Kovacs
 template < typename Graph,
 typename LowerMap = typename Graph::template EdgeMap<int>,
 typename CostMap = typename Graph::template EdgeMap<int>,
 typename SupplyMap = typename Graph::template NodeMap
 <typename CapacityMap::Value> >
 class CycleCanceling
 {
-typedef typename Graph::Node Node;
+GRAPH_TYPEDEFS(typename Graph);
-typedef typename Graph::NodeIt NodeIt;
-typedef typename Graph::Edge Edge;
-typedef typename Graph::EdgeIt EdgeIt;
-typedef typename Graph::InEdgeIt InEdgeIt;
-typedef typename Graph::OutEdgeIt OutEdgeIt;
 typedef typename LowerMap::Value Lower;
 typedef typename CapacityMap::Value Capacity;
 typedef typename CostMap::Value Cost;
 typedef typename SupplyMap::Value Supply;
-typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
+typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
-typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
+typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
 typedef ResGraphAdaptor< const Graph, Capacity,
-			     CapacityRefMap, CapacityRefMap > ResGraph;
+CapacityEdgeMap, CapacityEdgeMap > ResGraph;
 typedef typename ResGraph::Node ResNode;
 typedef typename ResGraph::NodeIt ResNodeIt;
 typedef typename ResGraph::Edge ResEdge;
 typedef typename ResGraph::EdgeIt ResEdgeIt;
 public:
-/// \brief The type of the flow map.
+/// The type of the flow map.
-typedef CapacityRefMap FlowMap;
+typedef typename Graph::template EdgeMap<Capacity> FlowMap;
 protected:
-/// \brief Map adaptor class for handling residual edge costs.
+/// Map adaptor class for handling residual edge costs.
 class ResCostMap : public MapBase<ResEdge, Cost>
 {
 private:
 const CostMap &cost_map;
 public:
 ResCostMap(const CostMap &_cost) : cost_map(_cost) {}
 Cost operator[](const ResEdge &e) const {
-	return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
+return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
 }
 }; //class ResCostMap
 protected:
-/// \brief The directed graph the algorithm runs on.
+/// The directed graph the algorithm runs on.
 const Graph &graph;
-/// \brief The original lower bound map.
+/// The original lower bound map.
 const LowerMap *lower;
-/// \brief The modified capacity map.
+/// The modified capacity map.
-CapacityRefMap capacity;
+CapacityEdgeMap capacity;
-/// \brief The cost map.
+/// The cost map.
 const CostMap &cost;
-/// \brief The modified supply map.
+/// The modified supply map.
-SupplyRefMap supply;
+SupplyNodeMap supply;
-/// \brief The sum of supply values equals zero.
 bool valid_supply;
-/// \brief The current flow.
+/// The current flow.
 FlowMap flow;
-/// \brief The residual graph.
+/// The residual graph.
 ResGraph res_graph;
-/// \brief The residual cost map.
+/// The residual cost map.
 ResCostMap res_cost;
 public :
 /// \brief General constructor of the class (with lower bounds).
 /// \param _lower The lower bounds of the edges.
 /// \param _capacity The capacities (upper bounds) of the edges.
 /// \param _cost The cost (length) values of the edges.
 /// \param _supply The supply values of the nodes (signed).
 CycleCanceling( const Graph &_graph,
-		    const LowerMap &_lower,
+const LowerMap &_lower,
-		    const CapacityMap &_capacity,
+const CapacityMap &_capacity,
-		    const CostMap &_cost,
+const CostMap &_cost,
-		    const SupplyMap &_supply ) :
+const SupplyMap &_supply ) :
 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
 supply(_graph), flow(_graph, 0),
 res_graph(_graph, capacity, flow), res_cost(cost)
 {
-// Removing nonzero lower bounds
+// Removing non-zero lower bounds
 capacity = subMap(_capacity, _lower);
 Supply sum = 0;
 for (NodeIt n(graph); n != INVALID; ++n) {
-	Supply s = _supply[n];
+Supply s = _supply[n];
-	for (InEdgeIt e(graph, n); e != INVALID; ++e)
+for (InEdgeIt e(graph, n); e != INVALID; ++e)
-	  s += _lower[e];
+s += _lower[e];
-	for (OutEdgeIt e(graph, n); e != INVALID; ++e)
+for (OutEdgeIt e(graph, n); e != INVALID; ++e)
-	  s -= _lower[e];
+s -= _lower[e];
-	sum += (supply[n] = s);
+sum += (supply[n] = s);
 }
 valid_supply = sum == 0;
 }
 /// \brief General constructor of the class (without lower bounds).
 /// \param _graph The directed graph the algorithm runs on.
 /// \param _capacity The capacities (upper bounds) of the edges.
 /// \param _cost The cost (length) values of the edges.
 /// \param _supply The supply values of the nodes (signed).
 CycleCanceling( const Graph &_graph,
-		    const CapacityMap &_capacity,
+const CapacityMap &_capacity,
-		    const CostMap &_cost,
+const CostMap &_cost,
-		    const SupplyMap &_supply ) :
+const SupplyMap &_supply ) :
 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
 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];
 valid_supply = sum == 0;
 }
 /// \brief Simple constructor of the class (with lower bounds).
 ///
 /// Simple constructor of the class (with lower bounds).
 ///
 /// \param _graph The directed graph the algorithm runs on.
 /// \param _capacity The capacities (upper bounds) of the edges.
 /// \param _cost The cost (length) values of the edges.
 /// \param _s The source node.
 /// \param _t The target node.
 /// \param _flow_value The required amount of flow from node \c _s
-/// to node \c _t (i.e. the supply of \c _s and the demand of
+/// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
-/// \c _t).
 CycleCanceling( const Graph &_graph,
-		    const LowerMap &_lower,
+const LowerMap &_lower,
-		    const CapacityMap &_capacity,
+const CapacityMap &_capacity,
-		    const CostMap &_cost,
+const CostMap &_cost,
-		    Node _s, Node _t,
+Node _s, Node _t,
-		    Supply _flow_value ) :
+Supply _flow_value ) :
 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
 supply(_graph), flow(_graph, 0),
 res_graph(_graph, capacity, flow), res_cost(cost)
 {
-// Removing nonzero lower bounds
+// Removing non-zero lower bounds
 capacity = subMap(_capacity, _lower);
 for (NodeIt n(graph); n != INVALID; ++n) {
-	Supply s = 0;
+Supply s = 0;
-	if (n == _s) s =  _flow_value;
+if (n == _s) s =  _flow_value;
-	if (n == _t) s = -_flow_value;
+if (n == _t) s = -_flow_value;
-	for (InEdgeIt e(graph, n); e != INVALID; ++e)
+for (InEdgeIt e(graph, n); e != INVALID; ++e)
-	  s += _lower[e];
+s += _lower[e];
-	for (OutEdgeIt e(graph, n); e != INVALID; ++e)
+for (OutEdgeIt e(graph, n); e != INVALID; ++e)
-	  s -= _lower[e];
+s -= _lower[e];
-	supply[n] = s;
+supply[n] = s;
 }
 valid_supply = true;
 }
 /// \brief Simple constructor of the class (without lower bounds).
 /// \param _capacity The capacities (upper bounds) of the edges.
 /// \param _cost The cost (length) values of the edges.
 /// \param _s The source node.
 /// \param _t The target node.
 /// \param _flow_value The required amount of flow from node \c _s
-/// to node \c _t (i.e. the supply of \c _s and the demand of
+/// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
-/// \c _t).
 CycleCanceling( const Graph &_graph,
-		    const CapacityMap &_capacity,
+const CapacityMap &_capacity,
-		    const CostMap &_cost,
+const CostMap &_cost,
-		    Node _s, Node _t,
+Node _s, Node _t,
-		    Supply _flow_value ) :
+Supply _flow_value ) :
 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
 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;
 }
+/// \brief Runs the algorithm.
+///
+/// Runs the algorithm.
+///
+/// \return \c true if a feasible flow can be found.
+bool run() {
+return init() && start();
+}
 /// \brief Returns a const reference to the flow map.
 ///
 /// Returns a const reference to the flow map.
 ///
 /// \pre \ref run() must be called before using this function.
 ///
 /// \pre \ref run() must be called before using this function.
 Cost totalCost() const {
 Cost c = 0;
 for (EdgeIt e(graph); e != INVALID; ++e)
-	c += flow[e] * cost[e];
+c += flow[e] * cost[e];
 return c;
 }
-/// \brief Runs the algorithm.
-///
-/// Runs the algorithm.
-///
-/// \return \c true if a feasible flow can be found.
-bool run() {
-return init() && start();
-}
 protected:
-/// \brief Initializes the algorithm.
+/// Initializes the algorithm.
 bool init() {
 // Checking the sum of supply values
 Supply sum = 0;
 for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
 if (sum != 0) return false;
 // Finding a feasible flow
-Circulation< Graph, ConstMap<Edge, Capacity>, CapacityRefMap,
+Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
-		   SupplyMap >
+SupplyMap >
-	circulation( graph, constMap<Edge>((Capacity)0), capacity,
+circulation( graph, constMap<Edge>((Capacity)0), capacity,
-		     supply );
+supply );
 circulation.flowMap(flow);
 return circulation.run();
 }
 #ifdef LIMITED_CYCLE_CANCELING
 /// \brief Executes a cycle-canceling algorithm using
-/// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited
+/// \ref Bellman-Ford algorithm with limited iteration count.
-/// iteration count.
 bool start() {
 typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph);
 typename ResGraph::template NodeMap<int> visited(res_graph);
 std::vector<ResEdge> cycle;
 int node_num = countNodes(graph);
 int cycle_num = 0;
 #endif
 int length_bound = STARTING_LIMIT;
 bool optimal = false;
 while (!optimal) {
-	BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
+BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
-	bf.predMap(pred);
+bf.predMap(pred);
-	bf.init(0);
+bf.init(0);
-	int iter_num = 0;
+int iter_num = 0;
-	bool cycle_found = false;
+bool cycle_found = false;
-	while (!cycle_found) {
+while (!cycle_found) {
 #ifdef _NO_BACK_STEP_
-	  int curr_iter_num = length_bound <= node_num ?
+int curr_iter_num = length_bound <= node_num ?
-			      length_bound - iter_num : node_num - iter_num;
+length_bound - iter_num : node_num - iter_num;
 #else
-	  int curr_iter_num = iter_num + length_bound <= node_num ?
+int curr_iter_num = iter_num + length_bound <= node_num ?
-			      length_bound : node_num - iter_num;
+length_bound : node_num - iter_num;
 #endif
-	  iter_num += curr_iter_num;
+iter_num += curr_iter_num;
-	  int real_iter_num = curr_iter_num;
+int real_iter_num = curr_iter_num;
-	  for (int i = 0; i < curr_iter_num; ++i) {
+for (int i = 0; i < curr_iter_num; ++i) {
-	    if (bf.processNextWeakRound()) {
+if (bf.processNextWeakRound()) {
-	      real_iter_num = i;
+real_iter_num = i;
-	      break;
+break;
-	    }
+}
-	  }
+}
-	  if (real_iter_num < curr_iter_num) {
+if (real_iter_num < curr_iter_num) {
-	    optimal = true;
+optimal = true;
-	    break;
+break;
-	  } else {
+} else {
-	    // Searching for node disjoint negative cycles
+// Searching for node disjoint negative cycles
-	    for (ResNodeIt n(res_graph); n != INVALID; ++n)
+for (ResNodeIt n(res_graph); n != INVALID; ++n)
-	      visited[n] = 0;
+visited[n] = 0;
-	    int id = 0;
+int id = 0;
-	    for (ResNodeIt n(res_graph); n != INVALID; ++n) {
+for (ResNodeIt n(res_graph); n != INVALID; ++n) {
-	      if (visited[n] > 0) continue;
+if (visited[n] > 0) continue;
-	      visited[n] = ++id;
+visited[n] = ++id;
-	      ResNode u = pred[n] == INVALID ?
+ResNode u = pred[n] == INVALID ?
-			  INVALID : res_graph.source(pred[n]);
+INVALID : res_graph.source(pred[n]);
-	      while (u != INVALID && visited[u] == 0) {
+while (u != INVALID && visited[u] == 0) {
-		visited[u] = id;
+visited[u] = id;
-		u = pred[u] == INVALID ?
+u = pred[u] == INVALID ?
-		    INVALID : res_graph.source(pred[u]);
+INVALID : res_graph.source(pred[u]);
-	      }
+}
-	      if (u != INVALID && visited[u] == id) {
+if (u != INVALID && visited[u] == id) {
-		// Finding the negative cycle
+// Finding the negative cycle
-		cycle_found = true;
+cycle_found = true;
-		cycle.clear();
+cycle.clear();
-		ResEdge e = pred[u];
+ResEdge e = pred[u];
-		cycle.push_back(e);
+cycle.push_back(e);
-		Capacity d = res_graph.rescap(e);
+Capacity d = res_graph.rescap(e);
-		while (res_graph.source(e) != u) {
+while (res_graph.source(e) != u) {
-		  cycle.push_back(e = pred[res_graph.source(e)]);
+cycle.push_back(e = pred[res_graph.source(e)]);
-		  if (res_graph.rescap(e) < d)
+if (res_graph.rescap(e) < d)
-		    d = res_graph.rescap(e);
+d = res_graph.rescap(e);
-		}
+}
 #ifdef _DEBUG_ITER_
-		++cycle_num;
+++cycle_num;
 #endif
-		// Augmenting along the cycle
+// Augmenting along the cycle
-		for (int i = 0; i < cycle.size(); ++i)
+for (int i = 0; i < cycle.size(); ++i)
-		  res_graph.augment(cycle[i], d);
+res_graph.augment(cycle[i], d);
 #ifdef _ONLY_ONE_CYCLE_
-		break;
+break;
 #endif
-	      }
+}
-	    }
+}
-	  }
+}
-	  if (!cycle_found)
+if (!cycle_found)
-	    length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
+length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
-	}
+}
 }
 #ifdef _DEBUG_ITER_
 std::cout << "Limited cycle-canceling algorithm finished. "
-		<< "Found " << cycle_num << " negative cycles."
+<< "Found " << cycle_num << " negative cycles."
-		<< std::endl;
+<< std::endl;
 #endif
-// Handling nonzero lower bounds
+// Handling non-zero lower bounds
 if (lower) {
-	for (EdgeIt e(graph); e != INVALID; ++e)
+for (EdgeIt e(graph); e != INVALID; ++e)
-	  flow[e] += (*lower)[e];
+flow[e] += (*lower)[e];
 }
 return true;
 }
 #endif
 #ifdef MIN_MEAN_CYCLE_CANCELING
 /// \brief Executes the minimum mean cycle-canceling algorithm
-/// using \ref lemon::MinMeanCycle "MinMeanCycle" class.
+/// using \ref MinMeanCycle.
 bool start() {
 typedef Path<ResGraph> ResPath;
 MinMeanCycle<ResGraph, ResCostMap> mmc(res_graph, res_cost);
 ResPath cycle;
 #ifdef _DEBUG_ITER_
 int cycle_num = 0;
 #endif
 mmc.cyclePath(cycle).init();
 if (mmc.findMinMean()) {
-	while (mmc.cycleLength() < 0) {
+while (mmc.cycleLength() < 0) {
 #ifdef _DEBUG_ITER_
-	  ++iter;
+++cycle_num;
 #endif
-	  // Finding the cycle
+// Finding the cycle
-	  mmc.findCycle();
+mmc.findCycle();
-	  // Finding the largest flow amount that can be augmented
+// Finding the largest flow amount that can be augmented
-	  // along the cycle
+// along the cycle
-	  Capacity delta = 0;
+Capacity delta = 0;
-	  for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
+for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
-	    if (delta == 0 || res_graph.rescap(e) < delta)
+if (delta == 0 || res_graph.rescap(e) < delta)
-	      delta = res_graph.rescap(e);
+delta = res_graph.rescap(e);
-	  }
+}
-	  // Augmenting along the cycle
+// Augmenting along the cycle
-	  for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
+for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
-	    res_graph.augment(e, delta);
+res_graph.augment(e, delta);
-	  // Finding the minimum cycle mean for the modified residual
+// Finding the minimum cycle mean for the modified residual
-	  // graph
+// graph
-	  mmc.reset();
+mmc.reset();
-	  if (!mmc.findMinMean()) break;
+if (!mmc.findMinMean()) break;
-	}
+}
 }
 #ifdef _DEBUG_ITER_
 std::cout << "Minimum mean cycle-canceling algorithm finished. "
-		<< "Found " << cycle_num << " negative cycles."
+<< "Found " << cycle_num << " negative cycles."
-		<< std::endl;
+<< std::endl;
 #endif
-// Handling nonzero lower bounds
+// Handling non-zero lower bounds
 if (lower) {
-	for (EdgeIt e(graph); e != INVALID; ++e)
+for (EdgeIt e(graph); e != INVALID; ++e)
-	  flow[e] += (*lower)[e];
+flow[e] += (*lower)[e];
 }
 return true;
 }
 #endif

changeset 2557	673cb4d1060b
parent 2553	bfced05fa852
child 2573	a9758ea1f01c