# HG changeset patch
# User marci
# Date 1083255903 0
# Node ID cfe5507617458d6af77d7d3c13bc08f72ccf58d8
# Parent  5fa75db9ebb4f192c6e5f3f1c9e888887b8efac0
preflow, maxflow

diff -r 5fa75db9ebb4 -r cfe550761745 src/work/jacint/preflow.h
--- a/src/work/jacint/preflow.h	Thu Apr 29 16:08:16 2004 +0000
+++ b/src/work/jacint/preflow.h	Thu Apr 29 16:25:03 2004 +0000
@@ -55,7 +55,7 @@
   template <typename Graph, typename Num, 
 	    typename CapMap=typename Graph::template EdgeMap<Num>, 
             typename FlowMap=typename Graph::template EdgeMap<Num> >
-  class Preflow {
+  class MaxFlow {
     
     typedef typename Graph::Node Node;
     typedef typename Graph::NodeIt NodeIt;
@@ -92,7 +92,7 @@
       PREFLOW=2
     };
 
-    Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 
+    MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 
 	    FlowMap& _flow) :
       g(&_G), s(_s), t(_t), capacity(&_capacity), 
       flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
@@ -535,7 +535,7 @@
 
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe ) 
+  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe ) 
   {
       
       int heur0=(int)(H0*n);  //time while running 'bound decrease' 
@@ -644,7 +644,7 @@
 
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase1() 
+  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1() 
   {
       
       int k=n-2;  //bound on the highest level under n containing a node
@@ -708,7 +708,7 @@
 
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath() 
+  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath() 
   {
       ResGW res_graph(*g, *capacity, *flow);
       bool _augment=false;
@@ -764,7 +764,7 @@
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
   template<typename MutableGraph> 
-  bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow() 
+  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow() 
   {      
       typedef MutableGraph MG;
       bool _augment=false;
@@ -881,7 +881,7 @@
 
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2() 
+  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2() 
   {
       bool _augment=false;
 
diff -r 5fa75db9ebb4 -r cfe550761745 src/work/marci/bipartite_graph_wrapper_test.cc
--- a/src/work/marci/bipartite_graph_wrapper_test.cc	Thu Apr 29 16:08:16 2004 +0000
+++ b/src/work/marci/bipartite_graph_wrapper_test.cc	Thu Apr 29 16:25:03 2004 +0000
@@ -11,7 +11,7 @@
 #include <bfs_iterator.h>
 #include <graph_wrapper.h>
 #include <maps.h>
-#include <edmonds_karp.h>
+#include <preflow.h>
 
 using namespace hugo;
 
diff -r 5fa75db9ebb4 -r cfe550761745 src/work/marci/bipartite_matching_try.cc
--- a/src/work/marci/bipartite_matching_try.cc	Thu Apr 29 16:08:16 2004 +0000
+++ b/src/work/marci/bipartite_matching_try.cc	Thu Apr 29 16:25:03 2004 +0000
@@ -12,7 +12,6 @@
 #include <bfs_iterator.h>
 #include <graph_wrapper.h>
 #include <maps.h>
-#include <edmonds_karp.h>
 #include <preflow.h>
 
 /**
@@ -180,7 +179,7 @@
 
   ts.reset();
   stGW::EdgeMap<int> pre_flow(stgw);
-  Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
+  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
     pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow/*, true*/);
   pre_flow_test.run();
   std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl;
diff -r 5fa75db9ebb4 -r cfe550761745 src/work/marci/lg_vs_sg.cc
--- a/src/work/marci/lg_vs_sg.cc	Thu Apr 29 16:08:16 2004 +0000
+++ b/src/work/marci/lg_vs_sg.cc	Thu Apr 29 16:25:03 2004 +0000
@@ -6,7 +6,6 @@
 #include <list_graph.h>
 #include <smart_graph.h>
 #include <dimacs.h>
-#include <edmonds_karp.h>
 #include <preflow.h>
 #include <time_measure.h>
 #include <for_each_macros.h>
@@ -34,19 +33,17 @@
 
     Timer ts;
     Graph::EdgeMap<int> flow(G); //0 flow
-    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-      pre_flow_test(G, s, t, cap, flow/*, true*/);
     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-      max_flow_test(G, s, t, cap, flow);
+      max_flow_test(G, s, t, cap, flow/*, true*/);
 
     std::cout << "ListGraph ..." << std::endl;
 
     {
       std::cout << "preflow ..." << std::endl;
       ts.reset();
-      pre_flow_test.run();
+      max_flow_test.run();
       std::cout << "elapsed time: " << ts << std::endl;
-      std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     }
 
     {
@@ -60,16 +57,16 @@
       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     }
 
-    {
-      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
-      ts.reset();
-      int i=0;
-      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
-      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 << "faster physical blocking flow augmentation ..." << std::endl;
+//       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+//       ts.reset();
+//       int i=0;
+//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
+//       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 << "on-the-fly blocking flow augmentation ..." << std::endl;
@@ -108,10 +105,10 @@
 
     Timer ts;
     Graph::EdgeMap<int> flow(G); //0 flow
-    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-      pre_flow_test(G, s, t, cap, flow/*, true*/);
     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-      max_flow_test(G, s, t, cap, flow);
+      max_flow_test(G, s, t, cap, flow/*, true*/);
+    //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
+    //  max_flow_test(G, s, t, cap, flow);
 
     std::cout << "SmatrGraph ..." << std::endl;
 
@@ -119,9 +116,9 @@
       std::cout << "preflow ..." << std::endl;
       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
       ts.reset();
-      pre_flow_test.run();
+      max_flow_test.run();
       std::cout << "elapsed time: " << ts << std::endl;
-      std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     }
 
     {
@@ -135,16 +132,16 @@
       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     }
 
-    {
-      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
-      ts.reset();
-      int i=0;
-      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
-      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 << "faster physical blocking flow augmentation ..." << std::endl;
+//       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+//       ts.reset();
+//       int i=0;
+//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
+//       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 << "on-the-fly blocking flow augmentation ..." << std::endl;
diff -r 5fa75db9ebb4 -r cfe550761745 src/work/marci/makefile
--- a/src/work/marci/makefile	Thu Apr 29 16:08:16 2004 +0000
+++ b/src/work/marci/makefile	Thu Apr 29 16:25:03 2004 +0000
@@ -4,7 +4,7 @@
 INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
 
 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
-BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try
+BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try
 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
 
 include ../makefile
diff -r 5fa75db9ebb4 -r cfe550761745 src/work/marci/max_flow_demo.cc
--- a/src/work/marci/max_flow_demo.cc	Thu Apr 29 16:08:16 2004 +0000
+++ b/src/work/marci/max_flow_demo.cc	Thu Apr 29 16:25:03 2004 +0000
@@ -5,7 +5,6 @@
 #include <list_graph.h>
 #include <smart_graph.h>
 #include <dimacs.h>
-//#include <edmonds_karp.h>
 #include <time_measure.h>
 //#include <graph_wrapper.h>
 #include <preflow.h>
@@ -70,30 +69,24 @@
   readDimacsMaxFlow(std::cin, G, s, t, cap);
   Timer ts;
   Graph::EdgeMap<int> flow(G); //0 flow
-  Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-    pre_flow_test(G, s, t, cap, flow/*, true*/);
-  //  Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-  //  pre_flow_ize(G, s, t, cap, flow/*, false*/);
-//   PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-//     pre_flow_res(G, s, t, cap, flow/*, true*/);
-  //MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-  //  max_flow_test(G, s, t, cap, flow);
+  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
+    max_flow_test(G, s, t, cap, flow);
 
   {
     std::cout << "preflow ..." << std::endl;
     ts.reset();
-    pre_flow_test.run();
+    max_flow_test.run();
     std::cout << "elapsed time: " << ts << std::endl;
-    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   }
 
   {
     std::cout << "preflow ..." << std::endl;
     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     ts.reset();
-    pre_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
+    max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
     std::cout << "elapsed time: " << ts << std::endl;
-    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   }
 
 //   {
@@ -110,10 +103,10 @@
     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     ts.reset();
     int i=0;
-    while (pre_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
+    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
     std::cout << "elapsed time: " << ts << std::endl;
     std::cout << "number of augmentation phases: " << i << std::endl; 
-    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   }
 
 //   {
@@ -132,10 +125,10 @@
     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     ts.reset();
     int i=0;
-    while (pre_flow_test.augmentOnBlockingFlow2()) { ++i; }
+    while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
     std::cout << "elapsed time: " << ts << std::endl;
     std::cout << "number of augmentation phases: " << i << std::endl; 
-    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   }
 
   {
@@ -143,10 +136,10 @@
     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     ts.reset();
     int i=0;
-    while (pre_flow_test.augmentOnShortestPath()) { ++i; }
+    while (max_flow_test.augmentOnShortestPath()) { ++i; }
     std::cout << "elapsed time: " << ts << std::endl;
     std::cout << "number of augmentation phases: " << i << std::endl; 
-    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   }