Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/jacint/max_flow_test.cc
changeset 727 aada518af30f
parent 588 510cf257e6f2
child 757 8680351d0c28
equal deleted inserted replaced
0:8ba92fd458b7 1:25fd33fb14ad 
     1 #include <iostream>
 
     1 #include <iostream>
 
     2 
     2 
     3 #include <list_graph.h>
 
     3 #include <hugo/list_graph.h>
 
     4 #include <dimacs.h>
 
     4 #include <hugo/dimacs.h>
 
     5 #include <max_flow.h>
 
     5 #include <max_flow.h>
 
     6 #include <time_measure.h>
 
     6 #include <max_flow_no_stack.h>
 
       
     7 #include <hugo/time_measure.h>
 
     7 
     8 
     8 using namespace hugo;
 
     9 using namespace hugo;
 
     9 
    10 
    10 int main(int, char **) {
 
    11 int main(int, char **) {
 
    11  
    12  
    23   std::cout <<
 
    24   std::cout <<
 
    24     "\n  Running max_flow.h on a graph with " << 
    25     "\n  Running max_flow.h on a graph with " << 
    25     G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
 
    26     G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
 
    26 	   << std::endl<<std::endl;
 
    27 	   << std::endl<<std::endl;
 
    27 
    28 
    28   Graph::EdgeMap<int> flow(G,0);
 
    29   Graph::EdgeMap<int> flowstack(G,0);
 
    29   MaxFlow<Graph, int> max_flow_test(G, s, t, cap, flow);
 
    30   MaxFlow<Graph, int> max_flow_test(G, s, t, cap, flowstack);
 
    30   ts.reset();
 
    31   ts.reset();
 
    31   max_flow_test.run();
 
    32   max_flow_test.run();
 
    32   std::cout << "Elapsed time of run(): " << std::endl 
    33   std::cout << "Elapsed time of run() with stl stack: " << std::endl 
       
    34 	    <<ts << std::endl;
 
       
    35 
       
    36   Graph::EdgeMap<int> flow(G,0);
 
       
    37   MaxFlowNoStack<Graph, int> max_flow_test_no_stack(G, s, t, cap, flow);
 
       
    38   ts.reset();
 
       
    39   max_flow_test_no_stack.run();
 
       
    40   std::cout << "Elapsed time of run() without stack: " << std::endl 
    33 	    <<ts << std::endl;
 
    41 	    <<ts << std::endl;
 
    34   
    42   
    35   Graph::NodeMap<bool> mincut(G);
 
    43   Graph::NodeMap<bool> mincut(G);
 
    36   max_flow_test.minMinCut(mincut); 
    44   max_flow_test_no_stack.minMinCut(mincut); 
    37   int min_min_cut_value=0;
 
    45   int min_min_cut_value=0;
 
    38   EdgeIt e;
 
    46   EdgeIt e;
 
    39   for(G.first(e); G.valid(e); G.next(e)) {
 
    47   for(G.first(e); G.valid(e); G.next(e)) {
 
    40     if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];
 
    48     if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];
 
    41   }
 
    49   }
 
    42 
    50 
    43   Graph::NodeMap<bool> cut(G);
 
    51   Graph::NodeMap<bool> cut(G);
 
    44   max_flow_test.minCut(cut); 
    52   max_flow_test_no_stack.minCut(cut); 
    45   int min_cut_value=0;
 
    53   int min_cut_value=0;
 
    46   for(G.first(e); G.valid(e); G.next(e)) {
 
    54   for(G.first(e); G.valid(e); G.next(e)) {
 
    47     if (cut[G.tail(e)] && !cut[G.head(e)]) 
    55     if (cut[G.tail(e)] && !cut[G.head(e)]) 
    48       min_cut_value+=cap[e];
 
    56       min_cut_value+=cap[e];
 
    49   }
 
    57   }
 
    50 
    58 
    51   Graph::NodeMap<bool> maxcut(G);
 
    59   Graph::NodeMap<bool> maxcut(G);
 
    52   max_flow_test.maxMinCut(maxcut); 
    60   max_flow_test_no_stack.maxMinCut(maxcut); 
    53   int max_min_cut_value=0;
 
    61   int max_min_cut_value=0;
 
    54   for(G.first(e); G.valid(e); G.next(e)) {
 
    62   for(G.first(e); G.valid(e); G.next(e)) {
 
    55     if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) 
    63     if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) 
    56       max_min_cut_value+=cap[e];
 
    64       max_min_cut_value+=cap[e];
 
    57       }
 
    65       }
 
    58 
    66 
    59   std::cout << "\n Checking the result: " <<std::endl;  
    67   std::cout << "\n Checking the result without stack: " <<std::endl;  
    60   std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl;
 
    68   std::cout << "Flow value: "<< max_flow_test_no_stack.flowValue() << std::endl;
 
    61   std::cout << "Min cut value: "<< min_cut_value << std::endl;
 
    69   std::cout << "Min cut value: "<< min_cut_value << std::endl;
 
    62   std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
 
    70   std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
 
    63   std::cout << "Max min cut value: "<< max_min_cut_value << 
    71   std::cout << "Max min cut value: "<< max_min_cut_value << 
    64     std::endl;
 
    72     std::endl;
 
    65 
    73 
    66   if ( max_flow_test.flowValue() == min_cut_value &&
 
    74   if ( max_flow_test_no_stack.flowValue() == min_cut_value &&
 
    67        min_cut_value == min_min_cut_value &&
 
    75        min_cut_value == min_min_cut_value &&
 
    68        min_min_cut_value == max_min_cut_value )
 
    76        min_min_cut_value == max_min_cut_value )
 
    69     std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";  
    77     std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";  
    70 
    78 
    71 
    79   /*
 
    72 
    80 
    73   Graph::EdgeMap<int> flow2(G,0);
 
    81   Graph::EdgeMap<int> flow2(G,0);
 
    74   std::cout << "Calling resetFlow() " << std::endl 
    82   std::cout << "Calling resetFlow() " << std::endl 
    75 	    << ts << std::endl;
 
    83 	    << ts << std::endl;
 
    76   max_flow_test.resetFlow(flow2);  
    84   max_flow_test.resetFlow(flow2);  
   150 
   158 
   151   if ( max_flow_test3.flowValue() == min_cut_value3 &&
 
   159   if ( max_flow_test3.flowValue() == min_cut_value3 &&
 
   152        min_cut_value3 == min_min_cut_value3 &&
 
   160        min_cut_value3 == min_min_cut_value3 &&
 
   153        min_min_cut_value3 == max_min_cut_value3 )
 
   161        min_min_cut_value3 == max_min_cut_value3 )
 
   154     std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";  
   162     std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";  
       
   163   */
 
   155   
   164   
   156   return 0;
 
   165   return 0;
 
   157 }
 
   166 }
lemon-0.x