source: lemon-0.x/src/work/jacint/preflow_res_comp.cc @ 410:d137525538dc

/*
The only difference between preflow.h and preflow_res.h is that the latter
uses the ResGraphWrapper, while the first does not. (Bfs is implemented by
hand in both.) This test program runs Preflow and PreflowRes on the same
graph, tests the result of these implementations and writes the running time
of them.  */
#include <iostream>

#include <smart_graph.h>
#include <dimacs.h>
#include <preflow.h>
#include <preflow_res.h>
#include <time_measure.h>

using namespace hugo;

int main(int, char **) {
 
  typedef SmartGraph Graph;
  
  typedef Graph::Node Node;
  typedef Graph::EdgeIt EdgeIt;

  Graph G;
  Node s, t;
  Graph::EdgeMap<int> cap(G);
  readDimacsMaxFlow(std::cin, G, s, t, cap);
  Timer ts;
  
  std::cout <<
    "\n  In which way are we faster: using ResGraphWrapper or not?"
            <<std::endl;
  std::cout <<
    "\n  Running preflow.h on a graph with " << 
    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
           << std::endl<<std::endl;


  
  Graph::EdgeMap<int> flow(G,0);
  Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 1);
  ts.reset();
  max_flow_test.run();
  std::cout << "Elapsed time NOT using the ResGraphWrapper: " << std::endl 
            <<ts << std::endl;
  
  Graph::NodeMap<bool> mincut(G);
  max_flow_test.minMinCut(mincut); 
  int min_min_cut_value=0;
  EdgeIt e;
  for(G.first(e); G.valid(e); G.next(e)) {
    if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];
  }

  Graph::NodeMap<bool> cut(G);
  max_flow_test.minCut(cut); 
  int min_cut_value=0;
  for(G.first(e); G.valid(e); G.next(e)) {
    if (cut[G.tail(e)] && !cut[G.head(e)]) 
      min_cut_value+=cap[e];
  }

  Graph::NodeMap<bool> maxcut(G);
  max_flow_test.maxMinCut(maxcut); 
  int max_min_cut_value=0;
  for(G.first(e); G.valid(e); G.next(e)) {
    if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) 
      max_min_cut_value+=cap[e];
      }

  std::cout << "\n Checking the result: " <<std::endl;  
  std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl;
  std::cout << "Min cut value: "<< min_cut_value << std::endl;
  std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
  std::cout << "Max min cut value: "<< max_min_cut_value << 
    std::endl;

  if ( max_flow_test.flowValue() == min_cut_value &&
       min_cut_value == min_min_cut_value &&
       min_min_cut_value == max_min_cut_value )
    std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";  
  
  Graph::EdgeMap<int> flow2(G,0);
  PreflowRes<Graph, int> max_flow_test2(G, s, t, cap, flow2, 1);
  ts.reset();
  max_flow_test2.run();
  std::cout << "Elapsed time using the ResGraphWrapper: " << std::endl 
            << ts << std::endl;
  
  Graph::NodeMap<bool> mincut2(G);
  max_flow_test2.minMinCut(mincut2); 
  int min_min_cut_value2=0;
    for(G.first(e); G.valid(e); G.next(e)) {
    if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e];
  }

  Graph::NodeMap<bool> cut2(G);
  max_flow_test2.minCut(cut2); 
  int min_cut_value2=0;
  for(G.first(e); G.valid(e); G.next(e)) {
    if (cut2[G.tail(e)] && !cut2[G.head(e)]) 
      min_cut_value2+=cap[e];
  }

  Graph::NodeMap<bool> maxcut2(G);
  max_flow_test2.maxMinCut(maxcut2); 
  int max_min_cut_value2=0;
  for(G.first(e); G.valid(e); G.next(e)) {
    if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) 
      max_min_cut_value2+=cap[e];
      }
  
  std::cout << "\n Checking the result: " <<std::endl;  
  std::cout << "Flow value: "<< max_flow_test2.flowValue() << std::endl;
  std::cout << "Min cut value: "<< min_cut_value2 << std::endl;
  std::cout << "Min min cut value: "<< min_min_cut_value2 << std::endl;
  std::cout << "Max min cut value: "<< max_min_cut_value2 << 
    std::endl;  
  if ( max_flow_test.flowValue() == min_cut_value &&
       min_cut_value == min_min_cut_value &&
       min_min_cut_value == max_min_cut_value )
    std::cout << "They are equal! " <<std::endl<<"/n";  
  
  return 0;
}