src/test/preflow_test.cc
author alpar
Mon, 13 Sep 2004 11:24:35 +0000
changeset 835 eb9587f09b42
child 842 a4bb28813570
permissions -rwxr-xr-x
Remove one remaining range checking.
     1 #include <fstream>
     2 #include "test_tools.h"
     3 #include <hugo/smart_graph.h>
     4 #include <hugo/dimacs.h>
     5 #include <hugo/preflow.h>
     6 #include <hugo/skeletons/graph.h>
     7 #include <hugo/skeletons/maps.h>
     8 using namespace hugo;
     9 
    10 void check_Preflow() 
    11 {
    12   typedef int VType;
    13   typedef skeleton::StaticGraphSkeleton Graph;
    14 
    15   typedef Graph::Node Node;
    16   typedef Graph::Edge Edge;
    17   typedef skeleton::ReadMap<Edge,VType> CapMap;
    18   typedef skeleton::ReadWriteMap<Edge,VType> FlowMap;
    19   typedef skeleton::ReadWriteMap<Node,bool> CutMap;
    20  
    21   typedef Preflow<Graph, int, CapMap, FlowMap> PType;
    22 
    23   Graph G;
    24   Node n;
    25   CapMap cap;
    26   FlowMap flow;
    27   CutMap cut;
    28 
    29   PType preflow_test(G,n,n,cap,flow);
    30 
    31   preflow_test.run();
    32   preflow_test.flowValue();
    33   preflow_test.setSource(n);
    34   preflow_test.setFlow(flow);
    35 
    36   preflow_test.phase1(PType::NO_FLOW);
    37   preflow_test.minCut(cut);
    38 
    39   preflow_test.phase2();
    40   preflow_test.setTarget(n);
    41   preflow_test.setCap(cap);
    42   preflow_test.minMinCut(cut);
    43   preflow_test.maxMinCut(cut);
    44 }
    45 
    46 int cut_value ( SmartGraph& G, SmartGraph::NodeMap<bool>& cut, 
    47 		SmartGraph::EdgeMap<int>& cap) {
    48   
    49   int c=0;
    50   for(SmartGraph::EdgeIt e(G); e!=INVALID; ++e) {
    51     if (cut[G.tail(e)] && !cut[G.head(e)]) c+=cap[e];
    52   }
    53   return c;
    54 }
    55 
    56 int main() {
    57 
    58   typedef SmartGraph Graph;
    59   
    60   typedef Graph::NodeIt NodeIt;
    61   typedef Graph::EdgeIt EdgeIt;
    62   typedef Graph::EdgeMap<int> CapMap;
    63   typedef Graph::EdgeMap<int> FlowMap;
    64   typedef Graph::NodeMap<bool> CutMap;
    65 
    66   typedef Preflow<Graph, int> PType;
    67 
    68   std::ifstream file("preflow_graph");
    69   
    70   Graph G;
    71   NodeIt s, t;
    72   CapMap cap(G);
    73   readDimacs(file, G, cap, s, t);
    74 
    75   FlowMap flow(G,0);
    76  
    77   PType preflow_test(G, s, t, cap, flow);
    78   preflow_test.run(PType::ZERO_FLOW);
    79  
    80    
    81   CutMap mincut(G,false);
    82   preflow_test.minCut(mincut); 
    83   int min_cut_value=cut_value(G,mincut,cap);
    84    
    85   CutMap minmincut(G,false);
    86   preflow_test.minMinCut(minmincut); 
    87   int min_min_cut_value=cut_value(G,minmincut,cap);
    88    
    89   CutMap maxmincut(G,false);
    90   preflow_test.maxMinCut(maxmincut); 
    91   int max_min_cut_value=cut_value(G,maxmincut,cap);
    92 
    93   check(preflow_test.flowValue() == min_cut_value &&
    94 	min_cut_value == min_min_cut_value &&
    95 	min_min_cut_value == max_min_cut_value,
    96 	"The max flow value is not equal to the three min cut values.");
    97 
    98   int flow_value=preflow_test.flowValue();
    99 
   100 
   101   for(EdgeIt e(G); e!=INVALID; ++e) cap[e]=2*cap[e]; 
   102   preflow_test.setCap(cap);  
   103   preflow_test.setTarget(++t); //the max flow value remains 2*flow_value
   104   //warning: ++t must be a valid node. In preflow_graph, it is.
   105 
   106   preflow_test.phase1(PType::PRE_FLOW);
   107 
   108   CutMap mincut1(G,false);
   109   preflow_test.minCut(mincut1); 
   110   min_cut_value=cut_value(G,mincut1,cap);
   111    
   112   check(preflow_test.flowValue() == min_cut_value &&
   113 	min_cut_value == 2*flow_value,
   114 	"The max flow value or the min cut value is wrong.");
   115 
   116   preflow_test.phase2();
   117 
   118   CutMap mincut2(G,false);
   119   preflow_test.minCut(mincut2); 
   120   min_cut_value=cut_value(G,mincut2,cap);
   121    
   122   CutMap minmincut2(G,false);
   123   preflow_test.minMinCut(minmincut2); 
   124   min_min_cut_value=cut_value(G,minmincut2,cap);
   125 
   126  
   127   preflow_test.maxMinCut(maxmincut); 
   128   
   129   max_min_cut_value=cut_value(G,maxmincut,cap);
   130 
   131   check(preflow_test.flowValue() == min_cut_value &&
   132 	min_cut_value == min_min_cut_value &&
   133 	min_min_cut_value == max_min_cut_value &&
   134 	min_cut_value == 2*flow_value,
   135 	"The max flow value or the three min cut values were not doubled");
   136 
   137   EdgeIt e(G);
   138   for( int i=1; i==1000; ++i ) {
   139     flow[e]=0;
   140     ++e;
   141   }
   142 
   143   preflow_test.setFlow(flow); 
   144   preflow_test.setSource(s);
   145 
   146   preflow_test.run();
   147 
   148   CutMap mincut3(G,false);
   149   preflow_test.minCut(mincut3); 
   150   min_cut_value=cut_value(G,mincut3,cap);
   151    
   152   CutMap minmincut3(G,false);
   153   preflow_test.minMinCut(minmincut3); 
   154   min_min_cut_value=cut_value(G,minmincut3,cap);
   155    
   156   preflow_test.maxMinCut(maxmincut); 
   157   max_min_cut_value=cut_value(G,maxmincut,cap);
   158 
   159   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 	"The max flow value or the three min cut values are incorrect.");
   163 }
   164 
   165 
   166