Changeset 303:1b377a730d02 in lemon-0.x for src/work/marci/edmonds_karp.h

Timestamp:

04/05/04 18:52:46 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

konvergalunk, konvergalunk...

File:

• src/work/marci/edmonds_karp.h (modified) (23 diffs)

src/work/marci/edmonds_karp.h

@@ -9 +9 @@
 #include <bfs_iterator.h>
 #include <invalid.h>
+#include <graph_wrapper.h>
 
 namespace hugo {
@@ -248 +249 @@
 
 
-  template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
+  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
   class MaxFlow {
   protected:
-    typedef GraphWrapper GW;
-    typedef typename GW::Node Node;
-    typedef typename GW::Edge Edge;
-    typedef typename GW::EdgeIt EdgeIt;
-    typedef typename GW::OutEdgeIt OutEdgeIt;
-    typedef typename GW::InEdgeIt InEdgeIt;
-    //const Graph* G;
-    GW gw;
+    typedef typename Graph::Node Node;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::EdgeIt EdgeIt;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    typedef typename Graph::InEdgeIt InEdgeIt;
+    const Graph* g;
     Node s;
     Node t;
     FlowMap* flow;
     const CapacityMap* capacity;
-    typedef ResGraphWrapper<GW, Number, FlowMap, CapacityMap > ResGW;
+    typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW;
     typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
     typedef typename ResGW::Edge ResGWEdge;
   public:
 
-    MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : 
-      gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
+    MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : 
+      g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
 
     bool augmentOnShortestPath() {
-      ResGW res_graph(gw, *flow, *capacity);
+      ResGW res_graph(*g, *flow, *capacity);
       bool _augment=false;
       
@@ -291 +290 @@
           Node w=res_graph.head(e);
           pred.set(w, e);
-          if (res_graph.valid(pred.get(v))) {
-            free.set(w, std::min(free.get(v), res_graph.resCap(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)); 
@@ -304 +303 @@
       if (_augment) {
         Node n=t;
-        Number augment_value=free.get(t);
-        while (res_graph.valid(pred.get(n))) { 
-          ResGWEdge e=pred.get(n);
+        Number 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);
@@ -318 +317 @@
     class DistanceMap {
     protected:
-      MapGraphWrapper gw;
+      const MapGraphWrapper* g;
       typename MapGraphWrapper::NodeMap<int> dist; 
     public:
-      DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
+      DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
       void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
-      int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
-      bool get(const typename MapGraphWrapper::Edge& e) const { 
-        return (dist.get(gw.tail(e))<dist.get(gw.head(e))); 
+      int operator[](const typename MapGraphWrapper::Node& n) 
+        { return dist[n]; }
+//       int get(const typename MapGraphWrapper::Node& n) const { 
+//      return dist[n]; }
+//       bool get(const typename MapGraphWrapper::Edge& e) const { 
+//      return (dist.get(g->tail(e))<dist.get(g->head(e))); }
+      bool operator[](const typename MapGraphWrapper::Edge& e) const { 
+        return (dist[g->tail(e)]<dist[g->head(e)]); 
       }
     };
@@ -333 +337 @@
       bool _augment=false;
 
-      ResGW res_graph(gw, *flow, *capacity);
+      ResGW res_graph(*g, *flow, *capacity);
 
       typedef typename ResGW::NodeMap<bool> ReachedMap;
@@ -344 +348 @@
         ResGWOutEdgeIt e=bfs;
         if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
-          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+          dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
         }
         ++bfs;
@@ -360 +364 @@
       }
 
-      typename MG::Node sF=res_graph_to_F.get(s);
-      typename MG::Node tF=res_graph_to_F.get(t);
+      typename MG::Node sF=res_graph_to_F[s];
+      typename MG::Node tF=res_graph_to_F[t];
       typename MG::EdgeMap<ResGWEdge> original_edge(F);
       typename MG::EdgeMap<Number> residual_capacity(F);
@@ -371 +375 @@
         for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
           //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
-          typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+          typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
           original_edge.update();
           original_edge.set(f, e);
@@ -401 +405 @@
               typename MG::Node w=F.bNode(dfs);
               pred.set(w, dfs);
-              if (F.valid(pred.get(v))) {
-                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
+              if (F.valid(pred[v])) {
+                free.set(w, std::min(free[v], residual_capacity[dfs]));
               } else {
-                free.set(w, residual_capacity.get(dfs)); 
+                free.set(w, residual_capacity[dfs]); 
               }
               if (w==tF) { 
@@ -420 +424 @@
         if (__augment) {
           typename MG::Node n=tF;
-          Number augment_value=free.get(tF);
-          while (F.valid(pred.get(n))) { 
-            typename MG::Edge e=pred.get(n);
-            res_graph.augment(original_edge.get(e), augment_value); 
+          Number augment_value=free[tF];
+          while (F.valid(pred[n])) { 
+            typename MG::Edge e=pred[n];
+            res_graph.augment(original_edge[e], augment_value); 
             n=F.tail(e);
-            if (residual_capacity.get(e)==augment_value) 
+            if (residual_capacity[e]==augment_value) 
               F.erase(e); 
             else 
-              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
+              residual_capacity.set(e, residual_capacity[e]-augment_value);
           }
         }
@@ -441 +445 @@
       bool _augment=false;
 
-      ResGW res_graph(gw, *flow, *capacity);
+      ResGW res_graph(*g, *flow, *capacity);
 
       //bfs for distances on the residual graph
@@ -460 +464 @@
       }
 
-      typename MG::Node sF=res_graph_to_F.get(s);
-      typename MG::Node tF=res_graph_to_F.get(t);
+      typename MG::Node sF=res_graph_to_F[s];
+      typename MG::Node tF=res_graph_to_F[t];
       typename MG::EdgeMap<ResGWEdge> original_edge(F);
       typename MG::EdgeMap<Number> residual_capacity(F);
@@ -469 +473 @@
         if (res_graph.valid(e)) {
           if (bfs.isBNodeNewlyReached()) {
-            dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
-            typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+            dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
+            typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
             original_edge.update();
             original_edge.set(f, e);
@@ -476 +480 @@
             residual_capacity.set(f, res_graph.resCap(e));
           } else {
-            if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
-              typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+            if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
+              typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
               original_edge.update();
               original_edge.set(f, e);
@@ -509 +513 @@
               typename MG::Node w=F.bNode(dfs);
               pred.set(w, dfs);
-              if (F.valid(pred.get(v))) {
-                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
+              if (F.valid(pred[v])) {
+                free.set(w, std::min(free[v], residual_capacity[dfs]));
               } else {
-                free.set(w, residual_capacity.get(dfs)); 
+                free.set(w, residual_capacity[dfs]); 
               }
               if (w==tF) { 
@@ -528 +532 @@
         if (__augment) {
           typename MG::Node n=tF;
-          Number augment_value=free.get(tF);
-          while (F.valid(pred.get(n))) { 
-            typename MG::Edge e=pred.get(n);
-            res_graph.augment(original_edge.get(e), augment_value); 
+          Number augment_value=free[tF];
+          while (F.valid(pred[n])) { 
+            typename MG::Edge e=pred[n];
+            res_graph.augment(original_edge[e], augment_value); 
             n=F.tail(e);
-            if (residual_capacity.get(e)==augment_value) 
+            if (residual_capacity[e]==augment_value) 
               F.erase(e); 
             else 
-              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
+              residual_capacity.set(e, residual_capacity[e]-augment_value);
           }
         }
@@ -548 +552 @@
       bool _augment=false;
 
-      ResGW res_graph(gw, *flow, *capacity);
+      ResGW res_graph(*g, *flow, *capacity);
 
       typedef typename ResGW::NodeMap<bool> ReachedMap;
@@ -558 +562 @@
         ResGWOutEdgeIt e=bfs;
         if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
-          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+          dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
         }
         ++bfs;
@@ -611 +615 @@
 
               pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
-              if (erasing_res_graph.valid(pred.get(v))) {
-                free.set(w, std::min(free.get(v), res_graph.resCap(dfs)));
+              if (erasing_res_graph.valid(pred[v])) {
+                free.set(w, std::min(free[v], res_graph.resCap(dfs)));
               } else {
                 free.set(w, res_graph.resCap(dfs)); 
@@ -630 +634 @@
         if (__augment) {
           typename ErasingResGW::Node n=t;
-          Number augment_value=free.get(n);
-          while (erasing_res_graph.valid(pred.get(n))) { 
-            typename ErasingResGW::OutEdgeIt e=pred.get(n);
+          Number augment_value=free[n];
+          while (erasing_res_graph.valid(pred[n])) { 
+            typename ErasingResGW::OutEdgeIt e=pred[n];
             res_graph.augment(e, augment_value);
             n=erasing_res_graph.tail(e);
@@ -645 +649 @@
     }
 
-//     bool augmentOnBlockingFlow2() {
-//       bool _augment=false;
-
-//       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
-//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
-//       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
-//       typedef typename EAugGraph::Edge EAugEdge;
-
-//       EAugGraph res_graph(*G, *flow, *capacity);
-
-//       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
-//       BfsIterator5< 
-//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 
-//      /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ 
-//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
-      
-//       bfs.pushAndSetReached(s);
-
-//       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
-//      NodeMap<int>& dist=res_graph.dist;
-
-//       while ( !bfs.finished() ) {
-//      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
-//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
-//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
-//      }
-//      ++bfs;  
-//       } //computing distances from s in the residual graph
-
-//       bool __augment=true;
-
-//       while (__augment) {
-
-//      __augment=false;
-//      //computing blocking flow with dfs
-//      typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
-//      DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > 
-//        dfs(res_graph);
-//      typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); 
-//      pred.set(s, EAugEdge(INVALID));
-//      //invalid iterators for sources
-
-//      typename EAugGraph::NodeMap<Number> free(res_graph);
-
-//      dfs.pushAndSetReached(s);
-//      while (!dfs.finished()) {
-//        ++dfs;
-//        if (res_graph.valid(EAugOutEdgeIt(dfs))) { 
-//          if (dfs.isBNodeNewlyReached()) {
-          
-//            typename EAugGraph::Node v=res_graph.aNode(dfs);
-//            typename EAugGraph::Node w=res_graph.bNode(dfs);
-
-//            pred.set(w, EAugOutEdgeIt(dfs));
-//            if (res_graph.valid(pred.get(v))) {
-//              free.set(w, std::min(free.get(v), res_graph.free(dfs)));
-//            } else {
-//              free.set(w, res_graph.free(dfs)); 
-//            }
-              
-//            if (w==t) { 
-//              __augment=true; 
-//              _augment=true;
-//              break; 
-//            }
-//          } else {
-//            res_graph.erase(dfs);
-//          }
-//        } 
-
-//      }
-
-//      if (__augment) {
-//        typename EAugGraph::Node n=t;
-//        Number augment_value=free.get(t);
-//        while (res_graph.valid(pred.get(n))) { 
-//          EAugEdge e=pred.get(n);
-//          res_graph.augment(e, augment_value);
-//          n=res_graph.tail(e);
-//          if (res_graph.free(e)==0)
-//            res_graph.erase(e);
-//        }
-//      }
-      
-//       }
-            
-//       return _augment;
-//     }
-
     void run() {
       //int num_of_augmentations=0;
@@ -755 +670 @@
       Number a=0;
       OutEdgeIt e;
-      for(gw.first(e, s); gw.valid(e); gw.next(e)) {
-        a+=flow->get(e);
+      for(g->first(e, s); g->valid(e); g->next(e)) {
+        a+=(*flow)[e];
       }
       return a;