# HG changeset patch
# User marci
# Date 1084559597 0
# Node ID f8053cb5104752498c60bae788f8d3eb418cc9d5
# Parent  e812963087f03434d64702ffbdff1fc997958af2
comparision of ListGraph, SmartGraph and SageGraph

diff -r e812963087f0 -r f8053cb51047 src/work/marci/lg_vs_sg.cc
--- a/src/work/marci/lg_vs_sg.cc	Fri May 14 18:28:57 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,250 +0,0 @@
-// -*- c++ -*-
-#include <iostream>
-#include <fstream>
-#include <string>
-
-#include <sage_graph.h>
-#include <hugo/list_graph.h>
-#include <hugo/smart_graph.h>
-#include <hugo/dimacs.h>
-#include <max_flow.h>
-#include <hugo/time_measure.h>
-#include <hugo/for_each_macros.h>
-
-using namespace hugo;
-
-// Use a DIMACS max flow file as stdin.
-// read_dimacs_demo dimacs_max_flow_file
-
-int main(int, char** argv) {
-
-  std::string in=argv[1];
-  typedef SageGraph MutableGraph;
-
-  {
-    typedef SageGraph 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*/);
-
-    std::cout << "SageGraph ..." << std::endl;
-
-    {
-      std::cout << "preflow ..." << std::endl;
-      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;
-    }
-  }
-
-  {
-    typedef SmartGraph 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 << "SmartGraph ..." << 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;
-    }
-  }
-
-  {
-    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;
-    }
-  }
-
-
-
-
-  return 0;
-}
diff -r e812963087f0 -r f8053cb51047 src/work/marci/lg_vs_sg_vs_sg.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci/lg_vs_sg_vs_sg.cc	Fri May 14 18:33:17 2004 +0000
@@ -0,0 +1,250 @@
+// -*- c++ -*-
+#include <iostream>
+#include <fstream>
+#include <string>
+
+#include <sage_graph.h>
+#include <hugo/list_graph.h>
+#include <hugo/smart_graph.h>
+#include <hugo/dimacs.h>
+#include <max_flow.h>
+#include <hugo/time_measure.h>
+#include <hugo/for_each_macros.h>
+
+using namespace hugo;
+
+// Use a DIMACS max flow file as stdin.
+// read_dimacs_demo dimacs_max_flow_file
+
+int main(int, char** argv) {
+
+  std::string in=argv[1];
+  typedef SageGraph MutableGraph;
+
+  {
+    typedef SageGraph 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*/);
+
+    std::cout << "SageGraph ..." << std::endl;
+
+    {
+      std::cout << "preflow ..." << std::endl;
+      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;
+    }
+  }
+
+  {
+    typedef SmartGraph 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 << "SmartGraph ..." << 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;
+    }
+  }
+
+  {
+    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;
+    }
+  }
+
+
+
+
+  return 0;
+}
diff -r e812963087f0 -r f8053cb51047 src/work/marci/makefile
--- a/src/work/marci/makefile	Fri May 14 18:28:57 2004 +0000
+++ b/src/work/marci/makefile	Fri May 14 18:33:17 2004 +0000
@@ -4,7 +4,7 @@
 INCLUDEDIRS ?= -I../.. -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
 
 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
-BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test max_flow_1
+BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test max_flow_1
 #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