1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/benchmark/hcube.cc	Mon May 23 04:48:14 2005 +0000
     1.3 @@ -0,0 +1,106 @@
     1.4 +// -*- mode:C++ -*-
     1.5 +
     1.6 +#include<math.h>
     1.7 +#include<lemon/list_graph.h>
     1.8 +#include<lemon/smart_graph.h>
     1.9 +#include<lemon/dijkstra.h>
    1.10 +#include<lemon/preflow.h>
    1.11 +
    1.12 +#include"bench_tools.h"
    1.13 +
    1.14 +using namespace std;
    1.15 +using namespace lemon;
    1.16 +
    1.17 +inline int numOfOnes(int n,int dim)
    1.18 +{
    1.19 +  int s=0;
    1.20 +  for(int i=0;i<dim;i++) {
    1.21 +    s+=n%2;
    1.22 +    n>>=1;
    1.23 +  }
    1.24 +  return s;
    1.25 +}
    1.26 +
    1.27 +inline int numOfZeros(int n,int dim)
    1.28 +{
    1.29 +  int s=dim;
    1.30 +  for(int i=0;i<dim;i++) {
    1.31 +    s-=n&1;
    1.32 +    n>>=1;
    1.33 +  }
    1.34 +  return s;
    1.35 +}
    1.36 +
    1.37 +int main(int argc, char *argv[])
    1.38 +{
    1.39 +  //  typedef ListGraph Graph;
    1.40 +  typedef SmartGraph Graph;
    1.41 +
    1.42 +  ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
    1.43 +  GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
    1.44 +
    1.45 +  Graph G;
    1.46 +  
    1.47 +  Timer T;
    1.48 +  
    1.49 +  if(argc!=2) {
    1.50 +    cout << "Usage: " << argv[0] << " dim\n";
    1.51 +    return 1;
    1.52 +  }
    1.53 +  
    1.54 +  int dim=atoi(argv[1]);
    1.55 +  
    1.56 +//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
    1.57 +//        << dim*(1<<dim) << " edges):";
    1.58 +
    1.59 +  T.reset();
    1.60 +  vector<Node> nodes;
    1.61 +  addBiDirHiperCube(G,dim,nodes);
    1.62 +
    1.63 +  PrintTime("GENGRAPH",T);
    1.64 +
    1.65 +  T.reset();
    1.66 +  Graph::EdgeMap<int> map(G);
    1.67 +  for(int i=0;i<5;i++) {
    1.68 +    Primes P;
    1.69 +    for(int i=0;i<dim*(1<<dim);i++) P();
    1.70 +    
    1.71 +    //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
    1.72 +
    1.73 +    ///\todo It must have been commented out because of
    1.74 +    ///setToId
    1.75 +//     Edge te;
    1.76 +//     for(int i=0;i<dim*(1<<dim);i++) {
    1.77 +//       te.setToId(((long long int)(i)*93505)%(dim*(1<<dim)));
    1.78 +//       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
    1.79 +//       map[te]=P();
    1.80 +//     }
    1.81 +    
    1.82 +//     for(int i=0;i<(1<<dim);i++) {
    1.83 +//       int mul= (1<<(numOfZeros(i,dim)/4));
    1.84 +//       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
    1.85 +// 	map[e]*=mul;
    1.86 +//     }
    1.87 +  }
    1.88 +  
    1.89 +  PrintTime("GENLENGTHS",T);
    1.90 +
    1.91 +  T.reset();
    1.92 +  {
    1.93 +    Dijkstra<Graph> Dij(G,map);
    1.94 +    for(int i=0;i<10;i++)
    1.95 +      Dij.run(nodes[0]);
    1.96 +  }
    1.97 +  PrintTime("DIJKSTRA",T);
    1.98 +
    1.99 +  T.reset();
   1.100 +  {
   1.101 +   Graph::EdgeMap<int> flow(G);
   1.102 +   
   1.103 +    Preflow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
   1.104 +    for(int i=0;i<10;i++)
   1.105 +      MF.run(MF.NO_FLOW);
   1.106 +  }
   1.107 +  PrintTime("PREFLOW",T);
   1.108 +
   1.109 +}