Changeset 642:e812963087f0 in lemon-0.x for src/work/marci/lg_vs_sg.cc

Timestamp:

05/14/04 20:28:57 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

To avoid confusion my old ListGraph? is can be used under name SageGraph?, work/sage_graph.h contains it.

File:

• src/work/marci/lg_vs_sg.cc (modified) (6 diffs)

src/work/marci/lg_vs_sg.cc

@@ -4 +4 @@
 #include <string>
 
-#include <list_graph.h>
+#include <sage_graph.h>
+#include <hugo/list_graph.h>
 #include <hugo/smart_graph.h>
 #include <hugo/dimacs.h>
@@ -19 +20 @@
 
   std::string in=argv[1];
-  typedef ListGraph MutableGraph;
+  typedef SageGraph MutableGraph;
 
   {
-    typedef ListGraph Graph;
+    typedef SageGraph Graph;
     typedef Graph::Node Node;
     typedef Graph::EdgeIt EdgeIt;
@@ -38 +39 @@
       max_flow_test(g, s, t, cap, flow/*, true*/);
 
-    std::cout << "ListGraph ..." << std::endl;
+    std::cout << "SageGraph ..." << std::endl;
 
     {
@@ -93 +94 @@
   }
 
-
   {
     typedef SmartGraph Graph;
@@ -113 +113 @@
     //  max_flow_test(g, s, t, cap, flow);
 
-    std::cout << "SmatrGraph ..." << std::endl;
+    std::cout << "SmartGraph ..." << std::endl;
 
     {
@@ -169 +169 @@
   }
 
+  {
+    typedef ListGraph Graph;
+    typedef Graph::Node Node;
+    typedef Graph::EdgeIt EdgeIt;
+
+    Graph g;
+    Node s, t;
+    Graph::EdgeMap<int> cap(g);
+    std::ifstream ins(in.c_str());
+    //readDimacsMaxFlow(ins, g, s, t, cap);
+    readDimacs(ins, g, cap, s, t);
+
+    Timer ts;
+    Graph::EdgeMap<int> flow(g); //0 flow
+    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
+      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 << "ListGraph ..." << std::endl;
+
+    {
+      std::cout << "preflow ..." << std::endl;
+      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      ts.reset();
+      max_flow_test.run();
+      std::cout << "elapsed time: " << ts << std::endl;
+      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+    }
+
+    {
+      std::cout << "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.augmentOnBlockingFlow<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;
+      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      ts.reset();
+      int i=0;
+      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: "<< max_flow_test.flowValue() << std::endl;
+    }
+
+    {
+      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
+      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+      ts.reset();
+      int i=0;
+      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: "<< max_flow_test.flowValue() << std::endl;
+    }
+  }
+