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

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

Location:

lemon

Files:

• capacity_scaling.h (modified) (10 diffs)
• cycle_canceling.h (modified) (15 diffs)
• network_simplex.h (modified) (3 diffs)

lemon/capacity_scaling.h

@@ -32 +32 @@
 #define WITH_SCALING
 
+//#define _DEBUG_ITER_
+
 namespace lemon {
 
@@ -38 +40 @@
 
   /// \brief Implementation of the capacity scaling version of the
-  /// succesive shortest path algorithm for finding a minimum cost flow.
+  /// successive shortest path algorithm for finding a minimum cost flow.
   ///
   /// \ref lemon::CapacityScaling "CapacityScaling" implements a
@@ -299 +301 @@
     /// \brief Map for identifing deficit nodes.
     DeficitBoolMap delta_deficit;
+
+    /// \brief The deficit nodes.
+    std::vector<ResNode> deficit_nodes;
 
 #else //WITHOUT_CAPACITY_SCALING
@@ -511 +516 @@
     }
 
-    /// \brief Runs the successive shortest path algorithm.
-    ///
-    /// Runs the successive shortest path algorithm.
+    /// \brief Runs the algorithm.
+    ///
+    /// Runs the algorithm.
     ///
     /// \return \c true if a feasible flow can be found.
@@ -532 +537 @@
 #ifdef WITH_SCALING
       // Initilaizing delta value
-      Capacity max_cap = 0;
-      for (EdgeIt e(graph); e != INVALID; ++e) {
-        if (capacity[e] > max_cap) max_cap = capacity[e];
-      }
-      for (delta = 1; 2 * delta < max_cap; delta *= 2) ;
+      Supply max_sup = 0, max_dem = 0;
+      for (NodeIt n(graph); n != INVALID; ++n) {
+        if (supply[n] >  max_sup) max_sup =  supply[n];
+        if (supply[n] < -max_dem) max_dem = -supply[n];
+      }
+      if (max_dem < max_sup) max_sup = max_dem;
+      for (delta = 1; 2 * delta < max_sup; delta *= 2) ;
 #endif
       return true;
@@ -547 +554 @@
       typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt;
       typedef typename DeltaResGraph::Edge DeltaResEdge;
+#ifdef _DEBUG_ITER_
+      int dijk_num = 0;
+#endif
 
       // Processing capacity scaling phases
@@ -565 +575 @@
         // Finding excess nodes
         excess_nodes.clear();
+        deficit_nodes.clear();
         for (ResNodeIt n(res_graph); n != INVALID; ++n) {
-          if (imbalance[n] >= delta) excess_nodes.push_back(n);
+          if (imbalance[n] >=  delta) excess_nodes.push_back(n);
+          if (imbalance[n] <= -delta) deficit_nodes.push_back(n);
         }
         next_node = 0;
 
-        // Finding successive shortest paths
+        // Finding shortest paths
         while (next_node < excess_nodes.size()) {
+          // Checking deficit nodes
+          if (delta > 1) {
+            bool delta_def = false;
+            for (int i = 0; i < deficit_nodes.size(); ++i) {
+              if (imbalance[deficit_nodes[i]] <= -delta) {
+                delta_def = true;
+                break;
+              }
+            }
+            if (!delta_def) break;
+          }
+
           // Running Dijkstra
           s = excess_nodes[next_node];
@@ -577 +601 @@
           dijkstra.init();
           dijkstra.addSource(s);
+#ifdef _DEBUG_ITER_
+          ++dijk_num;
+#endif
           if ((t = dijkstra.start(delta_deficit)) == INVALID) {
             if (delta > 1) {
@@ -609 +636 @@
         }
       }
+#ifdef _DEBUG_ITER_
+      std::cout << "Cost Scaling algorithm finished with running Dijkstra algorithm "
+        << dijk_num << " times." << std::endl;
+#endif
 
       // Handling nonzero lower bounds
@@ -629 +660 @@
       next_node = 0;
 
-      // Finding successive shortest paths
+      // Finding shortest paths
       ResNode s, t;
       while ( imbalance[excess_nodes[next_node]] > 0 ||

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;

lemon/network_simplex.h

@@ -276 +276 @@
 
       // Copying graph_ref to graph
+      graph.reserveNode(countNodes(graph_ref) + 1);
+      graph.reserveEdge(countEdges(graph_ref) + countNodes(graph_ref));
       copyGraph(graph, graph_ref)
         .edgeMap(cost, _cost)
@@ -478 +480 @@
       parent[root] = INVALID;
       pred_edge[root] = INVALID;
-      depth[root] = supply[root] = potential[root] = 0;
+      depth[root] = 0;
+      supply[root] = 0;
+      potential[root] = 0;
 
       // Adding artificial edges to the graph and initializing the node
@@ -514 +518 @@
       // Initializing block_size for the edge block pivot rule
       int edge_num = countEdges(graph);
-      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ? 
+      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
                    edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
 #endif