Changeset 109:fc5982b39e10 in lemon-0.x for src/work/jacint/preflow_hl3.h

Timestamp:

02/21/04 22:01:22 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

Flows with test files. The best is preflow.h

File:

• src/work/jacint/preflow_hl3.h (modified) (16 diffs)

src/work/jacint/preflow_hl3.h

@@ -3 +3 @@
 preflow_hl3.h
 by jacint. 
-Runs the highest label variant of the preflow push algorithm with 
-running time O(n^2\sqrt(m)), with the felszippantos 'empty level' 
-and with the two-phase heuristic: if there is no active node of
-level at most n, then we go into phase 1, do a bfs
-from s, and flow the excess back to s.
-
-In phase 1 we shift everything downwards by n.
-
-'A' is a parameter for the empty_level heuristic
-
-Member functions:
-
-void run() : runs the algorithm
-
- The following functions should be used after run() was already run.
-
-T maxflow() : returns the value of a maximum flow
-
-T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
-
-FlowMap allflow() : returns the fixed maximum flow x
-
-void mincut(CutMap& M) : sets M to the characteristic vector of a 
+
+Heuristics: 
+
+ suck gap : if there is a gap, then we put all 
+   nodes reachable from the relabelled node to level n
+ 2 phase
+ highest label
+
+The constructor runs the algorithm.
+
+Members:
+
+T maxFlow() : returns the value of a maximum flow
+
+T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
+
+FlowMap Flow() : returns the fixed maximum flow x
+
+void minCut(CutMap& M) : sets M to the characteristic vector of a 
      minimum cut. M should be a map of bools initialized to false.
 
-void min_mincut(CutMap& M) : sets M to the characteristic vector of the 
+void minMinCut(CutMap& M) : sets M to the characteristic vector of the 
      minimum min cut. M should be a map of bools initialized to false.
 
-void max_mincut(CutMap& M) : sets M to the characteristic vector of the 
+void maxMinCut(CutMap& M) : sets M to the characteristic vector of the 
      maximum min cut. M should be a map of bools initialized to false.
 
@@ -38 +34 @@
 #ifndef PREFLOW_HL3_H
 #define PREFLOW_HL3_H
-
-#define A 1
 
 #include <vector>
@@ -45 +39 @@
 #include <queue>
 
+#include <time_measure.h> //for test
+
 namespace hugo {
 
   template <typename Graph, typename T, 
-    typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>, 
-    typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> >
+    typename FlowMap=typename Graph::EdgeMap<T>, 
+    typename CapMap=typename Graph::EdgeMap<T> >
   class preflow_hl3 {
     
@@ -67 +63 @@
   public:
 
+    double time; //for test
+
     preflow_hl3(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
-      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
-
-
-    void run() {
- 
+      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) {
+      
       bool phase=0;
       int n=G.nodeNum(); 
@@ -81 +76 @@
       */
 
-      IntMap level(G,n);      
-      TMap excess(G); 
+      typename Graph::NodeMap<int> level(G,n);      
+      typename Graph::NodeMap<T> excess(G); 
       
       std::vector<int> numb(n);    
@@ -149 +144 @@
           if ( phase ) break; 
           phase=1;
-
+          time=currTime();
+          
           level.set(s,0);
 
@@ -188 +184 @@
         else {
           
-          NodeIt w=stack[b].top();        //w is a highest label active node.
+          NodeIt w=stack[b].top(); 
           stack[b].pop();           
           int lev=level.get(w);
-          int exc=excess.get(w);
-          int newlevel=n;                 //In newlevel we bound the next level of w.
+          T exc=excess.get(w);
+          int newlevel=n;          //bound on the next level of w.
           
           for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
@@ -207 +203 @@
               /*v becomes active.*/
               
-              int cap=capacity.get(e);
-              int flo=flow.get(e);
-              int remcap=cap-flo;
+              T cap=capacity.get(e);
+              T flo=flow.get(e);
+              T remcap=cap-flo;
               
               if ( remcap >= exc ) {       
@@ -245 +241 @@
               /*v becomes active.*/
               
-              int flo=flow.get(e);
+              T flo=flow.get(e);
               
               if ( flo >= exc ) { 
@@ -350 +346 @@
      */
 
-    T maxflow() {
+    T maxFlow() {
       return value;
     }
@@ -357 +353 @@
 
     /*
-      For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e). 
+      For the maximum flow x found by the algorithm, 
+      it returns the flow value on edge e, i.e. x(e). 
     */
 
-    T flowonedge(EdgeIt e) {
+    T flowOnEdge(EdgeIt e) {
       return flow.get(e);
     }
@@ -370 +367 @@
     */
 
-    FlowMap allflow() {
+    FlowMap Flow() {
       return flow;
     }
@@ -382 +379 @@
     
     template<typename CutMap>
-    void mincut(CutMap& M) {
+    void minCut(CutMap& M) {
     
       std::queue<NodeIt> queue;
@@ -421 +418 @@
     
     template<typename CutMap>
-    void max_mincut(CutMap& M) {
+    void maxMinCut(CutMap& M) {
     
       std::queue<NodeIt> queue;
@@ -458 +455 @@
 
     template<typename CutMap>
-    void min_mincut(CutMap& M) {
-      mincut(M);
+    void minMinCut(CutMap& M) {
+      minCut(M);
     }
 
@@ -465 +462 @@
 
   };
-}//namespace hugo
+}//namespace
 #endif