src/benchmark/hcube.cc
author alpar
Mon, 06 Sep 2004 08:21:42 +0000
changeset 804 6874a72dbdc5
parent 729 a9b1c49440f7
child 840 10002fa8847a
permissions -rw-r--r--
One more thing to do...
     1 // -*- mode:C++ -*-
     2 
     3 #include<math.h>
     4 #include<hugo/list_graph.h>
     5 #include<hugo/smart_graph.h>
     6 #include<hugo/dijkstra.h>
     7 #include<hugo/max_flow.h>
     8 
     9 #include"bench_tools.h"
    10 
    11 using namespace std;
    12 using namespace hugo;
    13 
    14 inline int numOfOnes(int n,int dim)
    15 {
    16   int s=0;
    17   for(int i=0;i<dim;i++) {
    18     s+=n%2;
    19     n>>=1;
    20   }
    21   return s;
    22 }
    23 
    24 inline int numOfZeros(int n,int dim)
    25 {
    26   int s=dim;
    27   for(int i=0;i<dim;i++) {
    28     s-=n&1;
    29     n>>=1;
    30   }
    31   return s;
    32 }
    33 
    34 int main(int argc, char *argv[])
    35 {
    36   //  typedef ListGraph Graph;
    37   typedef SmartGraph Graph;
    38 
    39   ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
    40   GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
    41 
    42   Graph G;
    43   
    44   Timer T;
    45   
    46   if(argc!=2) {
    47     cout << "Usage: " << argv[0] << " dim\n";
    48     return 1;
    49   }
    50   
    51   int dim=atoi(argv[1]);
    52   
    53 //   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
    54 //        << dim*(1<<dim) << " edges):";
    55 
    56   T.reset();
    57   vector<Node> nodes;
    58   addBiDirHiperCube(G,dim,nodes);
    59 
    60   PrintTime("GENGRAPH",T);
    61 
    62   T.reset();
    63   Graph::EdgeMap<int> map(G);
    64   for(int i=0;i<5;i++) {
    65     Primes P;
    66     for(int i=0;i<dim*(1<<dim);i++) P();
    67     
    68     //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
    69     for(int i=0;i<dim*(1<<dim);i++)
    70       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
    71       map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
    72   
    73 //     for(int i=0;i<(1<<dim);i++) {
    74 //       int mul= (1<<(numOfZeros(i,dim)/4));
    75 //       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
    76 // 	map[e]*=mul;
    77 //     }
    78   }
    79   
    80   PrintTime("GENLENGTHS",T);
    81 
    82   T.reset();
    83   {
    84     Dijkstra<Graph> Dij(G,map);
    85     for(int i=0;i<10;i++)
    86       Dij.run(nodes[0]);
    87   }
    88   PrintTime("DIJKSTRA",T);
    89 
    90   T.reset();
    91   {
    92    Graph::EdgeMap<int> flow(G);
    93    
    94     MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
    95     for(int i=0;i<10;i++)
    96       MF.run(MF.NO_FLOW);
    97   }
    98   PrintTime("PREFLOW",T);
    99 
   100 }