# HG changeset patch
# User marci
# Date 1091121651 0
# Node ID be163d94c109b5fdd9b97655997226f2fecb20db
# Parent  6ee2046cc210eaaee53d006bdef61740fbfb2077
a bug test for preflow with preflow_bug_8 dimacs file

diff -r 6ee2046cc210 -r be163d94c109 src/work/marci/preflow_bug.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci/preflow_bug.cc	Thu Jul 29 17:20:51 2004 +0000
@@ -0,0 +1,224 @@
+// -*- c++ -*-
+#include <iostream>
+#include <fstream>
+
+#include <sage_graph.h>
+#include <hugo/smart_graph.h>
+#include <hugo/dimacs.h>
+//#include <hugo/time_measure.h>
+//#include <graph_wrapper.h>
+#include <hugo/max_flow.h>
+//#include <preflow_res.h>
+#include <for_each_macros.h>
+#include <graph_concept.h>
+
+using std::cout;
+using std::endl;
+
+using namespace hugo;
+
+// Use a DIMACS min cost flow file as stdin.
+// read_dimacs_demo < dimacs_max_flow_file
+
+int main(int, char **) {
+
+  //typedef SageGraph MutableGraph;
+  //typedef FullFeatureGraphConcept Graph;
+  //typedef SmartGraph Graph;
+  typedef SageGraph Graph;
+  typedef Graph::Node Node;
+  typedef Graph::EdgeIt EdgeIt;
+
+  Graph g;
+
+  Node s, t;
+  Graph::EdgeMap<int> cap(g);
+  Graph::EdgeMap<int> flow(g); //0 flow
+  //readDimacs(std::cin, g, cap, s, t);
+  readDimacs(std::cin, g, cap, s, t, flow);
+//  Timer ts;
+  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
+    max_flow_test(g, s, t, cap, flow);
+  
+  Graph::NodeMap<bool> cut(g);
+
+  {
+    Graph::EdgeIt e;
+    for (g.first(e); g.valid(e); g.next(e))
+      cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e)) << " cap: " << cap[e] << " preflow: " << flow[e] << endl;
+  }
+  {
+    Graph::NodeIt n;
+    for (g.first(n); g.valid(n); g.next(n)) {
+      int a=0;
+      {
+	Graph::InEdgeIt e;
+	for (g.first(e, n); g.valid(e); g.next(e)) a+=flow[e];
+      }
+      {
+	Graph::OutEdgeIt e;
+	for (g.first(e, n); g.valid(e); g.next(e)) a-=flow[e];
+      }
+      cout << 1+g.id(n) << " excess: " << a << endl;
+    }
+  }
+
+
+  {
+//    std::cout << "preflow ..." << std::endl;
+//    ts.reset();
+    max_flow_test.preflowPhase1(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::PRE_FLOW);
+//    std::cout << "elapsed time: " << ts << std::endl;
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+    std::cout << "flow value 2: "<< max_flow_test.flowValue2() << std::endl;
+    max_flow_test.actMinCut(cut);
+    
+    Graph::EdgeIt e;
+    for (g.first(e); g.valid(e); g.next(e)) {
+      if (cut[g.tail(e)] && !cut[g.head(e)]) {
+	cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e)) 
+	     << "(forward edge) flow: " << flow[e] 
+	     << " cap: " << cap[e]<< endl;
+	if (flow[e]!=cap[e]) 
+	std::cout << "Slackness does not hold!" << std::endl;
+      }
+      if (!cut[g.tail(e)] && cut[g.head(e)]) {
+	cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e)) 
+	     << "(backward edge) flow: " << flow[e] << endl;
+	if (flow[e]!=0) 
+	std::cout << "Slackness does not hold!" << std::endl;
+      }
+    }
+    Graph::NodeIt n;
+    for (g.first(n); g.valid(n); g.next(n)) {
+      if (cut[n]) 
+	cout << "in cut: " << 1+g.id(n) << endl;
+    }
+  }
+
+//   {
+//     std::cout << "preflow ..." << std::endl;
+//     ts.reset();
+//     max_flow_test.run();
+//     std::cout << "elapsed time: " << ts << std::endl;
+//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+//     max_flow_test.actMinCut(cut);
+
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+//       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+// 	std::cout << "Slackness does not hold!" << std::endl;
+//       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+// 	std::cout << "Slackness does not hold!" << std::endl;
+//     }
+//   }
+
+//   {
+//     std::cout << "preflow ..." << std::endl;
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+//     ts.reset();
+//     max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
+//     std::cout << "elapsed time: " << ts << std::endl;
+//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+//       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+// 	std::cout << "Slackness does not hold!" << std::endl;
+//       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+// 	std::cout << "Slackness does not hold!" << std::endl;
+//     }
+//   }
+
+// //   {
+// //     std::cout << "wrapped preflow ..." << std::endl;
+// //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+// //     ts.reset();
+// //     pre_flow_res.run();
+// //     std::cout << "elapsed time: " << ts << std::endl;
+// //     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+// //   }
+
+//   {
+//     std::cout << "physical blocking flow augmentation ..." << std::endl;
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+//     ts.reset();
+//     int i=0;
+//     while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
+//     std::cout << "elapsed time: " << ts << std::endl;
+//     std::cout << "number of augmentation phases: " << i << std::endl; 
+//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
+
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+//       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+// 	std::cout << "Slackness does not hold!" << std::endl;
+//       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+// 	std::cout << "Slackness does not hold!" << std::endl;
+//     }
+//   }
+
+// //   {
+// //     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
+// //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+// //     ts.reset();
+// //     int i=0;
+// //     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
+// //     std::cout << "elapsed time: " << ts << std::endl;
+// //     std::cout << "number of augmentation phases: " << i << std::endl; 
+// //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+// //   }
+
+//   {
+//     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+//     ts.reset();
+//     int i=0;
+//     while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
+//     std::cout << "elapsed time: " << ts << std::endl;
+//     std::cout << "number of augmentation phases: " << i << std::endl; 
+//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
+
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+//       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+// 	std::cout << "Slackness does not hold!" << std::endl;
+//       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+// 	std::cout << "Slackness does not hold!" << std::endl;
+//     }
+//   }
+
+//   {
+//     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+//     ts.reset();
+//     int i=0;
+//     while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
+//     std::cout << "elapsed time: " << ts << std::endl;
+//     std::cout << "number of augmentation phases: " << i << std::endl; 
+//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
+
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+//       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+// 	std::cout << "Slackness does not hold!" << std::endl;
+//       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+// 	std::cout << "Slackness does not hold!" << std::endl;
+//     }
+//   }
+
+//   {
+//     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+//     ts.reset();
+//     int i=0;
+//     while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
+//     std::cout << "elapsed time: " << ts << std::endl;
+//     std::cout << "number of augmentation phases: " << i << std::endl; 
+//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
+
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+//       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+// 	std::cout << "Slackness does not hold!" << std::endl;
+//       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+// 	std::cout << "Slackness does not hold!" << std::endl;
+//     }
+//   }
+
+  return 0;
+}