Changeset 59:41c7f9c09a12 in lemon-0.x for src/work/edmonds_karp.hh

Timestamp:

02/04/04 13:46:33 (19 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

.

File:

• src/work/edmonds_karp.hh (modified) (9 diffs)

src/work/edmonds_karp.hh

@@ -1 @@
-#ifndef MARCI_MAX_FLOW_HH
-#define MARCI_MAX_FLOW_HH
+#ifndef EDMONDS_KARP_HH
+#define EDMONDS_KARP_HH
 
 #include <algorithm>
@@ -8 +8 @@
 namespace marci {
 
-  template<typename Graph, typename T>
+  template<typename Graph, typename T, typename FlowMap, typename CapacityMap>
   class ResGraph {
     typedef typename Graph::NodeIt NodeIt;
@@ -14 +14 @@
     typedef typename Graph::SymEdgeIt OldSymEdgeIt;
     const Graph& G;
-    typename Graph::EdgeMap<T>& flow;
-    const typename Graph::EdgeMap<T>& capacity;
+    FlowMap& flow;
+    const CapacityMap& capacity;
   public:
-    ResGraph(const Graph& _G, typename Graph::EdgeMap<T>& _flow, 
-             const typename Graph::EdgeMap<T>& _capacity) : 
+    ResGraph(const Graph& _G, FlowMap& _flow, 
+             const CapacityMap& _capacity) : 
       G(_G), flow(_flow), capacity(_capacity) { }
 
@@ -27 +27 @@
 
     class EdgeIt {
-      friend class ResGraph<Graph, T>;
+      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
     protected:
-      const ResGraph<Graph, T>* resG;
+      const ResGraph<Graph, T, FlowMap, CapacityMap>* resG;
       OldSymEdgeIt sym;
     public:
@@ -52 +52 @@
 
     class OutEdgeIt : public EdgeIt {
-      friend class ResGraph<Graph, T>;
+      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
     public:
       OutEdgeIt() { }
       //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
     private:
-      OutEdgeIt(const ResGraph<Graph, T>& _resG, const NodeIt v) { 
+      OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, const NodeIt v) { 
         resG=&_resG;
         sym=resG->G.template first<OldSymEdgeIt>(v);
@@ -99 +99 @@
     template <typename ValueType>
     class NodeMap {
-      //const ResGraph<Graph, T>& G; 
       typename Graph::NodeMap<ValueType> node_map; 
     public:
-      NodeMap(const ResGraph<Graph, T>& _G) : node_map(_G.G)/*: G(_G)*/ { }
-      NodeMap(const ResGraph<Graph, T>& _G, const ValueType a) : node_map(_G.G, a) /*: G(_G)*/ { }
+      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
+      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, const ValueType a) : node_map(_G.G, a) { }
       void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); }
       ValueType get(const NodeIt nit) const { return node_map.get(nit); }
@@ -110 +109 @@
   };
 
-  template <typename Graph, typename T>
-  struct max_flow_type {
+  template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
+  class MaxFlow {
     typedef typename Graph::NodeIt NodeIt;
     typedef typename Graph::EdgeIt EdgeIt;
@@ -118 +117 @@
     typedef typename Graph::InEdgeIt InEdgeIt;
     const Graph& G;
-    NodeIt s;
-    NodeIt t;
-    typename Graph::EdgeMap<T> flow;
-    const typename Graph::EdgeMap<T>& capacity;
-
-    max_flow_type(const Graph& _G, NodeIt _s, NodeIt _t, const typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
+    const NodeIt s;
+    const NodeIt t;
+    FlowMap& flow;
+    const CapacityMap& capacity;
+    typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph;
+    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
+    typedef typename AugGraph::EdgeIt AugEdgeIt;
+  public:
+    MaxFlow(const Graph& _G, const NodeIt _s, const NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
+    bool augment() {
+      AugGraph res_graph(G, flow, capacity);
+      bool _augment=false;
+      
+      typedef typename AugGraph::NodeMap<bool> ReachedMap;
+      BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
+      res_bfs.pushAndSetReached(s);
+        
+      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
+      //filled with invalid iterators
+      
+      typename AugGraph::NodeMap<int> free(res_graph);
+        
+      //searching for augmenting path
+      while ( !res_bfs.finished() ) { 
+        //std::queue<AugOutEdgeIt> bfs_copy(res_bfs.getBfsQueue());
+        //while (!bfs_copy.empty()) {
+        //  AugOutEdgeIt e=bfs_copy.front();
+        //  bfs_copy.pop();
+        //  if (e.valid()) {
+        //    std::cout<<"queue:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<" ";
+        //  } else {
+        //    std::cout<<"queue:"<<res_graph.aNode(e)<<"->"<<" ";
+        //  }
+        //}
+        //std::cout<<std::endl;
+        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
+        //if (e.valid()) {
+        //  std::cout<<"actual:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<std::endl;
+        //} else {
+        //  std::cout<<"actual:"<<res_graph.aNode(e)<<"->"<<std::endl;
+        //}
+        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
+          NodeIt v=res_graph.tail(e);
+          NodeIt w=res_graph.head(e);
+          //std::cout<<v<<"->"<<w<<std::endl;
+          pred.set(w, e);
+          if (pred.get(v).valid()) {
+            free.set(w, std::min(free.get(v), e.free()));
+          } else {
+            free.set(w, e.free()); 
+          }
+          if (res_graph.head(e)==t) { _augment=true; break; }
+        }
+        
+        ++res_bfs;
+      } //end of searching augmenting path
+
+      if (_augment) {
+        NodeIt n=t;
+        T augment_value=free.get(t);
+        //std::cout<<"augmentation: ";
+        while (pred.get(n).valid()) { 
+          AugEdgeIt e=pred.get(n);
+          e.augment(augment_value); 
+          //std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
+          n=res_graph.tail(e);
+        }
+        //std::cout<<std::endl;
+      }
+      //std::cout << "actual flow: "<< std::endl;
+      //for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
+      //std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+      //}
+      //std::cout<<std::endl;
+
+      return _augment;
+    }
     void run() {
-      typedef ResGraph<Graph, T> AugGraph;
-      AugGraph res_graph(G, flow, capacity);
-
-      bool augment;
-      do {
-        augment=false;
-
-        typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
-        typedef typename AugGraph::EdgeIt AugEdgeIt;
-        typedef std::queue<AugOutEdgeIt> BfsQueue;
-        BfsQueue bfs_queue;
-        bfs_queue.push(res_graph.template first<AugOutEdgeIt>(s));
-
-        typedef typename AugGraph::NodeMap<bool> ReachedMap;
-        ReachedMap reached(res_graph, false);
-        reached.set(s, true); 
-        
-        bfs_iterator1< AugGraph, ReachedMap > 
-        res_bfs(res_graph, bfs_queue, reached);
-
-        typedef typename AugGraph::NodeMap<AugEdgeIt> PredMap;
-        PredMap pred(res_graph);
-        //typename AugGraph::EdgeIt a; //invalid
-        //a.makeInvalid();
-        //pred.set(s, a);
-
-        typedef typename AugGraph::NodeMap<int> FreeMap;
-        FreeMap free(res_graph);
-        
-        //searching for augmenting path
-        while ( res_bfs.valid() ) { 
-          //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
-          if (res_bfs.newly_reached()) {
-            AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
-            NodeIt v=res_graph.tail(e);
-            NodeIt w=res_graph.head(e);
-            //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
-            pred.set(w, e);
-            if (pred.get(v).valid()) {
-              free.set(w, std::min(free.get(v), e.free()));
-              //std::cout <<" nem elso csucs: ";
-              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
-            } else {
-              free.set(w, e.free()); 
-              //std::cout <<" elso csucs: ";
-              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
-            }
-            //std::cout<<std::endl;
-          }
-        
-          if (res_graph.head(res_bfs)==t) break;
-          ++res_bfs;
-        } //end searching augmenting path
-        if (reached.get(t)) {
-          augment=true;
-          NodeIt n=t;
-          T augment_value=free.get(t);
-          std::cout<<"augmentation: ";
-          while (pred.get(n).valid()) { 
-            AugEdgeIt e=pred.get(n);
-            e.augment(augment_value); 
-            std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
-            n=res_graph.tail(e);
-          }
-          std::cout<<std::endl;
-        }
-
-        std::cout << "actual flow: "<< std::endl;
-        for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
-          std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-        }
-        std::cout<<std::endl;
-
-      } while (augment);
+      while (augment()) { } 
     }
   };
@@ -204 +201 @@
 } // namespace marci
 
-#endif //MARCI_MAX_FLOW_HH
+#endif //EDMONDS_KARP_HH