Changeset 642:e812963087f0 in lemon-0.x

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.

Location:

src/work

Files:

• list_graph.h (deleted)
• marci/bfsit_vs_byhand.cc (modified) (2 diffs)
• marci/bipartite_graph_wrapper_test.cc (modified) (2 diffs)
• marci/bipartite_matching_try.cc (modified) (3 diffs)
• marci/bipartite_matching_try_3.cc (modified) (2 diffs)
• marci/iterator_bfs_demo.cc (modified) (2 diffs)
• marci/lg_vs_sg.cc (modified) (6 diffs)
• marci/macro_test.cc (modified) (2 diffs)
• marci/max_bipartite_matching_demo.cc (modified) (1 diff)
• marci/max_flow_1.cc (modified) (2 diffs)
• marci/max_flow_demo.cc (modified) (2 diffs)
• marci/top_sort_test.cc (modified) (2 diffs)
• sage_graph.h (added)

src/work/marci/bfsit_vs_byhand.cc

@@ -3 +3 @@
 #include <fstream>
 
-#include <list_graph.h>
+#include <sage_graph.h>
 //#include <smart_graph.h>
 #include <hugo/dimacs.h>
@@ -13 +13 @@
 
 int main() {
-  typedef ListGraph Graph; 
+  typedef SageGraph Graph; 
   typedef Graph::Node Node;
   typedef Graph::NodeIt NodeIt;

src/work/marci/bipartite_graph_wrapper_test.cc

@@ -4 +4 @@
 #include <vector>
 
-#include <list_graph.h>
+#include <sage_graph.h>
 //#include <smart_graph.h>
 //#include <dimacs.h>
@@ -18 +18 @@
 
 int main() {
-  typedef UndirListGraph Graph; 
+  typedef UndirSageGraph Graph; 
   typedef Graph::Node Node;
   typedef Graph::NodeIt NodeIt;

src/work/marci/bipartite_matching_try.cc

@@ -5 +5 @@
 #include <cstdlib>
 
-#include <list_graph.h>
+#include <sage_graph.h>
 //#include <smart_graph.h>
 //#include <dimacs.h>
@@ -41 +41 @@
 
 int main() {
-  typedef UndirListGraph Graph; 
+  typedef UndirSageGraph Graph; 
   typedef Graph::Node Node;
   typedef Graph::NodeIt NodeIt;
@@ -167 +167 @@
     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
 //  while (max_flow_test.augmentOnShortestPath()) { }
-  typedef ListGraph MutableGraph;
+  typedef SageGraph MutableGraph;
 //  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
   while (max_flow_test.augmentOnBlockingFlow2()) {

src/work/marci/bipartite_matching_try_3.cc

@@ -4 +4 @@
 #include <vector>
 
-#include <list_graph.h>
+#include <sage_graph.h>
 //#include <smart_graph.h>
 //#include <dimacs.h>
@@ -20 +20 @@
 int main() {
   //typedef UndirListGraph Graph; 
-  typedef BipartiteGraph<ListGraph> Graph;
+  typedef BipartiteGraph<SageGraph> Graph;
   
   typedef Graph::Node Node;

src/work/marci/iterator_bfs_demo.cc

@@ -4 +4 @@
 #include <string>
 
-#include <list_graph.h>
+#include <sage_graph.h>
 //#include <smart_graph.h>
 #include <bfs_dfs.h>
@@ -30 +30 @@
 {
   //typedef SmartGraph Graph;
-  typedef ListGraph Graph;
+  typedef SageGraph Graph;
 
   typedef Graph::Node Node;

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;
+    }
+  }
+
 
 

src/work/marci/macro_test.cc

@@ -3 +3 @@
 #include <fstream>
 
-#include <list_graph.h>
+#include <sage_graph.h>
 #include <hugo/for_each_macros.h>
 
@@ -10 +10 @@
 int main() 
 {
-  typedef ListGraph Graph;
+  typedef SageGraph Graph;
   Graph g;
   Graph::Node n1=g.addNode();

src/work/marci/max_bipartite_matching_demo.cc

@@ -10 +10 @@
 
 #include <leda_graph_wrapper.h>
-#include <list_graph.h>
+#include <sage_graph.h>
 #include <dimacs.h>
 #include <time_measure.h>

src/work/marci/max_flow_1.cc

@@ -3 +3 @@
 #include <fstream>
 
-#include <list_graph.h>
+#include <sage_graph.h>
 #include <hugo/smart_graph.h>
 #include <hugo/dimacs.h>
@@ -20 +20 @@
 int main(int, char **) {
 
-  typedef ListGraph MutableGraph;
+  typedef SageGraph MutableGraph;
 
   typedef SmartGraph Graph;

src/work/marci/max_flow_demo.cc

@@ -3 +3 @@
 #include <fstream>
 
-#include <list_graph.h>
+#include <sage_graph.h>
 #include <hugo/smart_graph.h>
 #include <hugo/dimacs.h>
@@ -35 +35 @@
 int main(int, char **) {
 
-  typedef ListGraph MutableGraph;
+  typedef SageGraph MutableGraph;
 
   typedef SmartGraph Graph;
-  //  typedef ListGraph Graph;
+  //  typedef SageGraph Graph;
   typedef Graph::Node Node;
   typedef Graph::EdgeIt EdgeIt;

src/work/marci/top_sort_test.cc

@@ -6 +6 @@
 #include <hugo/dimacs.h>
 #include <bfs_dfs_misc.h>
-#include <list_graph.h>
+#include <sage_graph.h>
 #include <hugo/graph_wrapper.h>
 #include <hugo/maps.h>
@@ -17 +17 @@
 
 int main() {
-  typedef ListGraph Graph;
+  typedef SageGraph Graph;
   Graph g;
   readDimacs(std::cin, g);