Changeset 718:75d36edc6bc4 in lemon-0.x for src/benchmark

Timestamp:

07/21/04 09:03:20 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@970

Message:

Ready to run the first test series.

Location:

src/benchmark

Files:

• bench_tools.h (modified) (3 diffs)
• benchmark (added)
• graph-bench.cc (modified) (4 diffs)
• hcube.cc (modified) (6 diffs)

src/benchmark/bench_tools.h

@@ -4 +4 @@
 
 #include<vector>
+#include<iostream>
+
+#include<hugo/time_measure.h>
 
 ///An experimental typedef factory
@@ -24 +27 @@
 
 ///A primitive primtest
+
+///\bug 2 is not a prime according to this function!
 bool isPrim(int n)
 {
@@ -70 +75 @@
 };
 
+inline void PrintTime(char *ID,hugo::Timer &T) 
+{
+  hugo::TimeStamp S(T);
+  std::cout << ID << ' ' << S.getUserTime() << ' '
+            << S.getSystemTime() << ' ' << S.getRealTime() << std::endl;
+}
+
+  
 
 #endif

src/benchmark/graph-bench.cc

@@ -1 +1 @@
 #include<math.h>
 #include<hugo/list_graph.h>
-#include<hugo/time_measure.h>
-#include<iostream>
 
 #include"bench_tools.h"
@@ -29 +27 @@
   std::vector<Edge> equ(rat);
   
-  unsigned long long int count;
+  long long int count;
   
   for(count=0;count<rat;count++) {
@@ -39 +37 @@
     equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);
   }
-  std::cout << "Added " << count
-            << " ( " << n << "^2 * " << rat << " ) edges\n";
+//   std::cout << "Added " << count
+//          << " ( " << n << "^2 * " << rat << " ) edges\n";
+
+
   //  for(int i=0;1;i++) ;
 }
@@ -46 +46 @@
 int main()
 {
-  std::cout << "START: n="  << nextPrim(1000) << " rat="
-            << nextPrim(300) << " p=" << nextPrim(100) << '\n';
   hugo::Timer T;
   makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
-  std::cout << T  << '\n';
-  std::cout << "START: n="  << nextPrim(1000) << " rat="
-            << nextPrim(300) << " p=" << nextPrim(100) << '\n';
+  
+  PrintTime("BIG",T);
   T.reset();
   makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));
-  std::cout << T  << '\n';
+
+  PrintTime("SMALL",T);
 }

src/benchmark/hcube.cc

@@ -5 +5 @@
 #include<hugo/smart_graph.h>
 #include<hugo/dijkstra.h>
-#include<hugo/time_measure.h>
-#include<iostream>
-//#include<../work/jacint/max_flow.h>
+#include<../work/jacint/max_flow_no_stack.h>
 #include"bench_tools.h"
 
@@ -24 +22 @@
   for(int i=0;i<bits[dim];i++) {
     nodes.push_back(G.addNode());
-    for(j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
+    for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
   }
 }
@@ -47 +45 @@
 }
 
+inline int numOfOnes(int n,int dim)
+{
+  int s=0;
+  for(int i=0;i<dim;i++) {
+    s+=n%2;
+    n>>=1;
+  }
+  return s;
+}
+
+inline int numOfZeros(int n,int dim)
+{
+  int s=dim;
+  for(int i=0;i<dim;i++) {
+    s-=n&1;
+    n>>=1;
+  }
+  return s;
+}
+
 int main(int argc, char *argv[])
 {
@@ -66 +84 @@
   int dim=atoi(argv[1]);
   
-  cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
-       << dim*(1<<dim) << " edges):";
+//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
+//        << dim*(1<<dim) << " edges):";
 
+  T.reset();
   vector<Node> nodes;
   addBiDirHiperCube(G,dim,nodes);
-  cout << T;
-  cout << "\nGenerating the lengths: ";
+
+  PrintTime("GENGRAPH",T);
+
   T.reset();
   Graph::EdgeMap<int> map(G);
@@ -83 +103 @@
       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
       map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
+  
+//     for(int i=0;i<(1<<dim);i++) {
+//       int mul= (1<<(numOfZeros(i,dim)/4));
+//       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
+//      map[e]*=mul;
+//     }
   }
   
-  cout << T;
-  cout << "\nRunning Dijkstra: ";
+  PrintTime("GENLENGTHS",T);
+
   T.reset();
   {
@@ -92 +118 @@
     Dij.run(nodes[0]);
   }
-  cout << T;
-//   cout << "\nRunning MaxFlow: ";
-//   T.reset();
-//   {
-//    Graph::EdgeMap<int> flow(G);
+  PrintTime("DIJKSTRA",T);
+
+  T.reset();
+  {
+   Graph::EdgeMap<int> flow(G);
    
-//     MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
-//     MF.run(MF.NO_FLOW);
-//   }
-//   cout << T;
-  cout << "\n";
+    MaxFlowNoStack<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
+    MF.run(MF.NO_FLOW);
+  }
+  PrintTime("PREFLOW",T);
+
 }