Changeset 715:665689d86225 in lemon-0.x for src

Timestamp:

07/20/04 16:31:24 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

trying if without stl stack we are faster

Location:

src/work/jacint

Files:

• makefile (modified) (1 diff)
• max_flow_test.cc (modified) (7 diffs)

src/work/jacint/makefile

@@ -1 @@
-BINARIES = max_matching
-INCLUDEDIRS= -I../../include -I.. -I../{klao,marci,jacint,alpar,johanna,akos}
+BINARIES = max_flow_test
+INCLUDEDIRS= -I../../include -I../.. -I.. -I../{klao,marci,jacint,alpar,johanna,akos}
 include ../makefile 

src/work/jacint/max_flow_test.cc

@@ -1 +1 @@
 #include <iostream>
 
-#include <list_graph.h>
-#include <dimacs.h>
+#include <hugo/list_graph.h>
+#include <hugo/dimacs.h>
 #include <max_flow.h>
-#include <time_measure.h>
+#include <max_flow_no_stack.h>
+#include <hugo/time_measure.h>
 
 using namespace hugo;
@@ -26 +27 @@
            << std::endl<<std::endl;
 
-  Graph::EdgeMap<int> flow(G,0);
-  MaxFlow<Graph, int> max_flow_test(G, s, t, cap, flow);
+  Graph::EdgeMap<int> flowstack(G,0);
+  MaxFlow<Graph, int> max_flow_test(G, s, t, cap, flowstack);
   ts.reset();
   max_flow_test.run();
-  std::cout << "Elapsed time of run(): " << std::endl 
+  std::cout << "Elapsed time of run() with stl stack: " << std::endl 
+            <<ts << std::endl;
+
+  Graph::EdgeMap<int> flow(G,0);
+  MaxFlowNoStack<Graph, int> max_flow_test_no_stack(G, s, t, cap, flow);
+  ts.reset();
+  max_flow_test_no_stack.run();
+  std::cout << "Elapsed time of run() without stack: " << std::endl 
             <<ts << std::endl;
   
   Graph::NodeMap<bool> mincut(G);
-  max_flow_test.minMinCut(mincut); 
+  max_flow_test_no_stack.minMinCut(mincut); 
   int min_min_cut_value=0;
   EdgeIt e;
@@ -42 +50 @@
 
   Graph::NodeMap<bool> cut(G);
-  max_flow_test.minCut(cut); 
+  max_flow_test_no_stack.minCut(cut); 
   int min_cut_value=0;
   for(G.first(e); G.valid(e); G.next(e)) {
@@ -50 +58 @@
 
   Graph::NodeMap<bool> maxcut(G);
-  max_flow_test.maxMinCut(maxcut); 
+  max_flow_test_no_stack.maxMinCut(maxcut); 
   int max_min_cut_value=0;
   for(G.first(e); G.valid(e); G.next(e)) {
@@ -57 +65 @@
       }
 
-  std::cout << "\n Checking the result: " <<std::endl;  
-  std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl;
+  std::cout << "\n Checking the result without stack: " <<std::endl;  
+  std::cout << "Flow value: "<< max_flow_test_no_stack.flowValue() << std::endl;
   std::cout << "Min cut value: "<< min_cut_value << std::endl;
   std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
@@ -64 +72 @@
     std::endl;
 
-  if ( max_flow_test.flowValue() == min_cut_value &&
+  if ( max_flow_test_no_stack.flowValue() == min_cut_value &&
        min_cut_value == min_min_cut_value &&
        min_min_cut_value == max_min_cut_value )
     std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";  
 
-
+  /*
 
   Graph::EdgeMap<int> flow2(G,0);
@@ -153 +161 @@
        min_min_cut_value3 == max_min_cut_value3 )
     std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";  
+  */
   
   return 0;