Changeset 647:19dd325da0e8 in lemon-0.x for src/work/jacint/max_flow.h

Timestamp:

05/19/04 18:09:38 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

the same

File:

• src/work/jacint/max_flow.h (modified) (25 diffs)

src/work/jacint/max_flow.h

@@ -26 +26 @@
   ///maximum value in a directed graph. The \e source node, the \e
   ///target node, the \e capacity of the edges and the \e starting \e
-  ///flow value of the edges can be passed to the algorithm through the
+  ///flow value of the edges should be passed to the algorithm through the
   ///constructor. It is possible to change these quantities using the
   ///functions \ref resetSource, \ref resetTarget, \ref resetCap and
   ///\ref resetFlow. Before any subsequent runs of any algorithm of
-  ///the class \ref resetFlow should be called, otherwise it will
-  ///start from a maximum flow.                                                                                                                 
-  ///After running an algorithm of the class, the maximum value of a
-  ///value can be obtained by calling \ref flowValue(). The minimum
+  ///the class \ref resetFlow should be called. 
+
+  ///After running an algorithm of the class, the actual flow value 
+  ///can be obtained by calling \ref flowValue(). The minimum
   ///value cut can be written into a \c node map of \c bools by
   ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes
@@ -40 +40 @@
   ///\param Graph The directed graph type the algorithm runs on.
   ///\param Num The number type of the capacities and the flow values.
-  ///\param CapMap The type of the capacity map.
-  ///\param FlowMap The type of the flow map.                                                                                                           
+  ///\param CapMap The capacity map type.
+  ///\param FlowMap The flow map type.                                                                                                           
   ///\author Marton Makai, Jacint Szabo 
   template <typename Graph, typename Num,
@@ -112 +112 @@
     ///- \c NO_FLOW: indicates an unspecified edge map. \ref flow will be 
     ///set to the constant zero flow in the beginning of the algorithm in this case.
-    enum flowEnum{
+    enum FlowEnum{
       ZERO_FLOW,
       GEN_FLOW,
@@ -119 +119 @@
     };
 
+    enum StatusEnum {
+      AFTER_NOTHING,
+      AFTER_AUGMENTING,
+      AFTER_PRE_FLOW_PHASE_1,      
+      AFTER_PRE_FLOW_PHASE_2
+    };
+
+    /// Don not needle this flag only if necessary.
+    StatusEnum status;
+    int number_of_augmentations;
+
+
+    template<typename IntMap>
+    class TrickyReachedMap {
+    protected:
+      IntMap* map;
+      int* number_of_augmentations;
+    public:
+      TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) : 
+        map(&_map), number_of_augmentations(&_number_of_augmentations) { }
+      void set(const Node& n, bool b) {
+        map->set(n, *number_of_augmentations);
+      }
+      bool operator[](const Node& n) const { 
+        return (*map)[n]==*number_of_augmentations; 
+      }
+    };
+    
     MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
             FlowMap& _flow) :
       g(&_G), s(_s), t(_t), capacity(&_capacity),
-      flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
+      flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0), 
+      status(AFTER_NOTHING), number_of_augmentations(0) { }
 
     ///Runs a maximum flow algorithm.
@@ -133 +162 @@
     /// - an arbitary preflow if \c fe is \c PRE_FLOW,
     /// - any map if \c fe is NO_FLOW.
-    void run(flowEnum fe=ZERO_FLOW) {
+    void run(FlowEnum fe=ZERO_FLOW) {
       preflow(fe);
     }
 
-                                                                                             
+                                                                              
     ///Runs a preflow algorithm.  
 
@@ -147 +176 @@
     /// - an arbitary preflow if \c fe is \c PRE_FLOW,
     /// - any map if \c fe is NO_FLOW.
-    void preflow(flowEnum fe) {
+    void preflow(FlowEnum fe) {
       preflowPhase1(fe);
       preflowPhase2();
@@ -174 +203 @@
     /// - an arbitary preflow if \c fe is \c PRE_FLOW,
     /// - any map if \c fe is NO_FLOW.
-    void preflowPhase1( flowEnum fe );
+    void preflowPhase1(FlowEnum fe);
 
     ///Runs the second phase of the preflow algorithm.
@@ -190 +219 @@
     /// The return value shows if the augmentation was succesful.
     bool augmentOnShortestPath();
+    bool augmentOnShortestPath2();
 
     /// Starting from a flow, this method searches for an augmenting blocking
@@ -208 +238 @@
     /// over-flow of the target node \ref t.
     /// It can be called already after running \ref preflowPhase1.
-    Num flowValue() {
+    Num flowValue() const {
       Num a=0;
       FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e];
@@ -229 +259 @@
     /// for MinCut computation
     template<typename _CutMap>
-    void actMinCut(_CutMap& M) {
+    void actMinCut(_CutMap& M) const {
       NodeIt v;
-      for(g->first(v); g->valid(v); g->next(v)) {
-        if ( level[v] < n ) {
-          M.set(v,false);
-        } else {
-          M.set(v,true);
-        }
+      switch (status) {
+        case AFTER_PRE_FLOW_PHASE_1:
+        for(g->first(v); g->valid(v); g->next(v)) {
+          if (level[v] < n) {
+            M.set(v, false);
+          } else {
+            M.set(v, true);
+          }
+        }
+        break;
+        case AFTER_PRE_FLOW_PHASE_2:
+        case AFTER_NOTHING:
+        minMinCut(M);
+        break;
+        case AFTER_AUGMENTING:
+        for(g->first(v); g->valid(v); g->next(v)) {
+          if (level[v]) {
+            M.set(v, true);
+          } else {
+            M.set(v, false);
+          }
+        }
+        break;
       }
     }
@@ -248 +295 @@
     ///\pre \c flow must be a maximum flow.
     template<typename _CutMap>
-    void minMinCut(_CutMap& M) {
-
+    void minMinCut(_CutMap& M) const {
       std::queue<Node> queue;
 
@@ -287 +333 @@
     ///\pre \c flow must be a maximum flow. 
     template<typename _CutMap>
-    void maxMinCut(_CutMap& M) {
+    void maxMinCut(_CutMap& M) const {
 
       NodeIt v;
@@ -329 +375 @@
     ///\pre \c flow must be a maximum flow.    
     template<typename CutMap>
-    void minCut(CutMap& M) { minMinCut(M); }
+    void minCut(CutMap& M) const { minMinCut(M); }
 
     ///Resets the source node to \c _s.
@@ -335 +381 @@
     ///Resets the source node to \c _s.
     /// 
-    void resetSource(Node _s) { s=_s; }
+    void resetSource(Node _s) { s=_s; status=AFTER_NOTHING; }
 
     ///Resets the target node to \c _t.
@@ -341 +387 @@
     ///Resets the target node to \c _t.
     ///
-    void resetTarget(Node _t) { t=_t; }
+    void resetTarget(Node _t) { t=_t; status=AFTER_NOTHING; }
 
     /// Resets the edge map of the capacities to _cap.
@@ -347 +393 @@
     /// Resets the edge map of the capacities to _cap.
     /// 
-    void resetCap(const CapMap& _cap) { capacity=&_cap; }
+    void resetCap(const CapMap& _cap) { capacity=&_cap; status=AFTER_NOTHING; }
 
     /// Resets the edge map of the flows to _flow.
@@ -353 +399 @@
     /// Resets the edge map of the flows to _flow.
     /// 
-    void resetFlow(FlowMap& _flow) { flow=&_flow; }
+    void resetFlow(FlowMap& _flow) { flow=&_flow; status=AFTER_NOTHING; }
 
 
@@ -435 +481 @@
 
 
-    void preflowPreproc(flowEnum fe, VecStack& active,
+    void preflowPreproc(FlowEnum fe, VecStack& active,
                         VecNode& level_list, NNMap& left, NNMap& right)
     {
@@ -639 +685 @@
         dist.set(n, a);
       }
-      int operator[](const typename MapGraphWrapper::Node& n)
-      { return dist[n]; }
+      int operator[](const typename MapGraphWrapper::Node& n) const { 
+        return dist[n]; 
+      }
       //       int get(const typename MapGraphWrapper::Node& n) const {
       //        return dist[n]; }
@@ -654 +701 @@
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1( flowEnum fe )
+  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1(FlowEnum fe)
   {
 
@@ -767 +814 @@
       }
     }
+
+    status=AFTER_PRE_FLOW_PHASE_1;
   }
 
@@ -831 +880 @@
       }  // if stack[b] is nonempty
     } // while(true)
+
+    status=AFTER_PRE_FLOW_PHASE_2;
   }
 
@@ -879 +930 @@
     }
 
+    status=AFTER_AUGMENTING;
     return _augment;
   }
 
 
-
-
-
+  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
+  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath2()
+  {
+    ResGW res_graph(*g, *capacity, *flow);
+    bool _augment=false;
+
+    if (status!=AFTER_AUGMENTING) {
+      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, -1); 
+      number_of_augmentations=0;
+    } else {
+      ++number_of_augmentations;
+    }
+    TrickyReachedMap<ReachedMap> 
+      tricky_reached_map(level, number_of_augmentations);
+    //ReachedMap level(res_graph);
+//    FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+    BfsIterator<ResGW, TrickyReachedMap<ReachedMap> > 
+      bfs(res_graph, tricky_reached_map);
+    bfs.pushAndSetReached(s);
+
+    typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
+    pred.set(s, INVALID);
+
+    typename ResGW::template NodeMap<Num> free(res_graph);
+
+    //searching for augmenting path
+    while ( !bfs.finished() ) {
+      ResGWOutEdgeIt e=bfs;
+      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
+        Node v=res_graph.tail(e);
+        Node w=res_graph.head(e);
+        pred.set(w, e);
+        if (res_graph.valid(pred[v])) {
+          free.set(w, std::min(free[v], res_graph.resCap(e)));
+        } else {
+          free.set(w, res_graph.resCap(e));
+        }
+        if (res_graph.head(e)==t) { _augment=true; break; }
+      }
+
+      ++bfs;
+    } //end of searching augmenting path
+
+    if (_augment) {
+      Node n=t;
+      Num augment_value=free[t];
+      while (res_graph.valid(pred[n])) {
+        ResGWEdge e=pred[n];
+        res_graph.augment(e, augment_value);
+        n=res_graph.tail(e);
+      }
+    }
+
+    status=AFTER_AUGMENTING;
+    return _augment;
+  }
 
 
@@ -1000 +1105 @@
     }
 
+    status=AFTER_AUGMENTING;
     return _augment;
   }
@@ -1130 +1236 @@
     } //while (__augment)
 
+    status=AFTER_AUGMENTING;
     return _augment;
   }