source: lemon-0.x/src/work/jacint/preflow_excess_test.cc @ 1124:12623f7ecb37

/*
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_excess.h>
#include <time_measure.h>

using namespace lemon;

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  Are we slower?"
            <<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, 0 , 0);
  ts.reset();
  max_flow_test.run();
  std::cout << "Elapsed time from a preflow: " << 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.source(e)] && !mincut[G.target(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.source(e)] && !cut[G.target(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.source(e)] && !maxcut[G.target(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);
  Preflow<Graph, int> max_flow_test2(G, s, t, cap, flow2, 0 , 1);
  ts.reset();
  max_flow_test2.run();
  std::cout << "Elapsed time from a flow: " << 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.source(e)] && !mincut2[G.target(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.source(e)] && !cut2[G.target(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.source(e)] && !maxcut2[G.target(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;  





  Graph::EdgeMap<int> flow3(G,0);
  Preflow<Graph, int> max_flow_test3(G, s, t, cap, flow3, 1 , 1);
  ts.reset();
  max_flow_test3.run();
  std::cout << "Elapsed time from a const zero flow: " << std::endl 
            <<ts << std::endl;
  
  Graph::NodeMap<bool> mincut3(G);
  max_flow_test3.minMinCut(mincut3); 
  int min_min_cut_value3=0;
  for(G.first(e); G.valid(e); G.next(e)) {
    if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e];
  }

  Graph::NodeMap<bool> cut3(G);
  max_flow_test3.minCut(cut3); 
  int min_cut_value3=0;
  for(G.first(e); G.valid(e); G.next(e)) {
    if (cut3[G.source(e)] && !cut3[G.target(e)]) 
      min_cut_value3+=cap[e];
  }

  Graph::NodeMap<bool> maxcut3(G);
  max_flow_test3.maxMinCut(maxcut3); 
  int max_min_cut_value3=0;
  for(G.first(e); G.valid(e); G.next(e)) {
    if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) 
      max_min_cut_value3+=cap[e];
      }

  std::cout << "\n Checking the result: " <<std::endl;  
  std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl;
  std::cout << "Min cut value: "<< min_cut_value3 << std::endl;
  std::cout << "Min min cut value: "<< min_min_cut_value3 << std::endl;
  std::cout << "Max min cut value: "<< max_min_cut_value3 << 
    std::endl;

  if ( max_flow_test3.flowValue() == min_cut_value3 &&
       min_cut_value3 == min_min_cut_value3 &&
       min_min_cut_value3 == max_min_cut_value3 )
    std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";  
  
  return 0;
}