1.1 --- a/src/work/jacint/makefile	Thu Jul 29 17:20:51 2004 +0000
     1.2 +++ b/src/work/jacint/makefile	Thu Jul 29 17:23:55 2004 +0000
     1.3 @@ -1,3 +1,3 @@
     1.4 -BINARIES = max_flow_test
     1.5 +BINARIES = max_flow_bug
     1.6  INCLUDEDIRS= -I../../include -I../.. -I.. -I../{klao,marci,jacint,alpar,johanna,akos}
     1.7  include ../makefile 

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/work/jacint/max_flow_bug.cc	Thu Jul 29 17:23:55 2004 +0000
     2.3 @@ -0,0 +1,163 @@
     2.4 +#include <iostream>
     2.5 +
     2.6 +//#include <hugo/list_graph.h>
     2.7 +#include <sage_graph.h>
     2.8 +#include <hugo/dimacs.h>
     2.9 +#include <hugo/max_flow.h>
    2.10 +//#include <max_flow_no_stack.h>
    2.11 +#include <hugo/time_measure.h>
    2.12 +
    2.13 +using namespace hugo;
    2.14 +
    2.15 +int main(int, char **) {
    2.16 + 
    2.17 +//  typedef ListGraph Graph;
    2.18 +  typedef SageGraph Graph;
    2.19 +  
    2.20 +  typedef Graph::Node Node;
    2.21 +  typedef Graph::EdgeIt EdgeIt;
    2.22 +
    2.23 +  Graph G;
    2.24 +  Node s, t;
    2.25 +  Graph::EdgeMap<int> cap(G);
    2.26 +  Graph::EdgeMap<int> flow(G,0);
    2.27 +
    2.28 +  readDimacs(std::cin, G, cap, s, t, flow);
    2.29 +  Timer ts;
    2.30 +  
    2.31 +  std::cout <<
    2.32 +    "\n  Running max_flow.h on a graph with " << 
    2.33 +    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
    2.34 +	   << std::endl<<std::endl;
    2.35 +
    2.36 +
    2.37 +  MaxFlow<Graph, int> max_flow_test_no_stack(G, s, t, cap, flow);
    2.38 +  ts.reset();
    2.39 +  max_flow_test_no_stack.preflowPhase1(MaxFlow<Graph, int>::PRE_FLOW);
    2.40 +  std::cout << "Elapsed time of run() without stack: " << std::endl 
    2.41 +	    <<ts << std::endl;
    2.42 +  
    2.43 +  Graph::NodeMap<bool> mincut(G);
    2.44 +  max_flow_test_no_stack.minMinCut(mincut); 
    2.45 +  int min_min_cut_value=0;
    2.46 +  EdgeIt e;
    2.47 +  for(G.first(e); G.valid(e); G.next(e)) {
    2.48 +    if (mincut[G.tail(e)] && !mincut[G.head(e)]) min_min_cut_value+=cap[e];
    2.49 +  }
    2.50 +
    2.51 +  Graph::NodeMap<bool> cut(G);
    2.52 +  max_flow_test_no_stack.minCut(cut); 
    2.53 +  int min_cut_value=0;
    2.54 +  for(G.first(e); G.valid(e); G.next(e)) {
    2.55 +    if (cut[G.tail(e)] && !cut[G.head(e)]) 
    2.56 +      min_cut_value+=cap[e];
    2.57 +  }
    2.58 +
    2.59 +  Graph::NodeMap<bool> maxcut(G);
    2.60 +  max_flow_test_no_stack.maxMinCut(maxcut); 
    2.61 +  int max_min_cut_value=0;
    2.62 +  for(G.first(e); G.valid(e); G.next(e)) {
    2.63 +    if (maxcut[G.tail(e)] && !maxcut[G.head(e)]) 
    2.64 +      max_min_cut_value+=cap[e];
    2.65 +      }
    2.66 +
    2.67 +  std::cout << "\n Checking the result without stack: " <<std::endl;  
    2.68 +  std::cout << "Flow value: "<< max_flow_test_no_stack.flowValue() << std::endl;
    2.69 +  std::cout << "Min cut value: "<< min_cut_value << std::endl;
    2.70 +  std::cout << "Min min cut value: "<< min_min_cut_value << std::endl;
    2.71 +  std::cout << "Max min cut value: "<< max_min_cut_value << 
    2.72 +    std::endl;
    2.73 +
    2.74 +  if ( max_flow_test_no_stack.flowValue() == min_cut_value &&
    2.75 +       min_cut_value == min_min_cut_value &&
    2.76 +       min_min_cut_value == max_min_cut_value )
    2.77 +    std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";  
    2.78 +
    2.79 +  /*
    2.80 +
    2.81 +  Graph::EdgeMap<int> flow2(G,0);
    2.82 +  std::cout << "Calling resetFlow() " << std::endl 
    2.83 +	    << ts << std::endl;
    2.84 +  max_flow_test.resetFlow(flow2);  
    2.85 +  ts.reset();
    2.86 +  max_flow_test.preflow(max_flow_test.PRE_FLOW);
    2.87 +  std::cout << "Elapsed time of preflow(PRE_FLOW) starting from the zero flow: " << std::endl 
    2.88 +	    << ts << std::endl;
    2.89 +  
    2.90 +  Graph::NodeMap<bool> mincut2(G);
    2.91 +  max_flow_test.minMinCut(mincut2); 
    2.92 +  int min_min_cut_value2=0;
    2.93 +    for(G.first(e); G.valid(e); G.next(e)) {
    2.94 +    if (mincut2[G.tail(e)] && !mincut2[G.head(e)]) min_min_cut_value2+=cap[e];
    2.95 +  }
    2.96 +
    2.97 +  Graph::NodeMap<bool> cut2(G);
    2.98 +  max_flow_test.minCut(cut2); 
    2.99 +  int min_cut_value2=0;
   2.100 +  for(G.first(e); G.valid(e); G.next(e)) {
   2.101 +    if (cut2[G.tail(e)] && !cut2[G.head(e)]) 
   2.102 +      min_cut_value2+=cap[e];
   2.103 +  }
   2.104 +
   2.105 +  Graph::NodeMap<bool> maxcut2(G);
   2.106 +  max_flow_test.maxMinCut(maxcut2); 
   2.107 +  int max_min_cut_value2=0;
   2.108 +  for(G.first(e); G.valid(e); G.next(e)) {
   2.109 +    if (maxcut2[G.tail(e)] && !maxcut2[G.head(e)]) 
   2.110 +      max_min_cut_value2+=cap[e];
   2.111 +      }
   2.112 +  
   2.113 +  std::cout << "\n Checking the result: " <<std::endl;  
   2.114 +  std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl;
   2.115 +  std::cout << "Min cut value: "<< min_cut_value2 << std::endl;
   2.116 +  std::cout << "Min min cut value: "<< min_min_cut_value2 << std::endl;
   2.117 +  std::cout << "Max min cut value: "<< max_min_cut_value2 << 
   2.118 +    std::endl;  
   2.119 +  if ( max_flow_test.flowValue() == min_cut_value &&
   2.120 +       min_cut_value == min_min_cut_value &&
   2.121 +       min_min_cut_value == max_min_cut_value )
   2.122 +    std::cout << "They are equal! " <<std::endl;  
   2.123 +
   2.124 +
   2.125 +  MaxFlow<Graph, int> max_flow_test3(G, s, t, cap, flow2);
   2.126 +  max_flow_test3.run(max_flow_test3.GEN_FLOW);
   2.127 +  std::cout << "Calling run(GEN_FLOW) from the max flow found before. " <<std::endl;  
   2.128 +  
   2.129 +  Graph::NodeMap<bool> mincut3(G);
   2.130 +  max_flow_test3.minMinCut(mincut3); 
   2.131 +  int min_min_cut_value3=0;
   2.132 +  for(G.first(e); G.valid(e); G.next(e)) {
   2.133 +    if (mincut3[G.tail(e)] && !mincut3[G.head(e)]) min_min_cut_value3+=cap[e];
   2.134 +  }
   2.135 +
   2.136 +  Graph::NodeMap<bool> cut3(G);
   2.137 +  max_flow_test3.minCut(cut3); 
   2.138 +  int min_cut_value3=0;
   2.139 +  for(G.first(e); G.valid(e); G.next(e)) {
   2.140 +    if (cut3[G.tail(e)] && !cut3[G.head(e)]) 
   2.141 +      min_cut_value3+=cap[e];
   2.142 +  }
   2.143 +
   2.144 +  Graph::NodeMap<bool> maxcut3(G);
   2.145 +  max_flow_test3.maxMinCut(maxcut3); 
   2.146 +  int max_min_cut_value3=0;
   2.147 +  for(G.first(e); G.valid(e); G.next(e)) {
   2.148 +    if (maxcut3[G.tail(e)] && !maxcut3[G.head(e)]) 
   2.149 +      max_min_cut_value3+=cap[e];
   2.150 +  }
   2.151 +
   2.152 +  std::cout << "\n Checking the result: " <<std::endl;  
   2.153 +  std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl;
   2.154 +  std::cout << "Min cut value: "<< min_cut_value3 << std::endl;
   2.155 +  std::cout << "Min min cut value: "<< min_min_cut_value3 << std::endl;
   2.156 +  std::cout << "Max min cut value: "<< max_min_cut_value3 << 
   2.157 +    std::endl;
   2.158 +
   2.159 +  if ( max_flow_test3.flowValue() == min_cut_value3 &&
   2.160 +       min_cut_value3 == min_min_cut_value3 &&
   2.161 +       min_min_cut_value3 == max_min_cut_value3 )
   2.162 +    std::cout << "They are equal! " <<std::endl<< std::endl<<"\n";  
   2.163 +  */
   2.164 +  
   2.165 +  return 0;
   2.166 +}