1.1 --- a/src/work/marci/lg_vs_sg.cc	Fri May 14 18:08:29 2004 +0000
     1.2 +++ b/src/work/marci/lg_vs_sg.cc	Fri May 14 18:28:57 2004 +0000
     1.3 @@ -3,7 +3,8 @@
     1.4  #include <fstream>
     1.5  #include <string>
     1.6  
     1.7 -#include <list_graph.h>
     1.8 +#include <sage_graph.h>
     1.9 +#include <hugo/list_graph.h>
    1.10  #include <hugo/smart_graph.h>
    1.11  #include <hugo/dimacs.h>
    1.12  #include <max_flow.h>
    1.13 @@ -18,10 +19,10 @@
    1.14  int main(int, char** argv) {
    1.15  
    1.16    std::string in=argv[1];
    1.17 -  typedef ListGraph MutableGraph;
    1.18 +  typedef SageGraph MutableGraph;
    1.19  
    1.20    {
    1.21 -    typedef ListGraph Graph;
    1.22 +    typedef SageGraph Graph;
    1.23      typedef Graph::Node Node;
    1.24      typedef Graph::EdgeIt EdgeIt;
    1.25  
    1.26 @@ -37,7 +38,7 @@
    1.27      MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    1.28        max_flow_test(g, s, t, cap, flow/*, true*/);
    1.29  
    1.30 -    std::cout << "ListGraph ..." << std::endl;
    1.31 +    std::cout << "SageGraph ..." << std::endl;
    1.32  
    1.33      {
    1.34        std::cout << "preflow ..." << std::endl;
    1.35 @@ -92,7 +93,6 @@
    1.36      }
    1.37    }
    1.38  
    1.39 -
    1.40    {
    1.41      typedef SmartGraph Graph;
    1.42      typedef Graph::Node Node;
    1.43 @@ -112,7 +112,7 @@
    1.44      //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    1.45      //  max_flow_test(g, s, t, cap, flow);
    1.46  
    1.47 -    std::cout << "SmatrGraph ..." << std::endl;
    1.48 +    std::cout << "SmartGraph ..." << std::endl;
    1.49  
    1.50      {
    1.51        std::cout << "preflow ..." << std::endl;
    1.52 @@ -168,6 +168,81 @@
    1.53      }
    1.54    }
    1.55  
    1.56 +  {
    1.57 +    typedef ListGraph Graph;
    1.58 +    typedef Graph::Node Node;
    1.59 +    typedef Graph::EdgeIt EdgeIt;
    1.60 +
    1.61 +    Graph g;
    1.62 +    Node s, t;
    1.63 +    Graph::EdgeMap<int> cap(g);
    1.64 +    std::ifstream ins(in.c_str());
    1.65 +    //readDimacsMaxFlow(ins, g, s, t, cap);
    1.66 +    readDimacs(ins, g, cap, s, t);
    1.67 +
    1.68 +    Timer ts;
    1.69 +    Graph::EdgeMap<int> flow(g); //0 flow
    1.70 +    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    1.71 +      max_flow_test(g, s, t, cap, flow/*, true*/);
    1.72 +    //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    1.73 +    //  max_flow_test(g, s, t, cap, flow);
    1.74 +
    1.75 +    std::cout << "ListGraph ..." << std::endl;
    1.76 +
    1.77 +    {
    1.78 +      std::cout << "preflow ..." << std::endl;
    1.79 +      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    1.80 +      ts.reset();
    1.81 +      max_flow_test.run();
    1.82 +      std::cout << "elapsed time: " << ts << std::endl;
    1.83 +      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    1.84 +    }
    1.85 +
    1.86 +    {
    1.87 +      std::cout << "physical blocking flow augmentation ..." << std::endl;
    1.88 +      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    1.89 +      ts.reset();
    1.90 +      int i=0;
    1.91 +      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
    1.92 +      std::cout << "elapsed time: " << ts << std::endl;
    1.93 +      std::cout << "number of augmentation phases: " << i << std::endl; 
    1.94 +      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    1.95 +    }
    1.96 +
    1.97 +//     {
    1.98 +//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    1.99 +//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   1.100 +//       ts.reset();
   1.101 +//       int i=0;
   1.102 +//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
   1.103 +//       std::cout << "elapsed time: " << ts << std::endl;
   1.104 +//       std::cout << "number of augmentation phases: " << i << std::endl; 
   1.105 +//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   1.106 +//     }
   1.107 +
   1.108 +    {
   1.109 +      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
   1.110 +      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   1.111 +      ts.reset();
   1.112 +      int i=0;
   1.113 +      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
   1.114 +      std::cout << "elapsed time: " << ts << std::endl;
   1.115 +      std::cout << "number of augmentation phases: " << i << std::endl; 
   1.116 +      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   1.117 +    }
   1.118 +
   1.119 +    {
   1.120 +      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
   1.121 +      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   1.122 +      ts.reset();
   1.123 +      int i=0;
   1.124 +      while (max_flow_test.augmentOnShortestPath()) { ++i; }
   1.125 +      std::cout << "elapsed time: " << ts << std::endl;
   1.126 +      std::cout << "number of augmentation phases: " << i << std::endl; 
   1.127 +      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   1.128 +    }
   1.129 +  }
   1.130 +
   1.131  
   1.132  
   1.133