Changeset 206:47f62d789fe7 in lemon-0.x for src/work

Timestamp:

03/19/04 10:09:20 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

.

Location:

src/work

Files:

• edmonds_karp.h (modified) (1 diff)
• marci/dimacs.h (modified) (1 diff)
• marci/edmonds_karp_demo.cc (modified) (2 diffs)

src/work/edmonds_karp.h ¶

@@ -357 +357 @@
         } 
       }
+
+      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;
+    }
+    template<typename MutableGraph> bool augmentOnBlockingFlow1() {      
+      bool _augment=false;
+
+      AugGraph res_graph(*G, *flow, *capacity);
+
+      //bfs for distances on the residual graph
+      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
+
+      //F will contain the physical copy of the residual graph
+      //with the set of edges which areon shortest paths
+      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);
+
+      while ( !bfs.finished() ) { 
+        AugOutEdgeIt e=bfs;
+        if (res_graph.valid(e)) {
+          if (bfs.isBNodeNewlyReached()) {
+            dist.set(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));
+          } else {
+            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));
+            }
+          }
+        }
+        ++bfs;
+      } //computing distances from s in the residual graph
 
       bool __augment=true;

src/work/marci/dimacs.h ¶

@@ -26 +26 @@
         getline(is, str);
         break;
-//       case 't': //type
-//      getline(is, str);
-//      break;
       case 'p': //problem definition
         is >> problem >> n >> m;

src/work/marci/edmonds_karp_demo.cc ¶

@@ -35 +35 @@
   typedef ListGraph MutableGraph;
 
-//  typedef SmartGraph Graph;
-  typedef ListGraph Graph;
+  typedef SmartGraph Graph;
+  //typedef ListGraph Graph;
   typedef Graph::Node Node;
   typedef Graph::EdgeIt EdgeIt;
@@ -115 +115 @@
 
   {
+    std::cout << "SmartGraph..." << std::endl;
+    std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
+    Graph::EdgeMap<int> flow(G); //0 flow
+
+    Timer ts;
+    ts.reset();
+
+    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
+    //max_flow_test.augmentWithBlockingFlow<Graph>();
+    int i=0;
+    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 
+//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
+//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+//     }
+//     std::cout<<std::endl;
+      ++i; 
+    }
+
+//   std::cout << "maximum flow: "<< std::endl;
+//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
+//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+//   }
+//   std::cout<<std::endl;
+    std::cout << "elapsed time: " << ts << std::endl;
+    std::cout << "number of augmentation phases: " << i << std::endl; 
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+  }
+
+  {
     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
     Graph::EdgeMap<int> flow(G); //0 flow