diff -r 03c71d754990 -r 46a6311ceffa benchmark/min_cut.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/benchmark/min_cut.cc	Thu Jan 11 21:27:51 2007 +0000
@@ -0,0 +1,169 @@
+#include <lemon/list_graph.h>
+
+#include <lemon/hao_orlin.h>
+#include <lemon/nagamochi_ibaraki.h>
+#include <lemon/time_measure.h>
+
+using namespace lemon;
+
+#include "min_cut_graphs.h"
+
+
+void testRegUGraph();
+void testNoiUGraph();
+void testBikeWheelUGraph();
+
+int main() {
+  testRegUGraph();
+  testNoiUGraph();
+  testBikeWheelUGraph();
+  return 0;
+}
+
+//#define int long long
+
+
+int cutValue(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c,
+           const ListUGraph::NodeMap<bool>& n) {
+  int v = 0;
+  for (ListUGraph::UEdgeIt e(g); e != INVALID; ++e) {
+    if (n[g.source(e)] != n[g.target(e)]) {
+      v += c[e];
+    }
+  }
+  return v;
+}
+
+int cutSize(const ListUGraph& g, const ListUGraph::NodeMap<bool>& nm) {
+  int m = 0;
+  for (ListUGraph::NodeIt n(g); n != INVALID; ++n) {
+    if (nm[n]) {
+      ++m;
+    }
+  }
+  return m;
+}
+
+int testNI(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c) {
+  TimeReport tr("Nagamochi-Ibaraki : ");
+  NagamochiIbaraki<ListUGraph, ListUGraph::UEdgeMap<int> > alg(g, c);
+  alg.run();
+  ListUGraph::NodeMap<bool> n(g);
+  alg.minCut(n);
+  std::cout << "Check : " << cutValue(g, c, n) << ' '
+            << cutSize(g, n) << std::endl;
+  return alg.minCut();
+}
+
+int testHO(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c) {
+  TimeReport tr("Hao-Orlin : ");
+  HaoOrlin<ListUGraph, ListUGraph::UEdgeMap<int> > alg(g, c);
+  alg.init();
+  alg.calculateOut();
+  ListUGraph::NodeMap<bool> n(g);
+  alg.minCut(n);
+  std::cout << "Check : " << cutValue(g, c, n) << ' '
+            << cutSize(g, n) << std::endl;
+  return alg.minCut();
+}
+
+void testBikeWheelUGraph(int n) {
+  ListUGraph g;
+  ListUGraph::UEdgeMap<int> c(g);
+  genBikeWheelUGraph(g, c, n);
+  std::cout << "Node number : " << n << std::endl;
+  std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
+  std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
+}
+
+void testBikeWheelUGraph() {
+  std::cout << "BikeWheelUGraph : " << std::endl;
+  for (int k = 10; k <= 13; ++k) {
+    int n = 1 << k;
+    testBikeWheelUGraph(n);
+  }
+}
+
+void testNoiUGraph(int n, int d, int k, int p) {
+  ListUGraph g;
+  ListUGraph::UEdgeMap<int> c(g);
+  genNoiUGraph(g, c, n, d, k, p);
+  std::cout << "Node number : " << n << std::endl;
+  std::cout << "Density : " << d << std::endl;
+  std::cout << "Tight components : " << k << std::endl;
+  std::cout << "Scale : " << p << std::endl;
+  std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
+  std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
+}
+
+
+void testNoiUGraph() {
+  std::cout << "NoiUGraph : " << std::endl; 
+  std::cout << "Serial 1 : " << std::endl;
+  for (int n = 300; n <= 1000; n += 100) {
+    testNoiUGraph(n, 50, 1, n);
+  }
+  std::cout << "Serial 2 : " << std::endl;
+  for (int n = 300; n <= 1000; n += 100) {
+    testNoiUGraph(n, 50, 2, n);
+  }
+  std::cout << "Serial 3 : " << std::endl;
+  int da3[] = { 5, 10, 25, 50, 75, 100 };
+  int dn3 = sizeof(da3) / sizeof(da3[0]);
+  for (int d = 0; d < dn3; ++d) {
+    testNoiUGraph(1000, da3[d], 1, 1000);
+  }
+  std::cout << "Serial 4 : " << std::endl;
+  for (int d = 0; d < dn3; ++d) {
+    testNoiUGraph(1000, da3[d], 2, 1000);
+  }
+  std::cout << "Serial 5 : " << std::endl;
+  int ka5[] = {1, 2, 3, 5, 7, 10, 20, 30, 33, 35, 
+               40, 50, 100, 200, 300, 400, 500};
+  int kn5 = sizeof(ka5) / sizeof(ka5[0]);
+  for (int k = 0; k < kn5; ++k) {
+    testNoiUGraph(1000, 50, ka5[k], 1000);
+  }
+  std::cout << "Serial 6 : " << std::endl;
+  int pa6[] = { 5000, 2000, 1000, 500, 250, 100, 50, 10, 1};
+  int pn6 = sizeof(pa6) / sizeof(pa6[0]);
+  for (int p = 0; p < pn6; ++p) {
+    testNoiUGraph(1000, 50, 2, pa6[p]);
+  }  
+  
+}
+
+void testRegUGraph(int n, int d) {
+  ListUGraph g;
+  ListUGraph::UEdgeMap<int> c(g);
+  genRegUGraph(g, c, n, d);
+  std::cout << "Node number : " << n << std::endl;
+  std::cout << "Number of cycles : " << d << std::endl;
+  std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
+  std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
+}
+
+void testRegUGraph() {
+  std::cout << "RegUGraph : " << std::endl; 
+  std::cout << "Serial 1 : " << std::endl;
+  int da1[] = { 1, 3, 10, 33, 100, 333, 1000};
+  int dn1 = sizeof(da1) / sizeof(da1[0]);
+  for (int d = 0; d < dn1; ++d) {
+    testRegUGraph(1001, da1[d]);
+  }
+  std::cout << "Serial 2 : " << std::endl;
+  int na2[] = { 50, 100, 200, 400, 800};
+  int nn2 = sizeof(na2) / sizeof(na2[0]);
+  for (int n = 0; n < nn2; ++n) {
+    testRegUGraph(na2[n], 50);
+  }
+  std::cout << "Serial 3 : " << std::endl;
+  for (int n = 8; n <= 14; ++n) {
+    testRegUGraph(1 << n, 2);
+  }
+  std::cout << "Serial 4 : " << std::endl;
+  for (int n = 7; n <= 11; ++n) {
+    testRegUGraph(1 << n, 1 << (n - 4));
+  }  
+}
+