Changeset 2457:8c791ee69a45 in lemon-0.x for lemon/cycle_canceling.h

Timestamp:

06/15/07 16:36:24 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3294

Message:

Improvments in min cost flow algorithms

• improved cycle cancelling

File:

• lemon/cycle_canceling.h (modified) (15 diffs)

lemon/cycle_canceling.h

@@ -23 +23 @@
 ///
 /// \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>
@@ -29 +29 @@
 #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
@@ -37 +37 @@
   /// \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
@@ -61 +65 @@
   /// @{
 
-  /// \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
-  /// canceling algorithm for finding a minimum cost flow.
+  /// \ref lemon::CycleCanceling "CycleCanceling" implements a
+  /// cycle-canceling algorithm for finding a minimum cost flow.
   ///
   /// \param Graph The directed graph type the algorithm runs on.
@@ -119 +123 @@
   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>
@@ -171 +155 @@
     /// \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;
@@ -200 +182 @@
                     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)
     {
@@ -230 +212 @@
                     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)
     {
@@ -260 +242 @@
                     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)
     {
@@ -296 +278 @@
                     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)
     {
@@ -346 +328 @@
       // 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.
@@ -374 +356 @@
         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;
@@ -433 +420 @@
 
 #ifdef _DEBUG_ITER_
-      std::cout << "Limited cycle canceling algorithm finished. "
+      std::cout << "Limited cycle-canceling algorithm finished. "
                 << "Found " << cycle_num << " negative cycles."
                 << std::endl;
@@ -448 +435 @@
 
 #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() {
@@ -487 +474 @@
 
 #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;