lemon-0.x: src/work/jacint/max_flow

     1 #include <iostream>

     3 #include <list_graph.h>

     4 #include <dimacs.h>

     5 #include <max_flow.h>

     6 #include <time_measure.h>

     8 using namespace hugo;

    10 int main(int, char **) {

    12   typedef ListGraph 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   readDimacs(std::cin, G, cap, s, t);

    21   Timer ts;

    23   std::cout <<

    24     "\n  Running max_flow.h on a graph with " <<

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

    26 	   << std::endl<<std::endl;

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

    29   MaxFlow<Graph, int> max_flow_test(G, s, t, cap, flow);

    30   ts.reset();

    31   max_flow_test.run();

    32   std::cout << "Elapsed time of run(): " << std::endl

    33 	    <<ts << std::endl;

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

    36   max_flow_test.minMinCut(mincut);

    37   int min_min_cut_value=0;

    38   EdgeIt e;

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

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

    41   }

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

    44   max_flow_test.minCut(cut);

    45   int min_cut_value=0;

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

    47     if (cut[G.tail(e)] && !cut[G.head(e)])

    48       min_cut_value+=cap[e];

    49   }

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

    52   max_flow_test.maxMinCut(maxcut);

    53   int max_min_cut_value=0;

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

    55     if (maxcut[G.tail(e)] && !maxcut[G.head(e)])

    56       max_min_cut_value+=cap[e];

    57       }

    59   std::cout << "\n Checking the result: " <<std::endl;

    60   std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl;

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

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

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

    64     std::endl;

    66   if ( max_flow_test.flowValue() == min_cut_value &&

    67        min_cut_value == min_min_cut_value &&

    68        min_min_cut_value == max_min_cut_value )

    69     std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";

    73   Graph::EdgeMap<int> flow2(G,0);

    74   std::cout << "Calling resetFlow() " << std::endl

    75 	    << ts << std::endl;

    76   max_flow_test.resetFlow(flow2);

    77   ts.reset();

    78   max_flow_test.preflow(max_flow_test.PRE_FLOW);

    79   std::cout << "Elapsed time of preflow(PRE_FLOW) starting from the zero flow: " << std::endl

    80 	    << ts << std::endl;

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

    83   max_flow_test.minMinCut(mincut2);

    84   int min_min_cut_value2=0;

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

    86     if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e];

    87   }

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

    90   max_flow_test.minCut(cut2);

    91   int min_cut_value2=0;

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

    93     if (cut2[G.tail(e)] && !cut2[G.head(e)])

    94       min_cut_value2+=cap[e];

    95   }

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

    98   max_flow_test.maxMinCut(maxcut2);

    99   int max_min_cut_value2=0;

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

   101     if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)])

   102       max_min_cut_value2+=cap[e];

   103       }

   105   std::cout << "\n Checking the result: " <<std::endl;

   106   std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl;

   107   std::cout << "Min cut value: "<< min_cut_value2 << std::endl;

   108   std::cout << "Min min cut value: "<< min_min_cut_value2 << std::endl;

   109   std::cout << "Max min cut value: "<< max_min_cut_value2 <<

   110     std::endl;

   111   if ( max_flow_test.flowValue() == min_cut_value &&

   112        min_cut_value == min_min_cut_value &&

   113        min_min_cut_value == max_min_cut_value )

   114     std::cout << "They are equal! " <<std::endl;

   117   MaxFlow<Graph, int> max_flow_test3(G, s, t, cap, flow2);

   118   max_flow_test3.run(max_flow_test3.GEN_FLOW);

   119   std::cout << "Calling run(GEN_FLOW) from the max flow found before. " <<std::endl;

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

   122   max_flow_test3.minMinCut(mincut3);

   123   int min_min_cut_value3=0;

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

   125     if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e];

   126   }

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

   129   max_flow_test3.minCut(cut3);

   130   int min_cut_value3=0;

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

   132     if (cut3[G.tail(e)] && !cut3[G.head(e)])

   133       min_cut_value3+=cap[e];

   134   }

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

   137   max_flow_test3.maxMinCut(maxcut3);

   138   int max_min_cut_value3=0;

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

   140     if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)])

   141       max_min_cut_value3+=cap[e];

   142   }

   144   std::cout << "\n Checking the result: " <<std::endl;

   145   std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl;

   146   std::cout << "Min cut value: "<< min_cut_value3 << std::endl;

   147   std::cout << "Min min cut value: "<< min_min_cut_value3 << std::endl;

   148   std::cout << "Max min cut value: "<< max_min_cut_value3 <<

   149     std::endl;

   151   if ( max_flow_test3.flowValue() == min_cut_value3 &&

   152        min_cut_value3 == min_min_cut_value3 &&

   153        min_min_cut_value3 == max_min_cut_value3 )

   154     std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";

   156   return 0;

   157 }

author	klao
	Fri, 04 Jun 2004 16:05:20 +0000
changeset 675	38755a4d4b51
child 715	665689d86225
permissions	-rw-r--r--