src/work/jacint/preflow_excess_test.cc
changeset 454 0cd33e3e60cb
child 921 818510fa3d99
equal deleted inserted replaced
-1:000000000000 0:9814c2ac76db
       
     1 /*
       
     2 The only difference between preflow.h and preflow_res.h is that the latter
       
     3 uses the ResGraphWrapper, while the first does not. (Bfs is implemented by
       
     4 hand in both.) This test program runs Preflow and PreflowRes on the same
       
     5 graph, tests the result of these implementations and writes the running time
       
     6 of them.  */
       
     7 #include <iostream>
       
     8 
       
     9 #include <smart_graph.h>
       
    10 #include <dimacs.h>
       
    11 #include <preflow_excess.h>
       
    12 #include <time_measure.h>
       
    13 
       
    14 using namespace hugo;
       
    15 
       
    16 int main(int, char **) {
       
    17  
       
    18   typedef SmartGraph Graph;
       
    19   
       
    20   typedef Graph::Node Node;
       
    21   typedef Graph::EdgeIt EdgeIt;
       
    22 
       
    23   Graph G;
       
    24   Node s, t;
       
    25   Graph::EdgeMap<int> cap(G);
       
    26   readDimacsMaxFlow(std::cin, G, s, t, cap);
       
    27   Timer ts;
       
    28   
       
    29   std::cout <<
       
    30     "\n  Are we slower?"
       
    31 	    <<std::endl;
       
    32   std::cout <<
       
    33     "\n  Running preflow.h on a graph with " << 
       
    34     G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
       
    35 	   << std::endl<<std::endl;
       
    36 
       
    37 
       
    38 
       
    39 
       
    40 
       
    41 
       
    42   
       
    43   Graph::EdgeMap<int> flow(G,0);
       
    44   Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 0 , 0);
       
    45   ts.reset();
       
    46   max_flow_test.run();
       
    47   std::cout << "Elapsed time from a preflow: " << std::endl 
       
    48 	    <<ts << std::endl;
       
    49   
       
    50   Graph::NodeMap<bool> mincut(G);
       
    51   max_flow_test.minMinCut(mincut); 
       
    52   int min_min_cut_value=0;
       
    53   EdgeIt e;
       
    54   for(G.first(e); G.valid(e); G.next(e)) {
       
    55     if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];
       
    56   }
       
    57 
       
    58   Graph::NodeMap<bool> cut(G);
       
    59   max_flow_test.minCut(cut); 
       
    60   int min_cut_value=0;
       
    61   for(G.first(e); G.valid(e); G.next(e)) {
       
    62     if (cut[G.tail(e)] && !cut[G.head(e)]) 
       
    63       min_cut_value+=cap[e];
       
    64   }
       
    65 
       
    66   Graph::NodeMap<bool> maxcut(G);
       
    67   max_flow_test.maxMinCut(maxcut); 
       
    68   int max_min_cut_value=0;
       
    69   for(G.first(e); G.valid(e); G.next(e)) {
       
    70     if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) 
       
    71       max_min_cut_value+=cap[e];
       
    72       }
       
    73 
       
    74   std::cout << "\n Checking the result: " <<std::endl;  
       
    75   std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl;
       
    76   std::cout << "Min cut value: "<< min_cut_value << std::endl;
       
    77   std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
       
    78   std::cout << "Max min cut value: "<< max_min_cut_value << 
       
    79     std::endl;
       
    80 
       
    81   if ( max_flow_test.flowValue() == min_cut_value &&
       
    82        min_cut_value == min_min_cut_value &&
       
    83        min_min_cut_value == max_min_cut_value )
       
    84     std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";  
       
    85 
       
    86 
       
    87 
       
    88 
       
    89 
       
    90   
       
    91   Graph::EdgeMap<int> flow2(G,0);
       
    92   Preflow<Graph, int> max_flow_test2(G, s, t, cap, flow2, 0 , 1);
       
    93   ts.reset();
       
    94   max_flow_test2.run();
       
    95   std::cout << "Elapsed time from a flow: " << std::endl 
       
    96 	    << ts << std::endl;
       
    97   
       
    98   Graph::NodeMap<bool> mincut2(G);
       
    99   max_flow_test2.minMinCut(mincut2); 
       
   100   int min_min_cut_value2=0;
       
   101     for(G.first(e); G.valid(e); G.next(e)) {
       
   102     if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e];
       
   103   }
       
   104 
       
   105   Graph::NodeMap<bool> cut2(G);
       
   106   max_flow_test2.minCut(cut2); 
       
   107   int min_cut_value2=0;
       
   108   for(G.first(e); G.valid(e); G.next(e)) {
       
   109     if (cut2[G.tail(e)] && !cut2[G.head(e)]) 
       
   110       min_cut_value2+=cap[e];
       
   111   }
       
   112 
       
   113   Graph::NodeMap<bool> maxcut2(G);
       
   114   max_flow_test2.maxMinCut(maxcut2); 
       
   115   int max_min_cut_value2=0;
       
   116   for(G.first(e); G.valid(e); G.next(e)) {
       
   117     if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) 
       
   118       max_min_cut_value2+=cap[e];
       
   119       }
       
   120   
       
   121   std::cout << "\n Checking the result: " <<std::endl;  
       
   122   std::cout << "Flow value: "<< max_flow_test2.flowValue() << std::endl;
       
   123   std::cout << "Min cut value: "<< min_cut_value2 << std::endl;
       
   124   std::cout << "Min min cut value: "<< min_min_cut_value2 << std::endl;
       
   125   std::cout << "Max min cut value: "<< max_min_cut_value2 << 
       
   126     std::endl;  
       
   127   if ( max_flow_test.flowValue() == min_cut_value &&
       
   128        min_cut_value == min_min_cut_value &&
       
   129        min_min_cut_value == max_min_cut_value )
       
   130     std::cout << "They are equal! " <<std::endl;  
       
   131 
       
   132 
       
   133 
       
   134 
       
   135 
       
   136   Graph::EdgeMap<int> flow3(G,0);
       
   137   Preflow<Graph, int> max_flow_test3(G, s, t, cap, flow3, 1 , 1);
       
   138   ts.reset();
       
   139   max_flow_test3.run();
       
   140   std::cout << "Elapsed time from a const zero flow: " << std::endl 
       
   141 	    <<ts << std::endl;
       
   142   
       
   143   Graph::NodeMap<bool> mincut3(G);
       
   144   max_flow_test3.minMinCut(mincut3); 
       
   145   int min_min_cut_value3=0;
       
   146   for(G.first(e); G.valid(e); G.next(e)) {
       
   147     if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e];
       
   148   }
       
   149 
       
   150   Graph::NodeMap<bool> cut3(G);
       
   151   max_flow_test3.minCut(cut3); 
       
   152   int min_cut_value3=0;
       
   153   for(G.first(e); G.valid(e); G.next(e)) {
       
   154     if (cut3[G.tail(e)] && !cut3[G.head(e)]) 
       
   155       min_cut_value3+=cap[e];
       
   156   }
       
   157 
       
   158   Graph::NodeMap<bool> maxcut3(G);
       
   159   max_flow_test3.maxMinCut(maxcut3); 
       
   160   int max_min_cut_value3=0;
       
   161   for(G.first(e); G.valid(e); G.next(e)) {
       
   162     if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)]) 
       
   163       max_min_cut_value3+=cap[e];
       
   164       }
       
   165 
       
   166   std::cout << "\n Checking the result: " <<std::endl;  
       
   167   std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl;
       
   168   std::cout << "Min cut value: "<< min_cut_value3 << std::endl;
       
   169   std::cout << "Min min cut value: "<< min_min_cut_value3 << std::endl;
       
   170   std::cout << "Max min cut value: "<< max_min_cut_value3 << 
       
   171     std::endl;
       
   172 
       
   173   if ( max_flow_test3.flowValue() == min_cut_value3 &&
       
   174        min_cut_value3 == min_min_cut_value3 &&
       
   175        min_min_cut_value3 == max_min_cut_value3 )
       
   176     std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";  
       
   177   
       
   178   return 0;
       
   179 }