src/work/jacint/preflow.cc
changeset 1308 0274efa2222f
parent 921 818510fa3d99
equal deleted inserted replaced
9:8c60a69d110d 10:89a484ec3acf
    44   preflow_test.maxMinCut(maxcut); 
    44   preflow_test.maxMinCut(maxcut); 
    45   int max_min_cut_value=0;
    45   int max_min_cut_value=0;
    46   EdgeIt e;
    46   EdgeIt e;
    47   for(G.first(e); G.valid(e); G.next(e)) {
    47   for(G.first(e); G.valid(e); G.next(e)) {
    48     int c=cap[e];
    48     int c=cap[e];
    49     if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=c;
    49     if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=c;
    50     if (cut[G.tail(e)] && !cut[G.head(e)]) min_cut_value+=c; 
    50     if (cut[G.source(e)] && !cut[G.target(e)]) min_cut_value+=c; 
    51     if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) max_min_cut_value+=c;
    51     if (maxcut[G.source(e)] && !maxcut[G.target(e)]) max_min_cut_value+=c;
    52   }
    52   }
    53 
    53 
    54   std::cout << "\nChecking the result: " <<std::endl;  
    54   std::cout << "\nChecking the result: " <<std::endl;  
    55   std::cout << "Flow value: "<< preflow_test.flowValue() << std::endl;
    55   std::cout << "Flow value: "<< preflow_test.flowValue() << std::endl;
    56   std::cout << "Min cut value: "<< min_cut_value << std::endl;
    56   std::cout << "Min cut value: "<< min_cut_value << std::endl;
    84   Graph::NodeMap<bool> maxcut2(G);
    84   Graph::NodeMap<bool> maxcut2(G);
    85   preflow_test.maxMinCut(maxcut2); 
    85   preflow_test.maxMinCut(maxcut2); 
    86   int max_min_cut2_value=0;
    86   int max_min_cut2_value=0;
    87   for(G.first(e); G.valid(e); G.next(e)) {
    87   for(G.first(e); G.valid(e); G.next(e)) {
    88     int c=cap[e];
    88     int c=cap[e];
    89     if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut2_value+=c;
    89     if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut2_value+=c;
    90     if (cut2[G.tail(e)] && !cut2[G.head(e)]) min_cut2_value+=c; 
    90     if (cut2[G.source(e)] && !cut2[G.target(e)]) min_cut2_value+=c; 
    91     if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) max_min_cut2_value+=c;
    91     if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) max_min_cut2_value+=c;
    92   }
    92   }
    93 
    93 
    94   std::cout << "\nThe given flow value is "
    94   std::cout << "\nThe given flow value is "
    95 	    << preflow_test2.flowValue();
    95 	    << preflow_test2.flowValue();
    96 
    96 
   136   preflow_test.maxMinCut(maxcut3); 
   136   preflow_test.maxMinCut(maxcut3); 
   137   int max_min_cut3_value=0;
   137   int max_min_cut3_value=0;
   138   
   138   
   139   for(G.first(e); G.valid(e); G.next(e)) {
   139   for(G.first(e); G.valid(e); G.next(e)) {
   140     int c=cap[e];
   140     int c=cap[e];
   141     if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut3_value+=c;
   141     if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut3_value+=c;
   142     if (cut3[G.tail(e)] && !cut3[G.head(e)]) min_cut3_value+=c; 
   142     if (cut3[G.source(e)] && !cut3[G.target(e)]) min_cut3_value+=c; 
   143     if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)]) max_min_cut3_value+=c;
   143     if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) max_min_cut3_value+=c;
   144     if (actcut3[G.tail(e)] && !actcut3[G.head(e)]) act_min_cut3_value+=c;
   144     if (actcut3[G.source(e)] && !actcut3[G.target(e)]) act_min_cut3_value+=c;
   145   }
   145   }
   146 
   146 
   147  std::cout << "\nThe min cut value given by actMinCut() after phase 0 is "<<
   147  std::cout << "\nThe min cut value given by actMinCut() after phase 0 is "<<
   148    act_min_cut3_value;
   148    act_min_cut3_value;
   149 
   149 
   193   Graph::NodeMap<bool> maxcut4(G);
   193   Graph::NodeMap<bool> maxcut4(G);
   194   preflow_test4.maxMinCut(maxcut4); 
   194   preflow_test4.maxMinCut(maxcut4); 
   195   int max_min_cut4_value=0;
   195   int max_min_cut4_value=0;
   196   for(G.first(e); G.valid(e); G.next(e)) {
   196   for(G.first(e); G.valid(e); G.next(e)) {
   197     int c=cap[e];
   197     int c=cap[e];
   198     if (mincut4[G.tail(e)] && !mincut4[G.head(e)]) min_min_cut4_value+=c;
   198     if (mincut4[G.source(e)] && !mincut4[G.target(e)]) min_min_cut4_value+=c;
   199     if (cut4[G.tail(e)] && !cut4[G.head(e)]) min_cut4_value+=c; 
   199     if (cut4[G.source(e)] && !cut4[G.target(e)]) min_cut4_value+=c; 
   200     if (maxcut4[G.tail(e)] && !maxcut4[G.head(e)]) max_min_cut4_value+=c;
   200     if (maxcut4[G.source(e)] && !maxcut4[G.target(e)]) max_min_cut4_value+=c;
   201   }
   201   }
   202 
   202 
   203   std::cout << "\nThe given flow value is "
   203   std::cout << "\nThe given flow value is "
   204 	    << preflow_test4.flowValue();
   204 	    << preflow_test4.flowValue();
   205   
   205   
   236   Graph::NodeMap<bool> maxcut5(G);
   236   Graph::NodeMap<bool> maxcut5(G);
   237   preflow_test4.maxMinCut(maxcut5); 
   237   preflow_test4.maxMinCut(maxcut5); 
   238   int max_min_cut5_value=0;
   238   int max_min_cut5_value=0;
   239   for(G.first(e); G.valid(e); G.next(e)) {
   239   for(G.first(e); G.valid(e); G.next(e)) {
   240     int c=cap[e];
   240     int c=cap[e];
   241     if (mincut5[G.tail(e)] && !mincut5[G.head(e)]) min_min_cut5_value+=c;
   241     if (mincut5[G.source(e)] && !mincut5[G.target(e)]) min_min_cut5_value+=c;
   242     if (cut5[G.tail(e)] && !cut5[G.head(e)]) min_cut5_value+=c; 
   242     if (cut5[G.source(e)] && !cut5[G.target(e)]) min_cut5_value+=c; 
   243     if (maxcut5[G.tail(e)] && !maxcut5[G.head(e)]) max_min_cut5_value+=c;
   243     if (maxcut5[G.source(e)] && !maxcut5[G.target(e)]) max_min_cut5_value+=c;
   244   }
   244   }
   245 
   245 
   246   std::cout << "\nThe given flow value is "
   246   std::cout << "\nThe given flow value is "
   247 	    << preflow_test4.flowValue();
   247 	    << preflow_test4.flowValue();
   248   
   248