1.1 --- a/src/benchmark/hcube.cc	Wed Jul 21 07:01:14 2004 +0000
     1.2 +++ b/src/benchmark/hcube.cc	Wed Jul 21 07:03:20 2004 +0000
     1.3 @@ -4,9 +4,7 @@
     1.4  #include<hugo/list_graph.h>
     1.5  #include<hugo/smart_graph.h>
     1.6  #include<hugo/dijkstra.h>
     1.7 -#include<hugo/time_measure.h>
     1.8 -#include<iostream>
     1.9 -//#include<../work/jacint/max_flow.h>
    1.10 +#include<../work/jacint/max_flow_no_stack.h>
    1.11  #include"bench_tools.h"
    1.12  
    1.13  using namespace std;
    1.14 @@ -23,7 +21,7 @@
    1.15    
    1.16    for(int i=0;i<bits[dim];i++) {
    1.17      nodes.push_back(G.addNode());
    1.18 -    for(j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
    1.19 +    for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
    1.20    }
    1.21  }
    1.22  
    1.23 @@ -46,6 +44,26 @@
    1.24    }
    1.25  }
    1.26  
    1.27 +inline int numOfOnes(int n,int dim)
    1.28 +{
    1.29 +  int s=0;
    1.30 +  for(int i=0;i<dim;i++) {
    1.31 +    s+=n%2;
    1.32 +    n>>=1;
    1.33 +  }
    1.34 +  return s;
    1.35 +}
    1.36 +
    1.37 +inline int numOfZeros(int n,int dim)
    1.38 +{
    1.39 +  int s=dim;
    1.40 +  for(int i=0;i<dim;i++) {
    1.41 +    s-=n&1;
    1.42 +    n>>=1;
    1.43 +  }
    1.44 +  return s;
    1.45 +}
    1.46 +
    1.47  int main(int argc, char *argv[])
    1.48  {
    1.49    //  typedef ListGraph Graph;
    1.50 @@ -65,13 +83,15 @@
    1.51    
    1.52    int dim=atoi(argv[1]);
    1.53    
    1.54 -  cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
    1.55 -       << dim*(1<<dim) << " edges):";
    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 -  cout << T;
    1.63 -  cout << "\nGenerating the lengths: ";
    1.64 +
    1.65 +  PrintTime("GENGRAPH",T);
    1.66 +
    1.67    T.reset();
    1.68    Graph::EdgeMap<int> map(G);
    1.69    {
    1.70 @@ -82,24 +102,30 @@
    1.71      for(int i=0;i<dim*(1<<dim);i++)
    1.72        //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
    1.73        map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
    1.74 +  
    1.75 +//     for(int i=0;i<(1<<dim);i++) {
    1.76 +//       int mul= (1<<(numOfZeros(i,dim)/4));
    1.77 +//       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
    1.78 +// 	map[e]*=mul;
    1.79 +//     }
    1.80    }
    1.81    
    1.82 -  cout << T;
    1.83 -  cout << "\nRunning Dijkstra: ";
    1.84 +  PrintTime("GENLENGTHS",T);
    1.85 +
    1.86    T.reset();
    1.87    {
    1.88      Dijkstra<Graph> Dij(G,map);
    1.89      Dij.run(nodes[0]);
    1.90    }
    1.91 -  cout << T;
    1.92 -//   cout << "\nRunning MaxFlow: ";
    1.93 -//   T.reset();
    1.94 -//   {
    1.95 -//    Graph::EdgeMap<int> flow(G);
    1.96 +  PrintTime("DIJKSTRA",T);
    1.97 +
    1.98 +  T.reset();
    1.99 +  {
   1.100 +   Graph::EdgeMap<int> flow(G);
   1.101     
   1.102 -//     MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
   1.103 -//     MF.run(MF.NO_FLOW);
   1.104 -//   }
   1.105 -//   cout << T;
   1.106 -  cout << "\n";
   1.107 +    MaxFlowNoStack<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
   1.108 +    MF.run(MF.NO_FLOW);
   1.109 +  }
   1.110 +  PrintTime("PREFLOW",T);
   1.111 +
   1.112  }