lemon-0.x: src/work/jacint/preflow.cc@bfd6c14e2975

     1 #include <iostream>

     3 #include <smart_graph.h>

     4 #include <dimacs.h>

     5 #include <preflow.h>

     6 #include <time_measure.h>

     8 using namespace hugo;

    10 int main(int, char **) {

    12   typedef SmartGraph Graph;

    14   typedef Graph::Node Node;

    15   typedef Graph::EdgeIt EdgeIt;

    17   Graph G;

    18   Node s, t;

    19   Graph::EdgeMap<int> cap(G);

    20   readDimacsMaxFlow(std::cin, G, s, t, cap);

    21   Timer ts;

    22   bool error=false;

    24   std::cout <<

    25     "\n  Testing preflow.h on a graph with " <<

    26     G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."

    27 	   << std::endl;

    30   Graph::EdgeMap<int> flow(G,0);

    31   Preflow<Graph, int> preflow_test(G, s, t, cap, flow);

    32   std::cout << "\nCalling run() (flow must be constant zero)..."<<std::endl;

    33   ts.reset();

    34   preflow_test.run();

    35   std::cout << "Elapsed time: " << ts << std::endl;

    37   Graph::NodeMap<bool> mincut(G);

    38   preflow_test.minMinCut(mincut);

    39   int min_min_cut_value=0;

    40   Graph::NodeMap<bool> cut(G);

    41   preflow_test.minCut(cut);

    42   int min_cut_value=0;

    43   Graph::NodeMap<bool> maxcut(G);

    44   preflow_test.maxMinCut(maxcut);

    45   int max_min_cut_value=0;

    46   EdgeIt e;

    47   for(G.first(e); G.valid(e); G.next(e)) {

    48     int c=cap[e];

    49     if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=c;

    50     if (cut[G.tail(e)] && !cut[G.head(e)]) min_cut_value+=c;

    51     if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) max_min_cut_value+=c;

    52   }

    54   std::cout << "\nChecking the result: " <<std::endl;

    55   std::cout << "Flow value: "<< preflow_test.flowValue() << std::endl;

    56   std::cout << "Min cut value: "<< min_cut_value << std::endl;

    57   std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;

    58   std::cout << "Max min cut value: "<< max_min_cut_value <<

    59     std::endl;

    61   if ( preflow_test.flowValue() == min_cut_value &&

    62        min_cut_value == min_min_cut_value &&

    63        min_min_cut_value == max_min_cut_value )

    64     std::cout << "They are equal. " <<std::endl;

    65   else {

    66     std::cout << "ERROR! They are not equal! " <<std::endl;

    67     error=true;

    68   }

    72   Preflow<Graph, int> preflow_test2(G, s, t, cap, flow);

    73   std::cout << "\n\nCalling preflow(GEN_FLOW) with the given maximum flow..."<<std::endl;

    74   ts.reset();

    75   preflow_test2.preflow(preflow_test2.GEN_FLOW);

    76   std::cout << "Elapsed time: " << ts << std::endl;

    78   Graph::NodeMap<bool> mincut2(G);

    79   preflow_test.minMinCut(mincut2);

    80   int min_min_cut2_value=0;

    81   Graph::NodeMap<bool> cut2(G);

    82   preflow_test.minCut(cut2);

    83   int min_cut2_value=0;

    84   Graph::NodeMap<bool> maxcut2(G);

    85   preflow_test.maxMinCut(maxcut2);

    86   int max_min_cut2_value=0;

    87   for(G.first(e); G.valid(e); G.next(e)) {

    88     int c=cap[e];

    89     if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut2_value+=c;

    90     if (cut2[G.tail(e)] && !cut2[G.head(e)]) min_cut2_value+=c;

    91     if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) max_min_cut2_value+=c;

    92   }

    94   std::cout << "\nThe given flow value is "

    95 	    << preflow_test2.flowValue();

    97   if ( preflow_test2.flowValue() == min_cut2_value &&

    98        min_cut2_value == min_min_cut2_value &&

    99        min_min_cut2_value == max_min_cut2_value )

   100     std::cout <<", which is equal to all three min cut values."

   101 	      <<std::endl;

   102   else {

   103     std::cout << "ERROR! It is not equal to all three min cut values! "

   104 	      <<std::endl;

   105     error=true;

   106   }

   111   Graph::EdgeMap<int> flow3(G,0);

   112   Preflow<Graph, int> preflow_test3(G, s, t, cap, flow3);

   113   std::cout << "\n\nCalling preflowPhase0(PREFLOW) on the constant zero flow..."<<std::endl;

   114   ts.reset();

   115   preflow_test3.preflowPhase0(preflow_test3.PREFLOW);

   116   std::cout << "Elapsed time: " << ts << std::endl;

   117   Graph::NodeMap<bool> actcut3(G);

   118   std::cout << "\nCalling actMinCut()..."<<std::endl;

   119   preflow_test3.actMinCut(actcut3);

   120   std::cout << "Calling preflowPhase1() on the given flow..."<<std::endl;

   121   ts.reset();

   122   preflow_test3.preflowPhase1();

   123   std::cout << "Elapsed time: " << ts << std::endl;

   125   int act_min_cut3_value=0;

   127   Graph::NodeMap<bool> mincut3(G);

   128   preflow_test.minMinCut(mincut3);

   129   int min_min_cut3_value=0;

   131   Graph::NodeMap<bool> cut3(G);

   132   preflow_test.minCut(cut3);

   133   int min_cut3_value=0;

   135   Graph::NodeMap<bool> maxcut3(G);

   136   preflow_test.maxMinCut(maxcut3);

   137   int max_min_cut3_value=0;

   139   for(G.first(e); G.valid(e); G.next(e)) {

   140     int c=cap[e];

   141     if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut3_value+=c;

   142     if (cut3[G.tail(e)] && !cut3[G.head(e)]) min_cut3_value+=c;

   143     if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)]) max_min_cut3_value+=c;

   144     if (actcut3[G.tail(e)] && !actcut3[G.head(e)]) act_min_cut3_value+=c;

   145   }

   147  std::cout << "\nThe min cut value given by actMinCut() after phase 0 is "<<

   148    act_min_cut3_value;

   150   if ( preflow_test3.flowValue() == min_cut3_value &&

   151        min_cut3_value == min_min_cut3_value &&

   152        min_min_cut3_value == max_min_cut3_value &&

   153        max_min_cut3_value == act_min_cut3_value ) {

   154     std::cout <<

   155       ", which is equal to the given flow value and to all three min cut values after phase 1."

   156 	      <<std::endl;

   157   }

   158   else {

   159     std::cout <<

   160       "ERROR! It is not equal to the given flow value and to all three min cut values after phase 1! "

   161 	      <<std::endl;

   162     error=true;

   163   }

   169   Graph::EdgeMap<int> flow4(G,0);

   170   Preflow<Graph, int> preflow_test4(G, s, t, cap, flow4);

   171   std::cout <<

   172     "\n\nCalling preflow(PREFLOW) with the constant 0 flow, the result is f..."

   173 	    <<std::endl;

   174   preflow_test4.preflow(preflow_test4.PREFLOW);

   176   std::cout << "Swapping the source and the target, "<<std::endl;

   177   std::cout << "by calling resetSource(t) and resetTarget(s)..."

   178 	    <<std::endl;

   179   preflow_test4.resetSource(t);

   180   preflow_test4.resetTarget(s);

   182   std::cout <<

   183     "Calling preflow(PREFLOW) to find a maximum t-s flow starting with flow f..."

   184 	    <<std::endl;

   185   preflow_test4.preflow(preflow_test4.PREFLOW);

   187   Graph::NodeMap<bool> mincut4(G);

   188   preflow_test4.minMinCut(mincut4);

   189   int min_min_cut4_value=0;

   190   Graph::NodeMap<bool> cut4(G);

   191   preflow_test4.minCut(cut4);

   192   int min_cut4_value=0;

   193   Graph::NodeMap<bool> maxcut4(G);

   194   preflow_test4.maxMinCut(maxcut4);

   195   int max_min_cut4_value=0;

   196   for(G.first(e); G.valid(e); G.next(e)) {

   197     int c=cap[e];

   198     if (mincut4[G.tail(e)] && !mincut4[G.head(e)]) min_min_cut4_value+=c;

   199     if (cut4[G.tail(e)] && !cut4[G.head(e)]) min_cut4_value+=c;

   200     if (maxcut4[G.tail(e)] && !maxcut4[G.head(e)]) max_min_cut4_value+=c;

   201   }

   203   std::cout << "\nThe given flow value is "

   204 	    << preflow_test4.flowValue();

   206   if ( preflow_test4.flowValue() == min_cut4_value &&

   207        min_cut4_value == min_min_cut4_value &&

   208        min_min_cut4_value == max_min_cut4_value )

   209     std::cout <<", which is equal to all three min cut values."

   210 	      <<std::endl;

   211   else {

   212     std::cout << "ERROR! It is not equal to all three min cut values! "

   213 	      <<std::endl;

   214     error=true;

   215   }

   220   Graph::EdgeMap<int> flow5(G,0);

   221   std::cout << "Resetting the stored flow to constant zero, by calling resetFlow..."

   222 	    <<std::endl;

   223   preflow_test4.resetFlow(flow5);

   224   std::cout <<

   225     "Calling preflow(GEN_FLOW) to find a maximum t-s flow "<<std::endl;

   226   std::cout <<

   227     "starting with this constant zero flow..." <<std::endl;

   228   preflow_test4.preflow(preflow_test4.GEN_FLOW);

   230   Graph::NodeMap<bool> mincut5(G);

   231   preflow_test4.minMinCut(mincut5);

   232   int min_min_cut5_value=0;

   233   Graph::NodeMap<bool> cut5(G);

   234   preflow_test4.minCut(cut5);

   235   int min_cut5_value=0;

   236   Graph::NodeMap<bool> maxcut5(G);

   237   preflow_test4.maxMinCut(maxcut5);

   238   int max_min_cut5_value=0;

   239   for(G.first(e); G.valid(e); G.next(e)) {

   240     int c=cap[e];

   241     if (mincut5[G.tail(e)] && !mincut5[G.head(e)]) min_min_cut5_value+=c;

   242     if (cut5[G.tail(e)] && !cut5[G.head(e)]) min_cut5_value+=c;

   243     if (maxcut5[G.tail(e)] && !maxcut5[G.head(e)]) max_min_cut5_value+=c;

   244   }

   246   std::cout << "\nThe given flow value is "

   247 	    << preflow_test4.flowValue();

   249   if ( preflow_test4.flowValue() == min_cut5_value &&

   250        min_cut5_value == min_min_cut5_value &&

   251        min_min_cut5_value == max_min_cut5_value )

   252     std::cout <<", which is equal to all three min cut values."

   253 	      <<std::endl<<std::endl;

   254   else {

   255     std::cout << "ERROR! It is not equal to all three min cut values! "

   256 	      <<std::endl;

   257     error=true;

   258   }

   260   if (error) std::cout <<"\nThere was some error in the results!\n"<<std::endl;

   261   else std::cout <<"\nThere was no error in the results.\n"<<std::endl;

   263   return 0;

   264 }

author	marci
	Fri, 14 May 2004 18:08:29 +0000
changeset 641	bfd6c14e2975
parent 451	6b36be4cffa4
child 921	818510fa3d99
permissions	-rw-r--r--