src/benchmark/hcube.cc
author alpar
Tue, 20 Jul 2004 09:52:03 +0000
changeset 712 6f1abe741fb6
parent 708 429dfcbbf47d
child 718 75d36edc6bc4
permissions -rw-r--r--
src/becnhmark gets in the distro.
I hope it works well.
     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/time_measure.h>
     8 #include<iostream>
     9 //#include<../work/jacint/max_flow.h>
    10 #include"bench_tools.h"
    11 
    12 using namespace std;
    13 using namespace hugo;
    14 
    15 template<class Graph>
    16 void addHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
    17 {
    18   GRAPH_TYPEDEF_FACTORY(Graph);
    19   
    20   vector<int> bits(dim+1);
    21   bits[0]=1;
    22   for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
    23   
    24   for(int i=0;i<bits[dim];i++) {
    25     nodes.push_back(G.addNode());
    26     for(j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
    27   }
    28 }
    29 
    30 template<class Graph>
    31 void addBiDirHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
    32 {
    33   GRAPH_TYPEDEF_FACTORY(Graph);
    34   
    35   vector<int> bits(dim+1);
    36   bits[0]=1;
    37   for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
    38   
    39   for(int i=0;i<bits[dim];i++) {
    40     nodes.push_back(G.addNode());
    41     for(int j=0;j<dim;j++) if(i&bits[j]) {
    42       G.addEdge(nodes[i-bits[j]],nodes[i]);
    43       G.addEdge(nodes[i],nodes[i-bits[j]]);
    44     }
    45     
    46   }
    47 }
    48 
    49 int main(int argc, char *argv[])
    50 {
    51   //  typedef ListGraph Graph;
    52   typedef SmartGraph Graph;
    53 
    54   ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
    55   GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
    56 
    57   Graph G;
    58   
    59   Timer T;
    60   
    61   if(argc!=2) {
    62     cout << "Usage: " << argv[0] << " dim\n";
    63     return 1;
    64   }
    65   
    66   int dim=atoi(argv[1]);
    67   
    68   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
    69        << dim*(1<<dim) << " edges):";
    70 
    71   vector<Node> nodes;
    72   addBiDirHiperCube(G,dim,nodes);
    73   cout << T;
    74   cout << "\nGenerating the lengths: ";
    75   T.reset();
    76   Graph::EdgeMap<int> map(G);
    77   {
    78     Primes P;
    79     for(int i=0;i<dim*(1<<dim);i++) P();
    80     
    81     //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
    82     for(int i=0;i<dim*(1<<dim);i++)
    83       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
    84       map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
    85   }
    86   
    87   cout << T;
    88   cout << "\nRunning Dijkstra: ";
    89   T.reset();
    90   {
    91     Dijkstra<Graph> Dij(G,map);
    92     Dij.run(nodes[0]);
    93   }
    94   cout << T;
    95 //   cout << "\nRunning MaxFlow: ";
    96 //   T.reset();
    97 //   {
    98 //    Graph::EdgeMap<int> flow(G);
    99    
   100 //     MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
   101 //     MF.run(MF.NO_FLOW);
   102 //   }
   103 //   cout << T;
   104   cout << "\n";
   105 }