1.1 --- a/src/work/jacint/preflow.h	Thu Apr 29 16:08:16 2004 +0000
     1.2 +++ b/src/work/jacint/preflow.h	Thu Apr 29 16:25:03 2004 +0000
     1.3 @@ -55,7 +55,7 @@
     1.4    template <typename Graph, typename Num, 
     1.5  	    typename CapMap=typename Graph::template EdgeMap<Num>, 
     1.6              typename FlowMap=typename Graph::template EdgeMap<Num> >
     1.7 -  class Preflow {
     1.8 +  class MaxFlow {
     1.9      
    1.10      typedef typename Graph::Node Node;
    1.11      typedef typename Graph::NodeIt NodeIt;
    1.12 @@ -92,7 +92,7 @@
    1.13        PREFLOW=2
    1.14      };
    1.15  
    1.16 -    Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 
    1.17 +    MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 
    1.18  	    FlowMap& _flow) :
    1.19        g(&_G), s(_s), t(_t), capacity(&_capacity), 
    1.20        flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
    1.21 @@ -535,7 +535,7 @@
    1.22  
    1.23  
    1.24    template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    1.25 -  void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe ) 
    1.26 +  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe ) 
    1.27    {
    1.28        
    1.29        int heur0=(int)(H0*n);  //time while running 'bound decrease' 
    1.30 @@ -644,7 +644,7 @@
    1.31  
    1.32  
    1.33    template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    1.34 -  void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase1() 
    1.35 +  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1() 
    1.36    {
    1.37        
    1.38        int k=n-2;  //bound on the highest level under n containing a node
    1.39 @@ -708,7 +708,7 @@
    1.40  
    1.41  
    1.42    template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    1.43 -  bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath() 
    1.44 +  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath() 
    1.45    {
    1.46        ResGW res_graph(*g, *capacity, *flow);
    1.47        bool _augment=false;
    1.48 @@ -764,7 +764,7 @@
    1.49  
    1.50    template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    1.51    template<typename MutableGraph> 
    1.52 -  bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow() 
    1.53 +  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow() 
    1.54    {      
    1.55        typedef MutableGraph MG;
    1.56        bool _augment=false;
    1.57 @@ -881,7 +881,7 @@
    1.58  
    1.59  
    1.60    template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    1.61 -  bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2() 
    1.62 +  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2() 
    1.63    {
    1.64        bool _augment=false;
    1.65  

     2.1 --- a/src/work/marci/bipartite_graph_wrapper_test.cc	Thu Apr 29 16:08:16 2004 +0000
     2.2 +++ b/src/work/marci/bipartite_graph_wrapper_test.cc	Thu Apr 29 16:25:03 2004 +0000
     2.3 @@ -11,7 +11,7 @@
     2.4  #include <bfs_iterator.h>
     2.5  #include <graph_wrapper.h>
     2.6  #include <maps.h>
     2.7 -#include <edmonds_karp.h>
     2.8 +#include <preflow.h>
     2.9  
    2.10  using namespace hugo;
    2.11  

     3.1 --- a/src/work/marci/bipartite_matching_try.cc	Thu Apr 29 16:08:16 2004 +0000
     3.2 +++ b/src/work/marci/bipartite_matching_try.cc	Thu Apr 29 16:25:03 2004 +0000
     3.3 @@ -12,7 +12,6 @@
     3.4  #include <bfs_iterator.h>
     3.5  #include <graph_wrapper.h>
     3.6  #include <maps.h>
     3.7 -#include <edmonds_karp.h>
     3.8  #include <preflow.h>
     3.9  
    3.10  /**
    3.11 @@ -180,7 +179,7 @@
    3.12  
    3.13    ts.reset();
    3.14    stGW::EdgeMap<int> pre_flow(stgw);
    3.15 -  Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    3.16 +  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    3.17      pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow/*, true*/);
    3.18    pre_flow_test.run();
    3.19    std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl;

     4.1 --- a/src/work/marci/lg_vs_sg.cc	Thu Apr 29 16:08:16 2004 +0000
     4.2 +++ b/src/work/marci/lg_vs_sg.cc	Thu Apr 29 16:25:03 2004 +0000
     4.3 @@ -6,7 +6,6 @@
     4.4  #include <list_graph.h>
     4.5  #include <smart_graph.h>
     4.6  #include <dimacs.h>
     4.7 -#include <edmonds_karp.h>
     4.8  #include <preflow.h>
     4.9  #include <time_measure.h>
    4.10  #include <for_each_macros.h>
    4.11 @@ -34,19 +33,17 @@
    4.12  
    4.13      Timer ts;
    4.14      Graph::EdgeMap<int> flow(G); //0 flow
    4.15 -    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    4.16 -      pre_flow_test(G, s, t, cap, flow/*, true*/);
    4.17      MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    4.18 -      max_flow_test(G, s, t, cap, flow);
    4.19 +      max_flow_test(G, s, t, cap, flow/*, true*/);
    4.20  
    4.21      std::cout << "ListGraph ..." << std::endl;
    4.22  
    4.23      {
    4.24        std::cout << "preflow ..." << std::endl;
    4.25        ts.reset();
    4.26 -      pre_flow_test.run();
    4.27 +      max_flow_test.run();
    4.28        std::cout << "elapsed time: " << ts << std::endl;
    4.29 -      std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
    4.30 +      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    4.31      }
    4.32  
    4.33      {
    4.34 @@ -60,16 +57,16 @@
    4.35        std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    4.36      }
    4.37  
    4.38 -    {
    4.39 -      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    4.40 -      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    4.41 -      ts.reset();
    4.42 -      int i=0;
    4.43 -      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    4.44 -      std::cout << "elapsed time: " << ts << std::endl;
    4.45 -      std::cout << "number of augmentation phases: " << i << std::endl; 
    4.46 -      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    4.47 -    }
    4.48 +//     {
    4.49 +//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    4.50 +//       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    4.51 +//       ts.reset();
    4.52 +//       int i=0;
    4.53 +//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    4.54 +//       std::cout << "elapsed time: " << ts << std::endl;
    4.55 +//       std::cout << "number of augmentation phases: " << i << std::endl; 
    4.56 +//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    4.57 +//     }
    4.58  
    4.59      {
    4.60        std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    4.61 @@ -108,10 +105,10 @@
    4.62  
    4.63      Timer ts;
    4.64      Graph::EdgeMap<int> flow(G); //0 flow
    4.65 -    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    4.66 -      pre_flow_test(G, s, t, cap, flow/*, true*/);
    4.67      MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    4.68 -      max_flow_test(G, s, t, cap, flow);
    4.69 +      max_flow_test(G, s, t, cap, flow/*, true*/);
    4.70 +    //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    4.71 +    //  max_flow_test(G, s, t, cap, flow);
    4.72  
    4.73      std::cout << "SmatrGraph ..." << std::endl;
    4.74  
    4.75 @@ -119,9 +116,9 @@
    4.76        std::cout << "preflow ..." << std::endl;
    4.77        FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    4.78        ts.reset();
    4.79 -      pre_flow_test.run();
    4.80 +      max_flow_test.run();
    4.81        std::cout << "elapsed time: " << ts << std::endl;
    4.82 -      std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
    4.83 +      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    4.84      }
    4.85  
    4.86      {
    4.87 @@ -135,16 +132,16 @@
    4.88        std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    4.89      }
    4.90  
    4.91 -    {
    4.92 -      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    4.93 -      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    4.94 -      ts.reset();
    4.95 -      int i=0;
    4.96 -      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    4.97 -      std::cout << "elapsed time: " << ts << std::endl;
    4.98 -      std::cout << "number of augmentation phases: " << i << std::endl; 
    4.99 -      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   4.100 -    }
   4.101 +//     {
   4.102 +//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
   4.103 +//       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   4.104 +//       ts.reset();
   4.105 +//       int i=0;
   4.106 +//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
   4.107 +//       std::cout << "elapsed time: " << ts << std::endl;
   4.108 +//       std::cout << "number of augmentation phases: " << i << std::endl; 
   4.109 +//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   4.110 +//     }
   4.111  
   4.112      {
   4.113        std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;

     5.1 --- a/src/work/marci/makefile	Thu Apr 29 16:08:16 2004 +0000
     5.2 +++ b/src/work/marci/makefile	Thu Apr 29 16:25:03 2004 +0000
     5.3 @@ -4,7 +4,7 @@
     5.4  INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
     5.5  
     5.6  LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
     5.7 -BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try
     5.8 +BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try
     5.9  #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
    5.10  
    5.11  include ../makefile

     6.1 --- a/src/work/marci/max_flow_demo.cc	Thu Apr 29 16:08:16 2004 +0000
     6.2 +++ b/src/work/marci/max_flow_demo.cc	Thu Apr 29 16:25:03 2004 +0000
     6.3 @@ -5,7 +5,6 @@
     6.4  #include <list_graph.h>
     6.5  #include <smart_graph.h>
     6.6  #include <dimacs.h>
     6.7 -//#include <edmonds_karp.h>
     6.8  #include <time_measure.h>
     6.9  //#include <graph_wrapper.h>
    6.10  #include <preflow.h>
    6.11 @@ -70,30 +69,24 @@
    6.12    readDimacsMaxFlow(std::cin, G, s, t, cap);
    6.13    Timer ts;
    6.14    Graph::EdgeMap<int> flow(G); //0 flow
    6.15 -  Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    6.16 -    pre_flow_test(G, s, t, cap, flow/*, true*/);
    6.17 -  //  Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    6.18 -  //  pre_flow_ize(G, s, t, cap, flow/*, false*/);
    6.19 -//   PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    6.20 -//     pre_flow_res(G, s, t, cap, flow/*, true*/);
    6.21 -  //MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    6.22 -  //  max_flow_test(G, s, t, cap, flow);
    6.23 +  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    6.24 +    max_flow_test(G, s, t, cap, flow);
    6.25  
    6.26    {
    6.27      std::cout << "preflow ..." << std::endl;
    6.28      ts.reset();
    6.29 -    pre_flow_test.run();
    6.30 +    max_flow_test.run();
    6.31      std::cout << "elapsed time: " << ts << std::endl;
    6.32 -    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
    6.33 +    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    6.34    }
    6.35  
    6.36    {
    6.37      std::cout << "preflow ..." << std::endl;
    6.38      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    6.39      ts.reset();
    6.40 -    pre_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
    6.41 +    max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
    6.42      std::cout << "elapsed time: " << ts << std::endl;
    6.43 -    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
    6.44 +    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    6.45    }
    6.46  
    6.47  //   {
    6.48 @@ -110,10 +103,10 @@
    6.49      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    6.50      ts.reset();
    6.51      int i=0;
    6.52 -    while (pre_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
    6.53 +    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
    6.54      std::cout << "elapsed time: " << ts << std::endl;
    6.55      std::cout << "number of augmentation phases: " << i << std::endl; 
    6.56 -    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
    6.57 +    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    6.58    }
    6.59  
    6.60  //   {
    6.61 @@ -132,10 +125,10 @@
    6.62      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    6.63      ts.reset();
    6.64      int i=0;
    6.65 -    while (pre_flow_test.augmentOnBlockingFlow2()) { ++i; }
    6.66 +    while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
    6.67      std::cout << "elapsed time: " << ts << std::endl;
    6.68      std::cout << "number of augmentation phases: " << i << std::endl; 
    6.69 -    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
    6.70 +    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    6.71    }
    6.72  
    6.73    {
    6.74 @@ -143,10 +136,10 @@
    6.75      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    6.76      ts.reset();
    6.77      int i=0;
    6.78 -    while (pre_flow_test.augmentOnShortestPath()) { ++i; }
    6.79 +    while (max_flow_test.augmentOnShortestPath()) { ++i; }
    6.80      std::cout << "elapsed time: " << ts << std::endl;
    6.81      std::cout << "number of augmentation phases: " << i << std::endl; 
    6.82 -    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
    6.83 +    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    6.84    }
    6.85  
    6.86