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

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.

File:

• src/benchmark/hcube.cc (modified) (6 diffs)

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);
+
 }