Changeset 193:84c19824322a in lemon-0.x for src/work/edmonds_karp.h

Timestamp:

03/17/04 16:01:04 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

.

File:

• src/work/edmonds_karp.h (modified) (1 diff)

src/work/edmonds_karp.h

@@ -527 +527 @@
     }
   };
+
+
+  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+  class MaxMatching {
+  public:
+    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;
+
+    typedef typename Graph::NodeMap<bool> SMap;
+    typedef typename Graph::NodeMap<bool> TMap;
+  private:
+    const Graph* G;
+    SMap* S;
+    TMap* T;
+    //Node s;
+    //Node t;
+    FlowMap* flow;
+    const CapacityMap* capacity;
+    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
+    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
+    typedef typename AugGraph::Edge AugEdge;
+
+  public:
+    MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : 
+      G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { }
+    bool augmentOnShortestPath() {
+      AugGraph res_graph(*G, *flow, *capacity);
+      bool _augment=false;
+      
+      typedef typename AugGraph::NodeMap<bool> ReachedMap;
+      BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
+      typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
+      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
+        Number f=0;
+        for(OutEdgeIt e=G->template first<OutEdgeIt>(); G->valid(e); G->next(e))
+          f+=flow->get(e);
+        if (f<1) {
+          res_bfs.pushAndSetReached(s);
+          pred.set(s, AugEdge(INVALID));
+        }
+      }
+      
+      typename AugGraph::NodeMap<Number> free(res_graph);
+        
+      Node n;
+      //searching for augmenting path
+      while ( !res_bfs.finished() ) { 
+        AugOutEdgeIt e=res_bfs;
+        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
+          Node v=res_graph.tail(e);
+          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.free(e)));
+          } else {
+            free.set(w, res_graph.free(e)); 
+          }
+          if (TMap(res_graph.head(e))) { 
+            n=res_graph.head(e);
+            _augment=true; 
+            break; 
+          }
+        }
+        
+        ++res_bfs;
+      } //end of searching augmenting path
+
+      if (_augment) {
+        //Node n=t;
+        Number augment_value=free.get(t);
+        while (res_graph.valid(pred.get(n))) { 
+          AugEdge e=pred.get(n);
+          res_graph.augment(e, augment_value); 
+          n=res_graph.tail(e);
+        }
+      }
+
+      return _augment;
+    }
+
+//     template<typename MutableGraph> bool augmentOnBlockingFlow() {      
+//       bool _augment=false;
+
+//       AugGraph res_graph(*G, *flow, *capacity);
+
+//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
+//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
+
+//       bfs.pushAndSetReached(s);
+//       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
+//       while ( !bfs.finished() ) { 
+//      AugOutEdgeIt 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
+
+//       MutableGraph F;
+//       typename AugGraph::NodeMap<typename MutableGraph::Node> 
+//      res_graph_to_F(res_graph);
+//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
+//      res_graph_to_F.set(n, F.addNode());
+//       }
+      
+//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
+//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
+
+//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
+//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
+
+//       //Making F to the graph containing the edges of the residual graph 
+//       //which are in some shortest paths
+//       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
+//      if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
+//        typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+//        original_edge.update();
+//        original_edge.set(f, e);
+//        residual_capacity.update();
+//        residual_capacity.set(f, res_graph.free(e));
+//      } 
+//       }
+
+//       bool __augment=true;
+
+//       while (__augment) {
+//      __augment=false;
+//      //computing blocking flow with dfs
+//      typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
+//      DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
+//      typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
+//      pred.set(sF, typename MutableGraph::Edge(INVALID));
+//      //invalid iterators for sources
+
+//      typename MutableGraph::NodeMap<Number> free(F);
+
+//      dfs.pushAndSetReached(sF);      
+//      while (!dfs.finished()) {
+//        ++dfs;
+//        if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
+//          if (dfs.isBNodeNewlyReached()) {
+//            typename MutableGraph::Node v=F.aNode(dfs);
+//            typename MutableGraph::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)));
+//            } else {
+//              free.set(w, residual_capacity.get(dfs)); 
+//            }
+//            if (w==tF) { 
+//              __augment=true; 
+//              _augment=true;
+//              break; 
+//            }
+              
+//          } else {
+//            F.erase(typename MutableGraph::OutEdgeIt(dfs));
+//          }
+//        } 
+//      }
+
+//      if (__augment) {
+//        typename MutableGraph::Node n=tF;
+//        Number augment_value=free.get(tF);
+//        while (F.valid(pred.get(n))) { 
+//          typename MutableGraph::Edge e=pred.get(n);
+//          res_graph.augment(original_edge.get(e), augment_value); 
+//          n=F.tail(e);
+//          if (residual_capacity.get(e)==augment_value) 
+//            F.erase(e); 
+//          else 
+//            residual_capacity.set(e, residual_capacity.get(e)-augment_value);
+//        }
+//      }
+        
+//       }
+            
+//       return _augment;
+//     }
+//     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;
+//       BfsIterator4< 
+//      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;
+//      DfsIterator4< 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;
+      while (augmentOnShortestPath()) { 
+        //while (augmentOnBlockingFlow<MutableGraph>()) { 
+        //std::cout << ++num_of_augmentations << " ";
+        //std::cout<<std::endl;
+      } 
+    }
+    template<typename MutableGraph> void run() {
+      //int num_of_augmentations=0;
+      //while (augmentOnShortestPath()) { 
+        while (augmentOnBlockingFlow<MutableGraph>()) { 
+        //std::cout << ++num_of_augmentations << " ";
+        //std::cout<<std::endl;
+      } 
+    }
+    Number flowValue() { 
+      Number a=0;
+      OutEdgeIt e;
+      for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
+        a+=flow->get(e);
+      }
+      return a;
+    }
+  };
+
+
+
+