test/preflow_test.cc
changeset 2517 d9cfac072869
parent 2391 14a343be7a5a
child 2553 bfced05fa852
equal deleted inserted replaced
6:27a04c36f190 7:54839ad9841b
    26 #include <lemon/concepts/graph.h>
    26 #include <lemon/concepts/graph.h>
    27 #include <lemon/concepts/maps.h>
    27 #include <lemon/concepts/maps.h>
    28 
    28 
    29 using namespace lemon;
    29 using namespace lemon;
    30 
    30 
    31 void check_Preflow() 
    31 void checkPreflow() 
    32 {
    32 {
    33   typedef int VType;
    33   typedef int VType;
    34   typedef concepts::Graph Graph;
    34   typedef concepts::Graph Graph;
    35 
    35 
    36   typedef Graph::Node Node;
    36   typedef Graph::Node Node;
    37   typedef Graph::Edge Edge;
    37   typedef Graph::Edge Edge;
    38   typedef concepts::ReadMap<Edge,VType> CapMap;
    38   typedef concepts::ReadMap<Edge,VType> CapMap;
    39   typedef concepts::ReadWriteMap<Edge,VType> FlowMap;
    39   typedef concepts::ReadWriteMap<Edge,VType> FlowMap;
    40   typedef concepts::ReadWriteMap<Node,bool> CutMap;
    40   typedef concepts::WriteMap<Node,bool> CutMap;
    41  
    41  
    42   typedef Preflow<Graph, int, CapMap, FlowMap> PType;
       
    43 
       
    44   Graph g;
    42   Graph g;
    45   Node n;
    43   Node n;
       
    44   Edge e;
    46   CapMap cap;
    45   CapMap cap;
    47   FlowMap flow;
    46   FlowMap flow;
    48   CutMap cut;
    47   CutMap cut;
    49 
    48 
    50   PType preflow_test(g,n,n,cap,flow);
    49   Preflow<Graph, CapMap>::DefFlowMap<FlowMap>::Create preflow_test(g,cap,n,n);
    51 
    50 
       
    51   preflow_test.capacityMap(cap);
       
    52   flow = preflow_test.flowMap();
       
    53   preflow_test.flowMap(flow);
       
    54   preflow_test.source(n);
       
    55   preflow_test.target(n);
       
    56   
       
    57   preflow_test.init();
       
    58   preflow_test.flowInit(cap);
       
    59   preflow_test.startFirstPhase();
       
    60   preflow_test.startSecondPhase();
    52   preflow_test.run();
    61   preflow_test.run();
       
    62   preflow_test.runMinCut();
       
    63 
    53   preflow_test.flowValue();
    64   preflow_test.flowValue();
    54   preflow_test.source(n);
    65   preflow_test.minCut(n);
    55   preflow_test.flowMap(flow);
    66   preflow_test.minCutMap(cut);
    56 
    67   preflow_test.flow(e);
    57   preflow_test.phase1(PType::NO_FLOW);
    68 
    58   preflow_test.minCut(cut);
    69 }
    59 
    70 
    60   preflow_test.phase2();
    71 int cutValue (const SmartGraph& g, 
    61   preflow_test.target(n);
    72 	      const SmartGraph::NodeMap<bool>& cut, 
    62   preflow_test.capacityMap(cap);
    73 	      const SmartGraph::EdgeMap<int>& cap) {
    63   preflow_test.minMinCut(cut);
       
    64   preflow_test.maxMinCut(cut);
       
    65 }
       
    66 
       
    67 int cut_value ( SmartGraph& g, SmartGraph::NodeMap<bool>& cut, 
       
    68 		SmartGraph::EdgeMap<int>& cap) {
       
    69   
    74   
    70   int c=0;
    75   int c=0;
    71   for(SmartGraph::EdgeIt e(g); e!=INVALID; ++e) {
    76   for(SmartGraph::EdgeIt e(g); e!=INVALID; ++e) {
    72     if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
    77     if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
    73   }
    78   }
    74   return c;
    79   return c;
       
    80 }
       
    81 
       
    82 bool checkFlow(const SmartGraph& g, 
       
    83 	       const SmartGraph::EdgeMap<int>& flow, 
       
    84 	       const SmartGraph::EdgeMap<int>& cap, 
       
    85 	       SmartGraph::Node s, SmartGraph::Node t) {
       
    86 
       
    87   for (SmartGraph::EdgeIt e(g); e != INVALID; ++e) {
       
    88     if (flow[e] < 0 || flow[e] > cap[e]) return false;
       
    89   }
       
    90 
       
    91   for (SmartGraph::NodeIt n(g); n != INVALID; ++n) {
       
    92     if (n == s || n == t) continue;
       
    93     int sum = 0;
       
    94     for (SmartGraph::OutEdgeIt e(g, n); e != INVALID; ++e) {
       
    95       sum += flow[e];
       
    96     }
       
    97     for (SmartGraph::InEdgeIt e(g, n); e != INVALID; ++e) {
       
    98       sum -= flow[e];
       
    99     }
       
   100     if (sum != 0) return false;
       
   101   }
       
   102   return true;
    75 }
   103 }
    76 
   104 
    77 int main() {
   105 int main() {
    78 
   106 
    79   typedef SmartGraph Graph;
   107   typedef SmartGraph Graph;
    83   typedef Graph::EdgeIt EdgeIt;
   111   typedef Graph::EdgeIt EdgeIt;
    84   typedef Graph::EdgeMap<int> CapMap;
   112   typedef Graph::EdgeMap<int> CapMap;
    85   typedef Graph::EdgeMap<int> FlowMap;
   113   typedef Graph::EdgeMap<int> FlowMap;
    86   typedef Graph::NodeMap<bool> CutMap;
   114   typedef Graph::NodeMap<bool> CutMap;
    87 
   115 
    88   typedef Preflow<Graph, int> PType;
   116   typedef Preflow<Graph, CapMap> PType;
    89 
   117 
    90   std::string f_name;
   118   std::string f_name;
    91   if( getenv("srcdir") )
   119   if( getenv("srcdir") )
    92     f_name = std::string(getenv("srcdir"));
   120     f_name = std::string(getenv("srcdir"));
    93   else f_name = ".";
   121   else f_name = ".";
   100   Graph g;
   128   Graph g;
   101   Node s, t;
   129   Node s, t;
   102   CapMap cap(g);
   130   CapMap cap(g);
   103   readDimacs(file, g, cap, s, t);
   131   readDimacs(file, g, cap, s, t);
   104 
   132 
   105   FlowMap flow(g,0);
   133   PType preflow_test(g, cap, s, t);
   106 
   134   preflow_test.run();
   107  
       
   108 
       
   109   PType preflow_test(g, s, t, cap, flow);
       
   110   preflow_test.run(PType::ZERO_FLOW);
       
   111     
   135     
   112   CutMap min_cut(g,false);
   136   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
   113   preflow_test.minCut(min_cut); 
   137 	"The flow is not feasible.");
   114   int min_cut_value=cut_value(g,min_cut,cap);
   138 
   115    
   139   CutMap min_cut(g);
   116   CutMap min_min_cut(g,false);
   140   preflow_test.minCutMap(min_cut); 
   117   preflow_test.minMinCut(min_min_cut); 
   141   int min_cut_value=cutValue(g,min_cut,cap);
   118   int min_min_cut_value=cut_value(g,min_min_cut,cap);
   142   
   119    
   143   check(preflow_test.flowValue() == min_cut_value,
   120   CutMap max_min_cut(g,false);
       
   121   preflow_test.maxMinCut(max_min_cut); 
       
   122   int max_min_cut_value=cut_value(g,max_min_cut,cap);
       
   123 
       
   124   check(preflow_test.flowValue() == min_cut_value &&
       
   125 	min_cut_value == min_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.");
   144 	"The max flow value is not equal to the three min cut values.");
   128 
   145 
       
   146   FlowMap flow(g);
       
   147   flow = preflow_test.flowMap();
       
   148 
   129   int flow_value=preflow_test.flowValue();
   149   int flow_value=preflow_test.flowValue();
   130 
   150 
   131 
       
   132 
       
   133   for(EdgeIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; 
   151   for(EdgeIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; 
   134   preflow_test.capacityMap(cap);  
   152   preflow_test.flowInit(flow);
   135 
   153   preflow_test.startFirstPhase();
   136   preflow_test.phase1(PType::PRE_FLOW);
   154 
   137 
   155   CutMap min_cut1(g);
   138   CutMap min_cut1(g,false);
   156   preflow_test.minCutMap(min_cut1); 
   139   preflow_test.minCut(min_cut1); 
   157   min_cut_value=cutValue(g,min_cut1,cap);
   140   min_cut_value=cut_value(g,min_cut1,cap);
       
   141    
   158    
   142   check(preflow_test.flowValue() == min_cut_value &&
   159   check(preflow_test.flowValue() == min_cut_value &&
   143 	min_cut_value == 2*flow_value,
   160 	min_cut_value == 2*flow_value,
   144 	"The max flow value or the min cut value is wrong.");
   161 	"The max flow value or the min cut value is wrong.");
   145 
   162 
   146   preflow_test.phase2();
   163   preflow_test.startSecondPhase();
   147 
   164 
   148   CutMap min_cut2(g,false);
   165   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
   149   preflow_test.minCut(min_cut2); 
   166 	"The flow is not feasible.");
   150   min_cut_value=cut_value(g,min_cut2,cap);
   167 
       
   168   CutMap min_cut2(g);
       
   169   preflow_test.minCutMap(min_cut2); 
       
   170   min_cut_value=cutValue(g,min_cut2,cap);
   151    
   171    
   152   CutMap min_min_cut2(g,false);
       
   153   preflow_test.minMinCut(min_min_cut2); 
       
   154   min_min_cut_value=cut_value(g,min_min_cut2,cap);
       
   155  
       
   156   preflow_test.maxMinCut(max_min_cut); 
       
   157   max_min_cut_value=cut_value(g,max_min_cut,cap);
       
   158 
       
   159   check(preflow_test.flowValue() == min_cut_value &&
   172   check(preflow_test.flowValue() == min_cut_value &&
   160 	min_cut_value == min_min_cut_value &&
       
   161 	min_min_cut_value == max_min_cut_value &&
       
   162 	min_cut_value == 2*flow_value,
   173 	min_cut_value == 2*flow_value,
   163 	"The max flow value or the three min cut values were not doubled");
   174 	"The max flow value or the three min cut values were not doubled");
   164 
   175 
   165 
       
   166 
       
   167   EdgeIt e(g);
       
   168   for( int i=1; i==10; ++i ) {
       
   169     flow.set(e,0);
       
   170     ++e;
       
   171   }
       
   172 
   176 
   173   preflow_test.flowMap(flow); 
   177   preflow_test.flowMap(flow); 
   174 
   178 
   175   NodeIt tmp1(g,s);
   179   NodeIt tmp1(g,s);
   176   ++tmp1;
   180   ++tmp1;
   183   preflow_test.source(s);
   187   preflow_test.source(s);
   184   preflow_test.target(t); 
   188   preflow_test.target(t); 
   185   
   189   
   186   preflow_test.run();
   190   preflow_test.run();
   187 
   191 
   188   CutMap min_cut3(g,false);
   192   CutMap min_cut3(g);
   189   preflow_test.minCut(min_cut3); 
   193   preflow_test.minCutMap(min_cut3); 
   190   min_cut_value=cut_value(g,min_cut3,cap);
   194   min_cut_value=cutValue(g,min_cut3,cap);
   191    
   195    
   192   CutMap min_min_cut3(g,false);
   196 
   193   preflow_test.minMinCut(min_min_cut3); 
   197   check(preflow_test.flowValue() == min_cut_value,
   194   min_min_cut_value=cut_value(g,min_min_cut3,cap);
       
   195    
       
   196   preflow_test.maxMinCut(max_min_cut); 
       
   197   max_min_cut_value=cut_value(g,max_min_cut,cap);
       
   198 
       
   199   check(preflow_test.flowValue() == min_cut_value &&
       
   200 	min_cut_value == min_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.");
   198 	"The max flow value or the three min cut values are incorrect.");
   203 }
   199   
       
   200   return 0;
       
   201 }