Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/test/preflow_test.cc
changeset 940 50a153b08f07
parent 921 818510fa3d99
child 959 c80ef5912903
equal deleted inserted replaced
9:75e46e02a340 10:6f9cfa5b74af 
    37   typedef skeleton::ReadWriteMap<Edge,VType> FlowMap;
 
    37   typedef skeleton::ReadWriteMap<Edge,VType> FlowMap;
 
    38   typedef skeleton::ReadWriteMap<Node,bool> CutMap;
 
    38   typedef skeleton::ReadWriteMap<Node,bool> CutMap;
 
    39  
    39  
    40   typedef Preflow<Graph, int, CapMap, FlowMap> PType;
 
    40   typedef Preflow<Graph, int, CapMap, FlowMap> PType;
 
    41 
    41 
    42   Graph G;
 
    42   Graph g;
 
    43   Node n;
 
    43   Node n;
 
    44   CapMap cap;
 
    44   CapMap cap;
 
    45   FlowMap flow;
 
    45   FlowMap flow;
 
    46   CutMap cut;
 
    46   CutMap cut;
 
    47 
    47 
    48   PType preflow_test(G,n,n,cap,flow);
 
    48   PType preflow_test(g,n,n,cap,flow);
 
    49 
    49 
    50   preflow_test.run();
 
    50   preflow_test.run();
 
    51   preflow_test.flowValue();
 
    51   preflow_test.flowValue();
 
    52   preflow_test.setSource(n);
 
    52   preflow_test.setSource(n);
 
    53   preflow_test.setFlow(flow);
 
    53   preflow_test.setFlow(flow);
 
    60   preflow_test.setCap(cap);
 
    60   preflow_test.setCap(cap);
 
    61   preflow_test.minMinCut(cut);
 
    61   preflow_test.minMinCut(cut);
 
    62   preflow_test.maxMinCut(cut);
 
    62   preflow_test.maxMinCut(cut);
 
    63 }
 
    63 }
 
    64 
    64 
    65 int cut_value ( SmartGraph& G, SmartGraph::NodeMap<bool>& cut, 
    65 int cut_value ( SmartGraph& g, SmartGraph::NodeMap<bool>& cut, 
    66 		SmartGraph::EdgeMap<int>& cap) {
 
    66 		SmartGraph::EdgeMap<int>& cap) {
 
    67   
    67   
    68   int c=0;
 
    68   int c=0;
 
    69   for(SmartGraph::EdgeIt e(G); e!=INVALID; ++e) {
 
    69   for(SmartGraph::EdgeIt e(g); e!=INVALID; ++e) {
 
    70     if (cut[G.tail(e)] && !cut[G.head(e)]) c+=cap[e];
 
    70     if (cut[g.tail(e)] && !cut[g.head(e)]) c+=cap[e];
 
    71   }
 
    71   }
 
    72   return c;
 
    72   return c;
 
    73 }
 
    73 }
 
    74 
    74 
    75 int main() {
 
    75 int main() {
 
    95   
    95   
    96   std::ifstream file(f_name.c_str());
 
    96   std::ifstream file(f_name.c_str());
 
    97   
    97   
    98   check(file, "Input file '" << f_name << "' not found.");
 
    98   check(file, "Input file '" << f_name << "' not found.");
 
    99   
    99   
   100   Graph G;
 
   100   Graph g;
 
   101   Node s, t;
 
   101   Node s, t;
 
   102   CapMap cap(G);
 
   102   CapMap cap(g);
 
   103   readDimacs(file, G, cap, s, t);
 
   103   readDimacs(file, g, cap, s, t);
 
   104 
   104 
   105   FlowMap flow(G,0);
 
   105   FlowMap flow(g,0);
 
   106 
   106 
   107  
   107  
   108 
   108 
   109   PType preflow_test(G, s, t, cap, flow);
 
   109   PType preflow_test(g, s, t, cap, flow);
 
   110   preflow_test.run(PType::ZERO_FLOW);
 
   110   preflow_test.run(PType::ZERO_FLOW);
 
   111     
   111     
   112   CutMap mincut(G,false);
 
   112   CutMap min_cut(g,false);
 
   113   preflow_test.minCut(mincut); 
   113   preflow_test.minCut(min_cut); 
   114   int min_cut_value=cut_value(G,mincut,cap);
 
   114   int min_cut_value=cut_value(g,min_cut,cap);
 
   115    
   115    
   116   CutMap minmincut(G,false);
 
   116   CutMap min_min_cut(g,false);
 
   117   preflow_test.minMinCut(minmincut); 
   117   preflow_test.minMinCut(min_min_cut); 
   118   int min_min_cut_value=cut_value(G,minmincut,cap);
 
   118   int min_min_cut_value=cut_value(g,min_min_cut,cap);
 
   119    
   119    
   120   CutMap maxmincut(G,false);
 
   120   CutMap max_min_cut(g,false);
 
   121   preflow_test.maxMinCut(maxmincut); 
   121   preflow_test.maxMinCut(max_min_cut); 
   122   int max_min_cut_value=cut_value(G,maxmincut,cap);
 
   122   int max_min_cut_value=cut_value(g,max_min_cut,cap);
 
   123 
   123 
   124   check(preflow_test.flowValue() == min_cut_value &&
 
   124   check(preflow_test.flowValue() == min_cut_value &&
 
   125 	min_cut_value == min_min_cut_value &&
 
   125 	min_cut_value == min_min_cut_value &&
 
   126 	min_min_cut_value == max_min_cut_value,
 
   126 	min_min_cut_value == max_min_cut_value,
 
   127 	"The max flow value is not equal to the three min cut values.");
 
   127 	"The max flow value is not equal to the three min cut values.");
 
   128 
   128 
   129   int flow_value=preflow_test.flowValue();
 
   129   int flow_value=preflow_test.flowValue();
 
   130 
   130 
   131 
   131 
   132 
   132 
   133   for(EdgeIt e(G); e!=INVALID; ++e) cap[e]=2*cap[e]; 
   133   for(EdgeIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; 
   134   preflow_test.setCap(cap);  
   134   preflow_test.setCap(cap);  
   135 
   135 
   136   preflow_test.phase1(PType::PRE_FLOW);
 
   136   preflow_test.phase1(PType::PRE_FLOW);
 
   137 
   137 
   138   CutMap mincut1(G,false);
 
   138   CutMap min_cut1(g,false);
 
   139   preflow_test.minCut(mincut1); 
   139   preflow_test.minCut(min_cut1); 
   140   min_cut_value=cut_value(G,mincut1,cap);
 
   140   min_cut_value=cut_value(g,min_cut1,cap);
 
   141    
   141    
   142   check(preflow_test.flowValue() == min_cut_value &&
 
   142   check(preflow_test.flowValue() == min_cut_value &&
 
   143 	min_cut_value == 2*flow_value,
 
   143 	min_cut_value == 2*flow_value,
 
   144 	"The max flow value or the min cut value is wrong.");
 
   144 	"The max flow value or the min cut value is wrong.");
 
   145 
   145 
   146   preflow_test.phase2();
 
   146   preflow_test.phase2();
 
   147 
   147 
   148   CutMap mincut2(G,false);
 
   148   CutMap min_cut2(g,false);
 
   149   preflow_test.minCut(mincut2); 
   149   preflow_test.minCut(min_cut2); 
   150   min_cut_value=cut_value(G,mincut2,cap);
 
   150   min_cut_value=cut_value(g,min_cut2,cap);
 
   151    
   151    
   152   CutMap minmincut2(G,false);
 
   152   CutMap min_min_cut2(g,false);
 
   153   preflow_test.minMinCut(minmincut2); 
   153   preflow_test.minMinCut(min_min_cut2); 
   154   min_min_cut_value=cut_value(G,minmincut2,cap);
 
   154   min_min_cut_value=cut_value(g,min_min_cut2,cap);
 
   155  
   155  
   156   preflow_test.maxMinCut(maxmincut); 
   156   preflow_test.maxMinCut(max_min_cut); 
   157   max_min_cut_value=cut_value(G,maxmincut,cap);
 
   157   max_min_cut_value=cut_value(g,max_min_cut,cap);
 
   158 
   158 
   159   check(preflow_test.flowValue() == min_cut_value &&
 
   159   check(preflow_test.flowValue() == min_cut_value &&
 
   160 	min_cut_value == min_min_cut_value &&
 
   160 	min_cut_value == min_min_cut_value &&
 
   161 	min_min_cut_value == max_min_cut_value &&
 
   161 	min_min_cut_value == max_min_cut_value &&
 
   162 	min_cut_value == 2*flow_value,
 
   162 	min_cut_value == 2*flow_value,
 
   163 	"The max flow value or the three min cut values were not doubled");
 
   163 	"The max flow value or the three min cut values were not doubled");
 
   164 
   164 
   165 
   165 
   166 
   166 
   167   EdgeIt e(G);
 
   167   EdgeIt e(g);
 
   168   for( int i=1; i==10; ++i ) {
 
   168   for( int i=1; i==10; ++i ) {
 
   169     flow.set(e,0);
 
   169     flow.set(e,0);
 
   170     ++e;
 
   170     ++e;
 
   171   }
 
   171   }
 
   172 
   172 
   173   preflow_test.setFlow(flow); 
   173   preflow_test.setFlow(flow); 
   174 
   174 
   175   NodeIt tmp1(G,s);
 
   175   NodeIt tmp1(g,s);
 
   176   ++tmp1;
 
   176   ++tmp1;
 
   177   if ( tmp1 != INVALID ) s=tmp1;
 
   177   if ( tmp1 != INVALID ) s=tmp1;
 
   178 
   178 
   179   NodeIt tmp2(G,t);
 
   179   NodeIt tmp2(g,t);
 
   180   ++tmp2;
 
   180   ++tmp2;
 
   181   if ( tmp2 != INVALID ) t=tmp2;
 
   181   if ( tmp2 != INVALID ) t=tmp2;
 
   182 
   182 
   183   preflow_test.setSource(s);
 
   183   preflow_test.setSource(s);
 
   184   preflow_test.setTarget(t); 
   184   preflow_test.setTarget(t); 
   185   
   185   
   186   preflow_test.run();
 
   186   preflow_test.run();
 
   187 
   187 
   188   CutMap mincut3(G,false);
 
   188   CutMap min_cut3(g,false);
 
   189   preflow_test.minCut(mincut3); 
   189   preflow_test.minCut(min_cut3); 
   190   min_cut_value=cut_value(G,mincut3,cap);
 
   190   min_cut_value=cut_value(g,min_cut3,cap);
 
   191    
   191    
   192   CutMap minmincut3(G,false);
 
   192   CutMap min_min_cut3(g,false);
 
   193   preflow_test.minMinCut(minmincut3); 
   193   preflow_test.minMinCut(min_min_cut3); 
   194   min_min_cut_value=cut_value(G,minmincut3,cap);
 
   194   min_min_cut_value=cut_value(g,min_min_cut3,cap);
 
   195    
   195    
   196   preflow_test.maxMinCut(maxmincut); 
   196   preflow_test.maxMinCut(max_min_cut); 
   197   max_min_cut_value=cut_value(G,maxmincut,cap);
 
   197   max_min_cut_value=cut_value(g,max_min_cut,cap);
 
   198 
   198 
   199   check(preflow_test.flowValue() == min_cut_value &&
 
   199   check(preflow_test.flowValue() == min_cut_value &&
 
   200 	min_cut_value == min_min_cut_value &&
 
   200 	min_cut_value == min_min_cut_value &&
 
   201 	min_min_cut_value == max_min_cut_value,
 
   201 	min_min_cut_value == max_min_cut_value,
 
   202 	"The max flow value or the three min cut values are incorrect.");
 
   202 	"The max flow value or the three min cut values are incorrect.");
lemon-0.x