src/benchmark/hcube.cc
author alpar
Thu, 22 Jul 2004 14:29:20 +0000
changeset 730 af375858f17c
parent 718 75d36edc6bc4
child 742 235fd36336b7
permissions -rw-r--r--
Custom made INSTALL file (will be sometime).
alpar@708
     1
// -*- mode:C++ -*-
alpar@708
     2
alpar@708
     3
#include<math.h>
alpar@708
     4
#include<hugo/list_graph.h>
alpar@708
     5
#include<hugo/smart_graph.h>
alpar@708
     6
#include<hugo/dijkstra.h>
alpar@729
     7
#include<hugo/max_flow.h>
alpar@729
     8
alpar@711
     9
#include"bench_tools.h"
alpar@708
    10
alpar@708
    11
using namespace std;
alpar@708
    12
using namespace hugo;
alpar@708
    13
alpar@708
    14
template<class Graph>
alpar@708
    15
void addHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
alpar@708
    16
{
alpar@708
    17
  GRAPH_TYPEDEF_FACTORY(Graph);
alpar@708
    18
  
alpar@708
    19
  vector<int> bits(dim+1);
alpar@708
    20
  bits[0]=1;
alpar@708
    21
  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
alpar@708
    22
  
alpar@708
    23
  for(int i=0;i<bits[dim];i++) {
alpar@708
    24
    nodes.push_back(G.addNode());
alpar@718
    25
    for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
alpar@708
    26
  }
alpar@708
    27
}
alpar@708
    28
alpar@708
    29
template<class Graph>
alpar@708
    30
void addBiDirHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
alpar@708
    31
{
alpar@708
    32
  GRAPH_TYPEDEF_FACTORY(Graph);
alpar@708
    33
  
alpar@708
    34
  vector<int> bits(dim+1);
alpar@708
    35
  bits[0]=1;
alpar@708
    36
  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
alpar@708
    37
  
alpar@708
    38
  for(int i=0;i<bits[dim];i++) {
alpar@708
    39
    nodes.push_back(G.addNode());
alpar@708
    40
    for(int j=0;j<dim;j++) if(i&bits[j]) {
alpar@708
    41
      G.addEdge(nodes[i-bits[j]],nodes[i]);
alpar@708
    42
      G.addEdge(nodes[i],nodes[i-bits[j]]);
alpar@708
    43
    }
alpar@708
    44
    
alpar@708
    45
  }
alpar@708
    46
}
alpar@708
    47
alpar@718
    48
inline int numOfOnes(int n,int dim)
alpar@718
    49
{
alpar@718
    50
  int s=0;
alpar@718
    51
  for(int i=0;i<dim;i++) {
alpar@718
    52
    s+=n%2;
alpar@718
    53
    n>>=1;
alpar@718
    54
  }
alpar@718
    55
  return s;
alpar@718
    56
}
alpar@718
    57
alpar@718
    58
inline int numOfZeros(int n,int dim)
alpar@718
    59
{
alpar@718
    60
  int s=dim;
alpar@718
    61
  for(int i=0;i<dim;i++) {
alpar@718
    62
    s-=n&1;
alpar@718
    63
    n>>=1;
alpar@718
    64
  }
alpar@718
    65
  return s;
alpar@718
    66
}
alpar@718
    67
alpar@708
    68
int main(int argc, char *argv[])
alpar@708
    69
{
alpar@708
    70
  //  typedef ListGraph Graph;
alpar@708
    71
  typedef SmartGraph Graph;
alpar@708
    72
alpar@708
    73
  ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
alpar@708
    74
  GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
alpar@708
    75
alpar@708
    76
  Graph G;
alpar@708
    77
  
alpar@708
    78
  Timer T;
alpar@708
    79
  
alpar@708
    80
  if(argc!=2) {
alpar@708
    81
    cout << "Usage: " << argv[0] << " dim\n";
alpar@708
    82
    return 1;
alpar@708
    83
  }
alpar@708
    84
  
alpar@708
    85
  int dim=atoi(argv[1]);
alpar@708
    86
  
alpar@718
    87
//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
alpar@718
    88
//        << dim*(1<<dim) << " edges):";
alpar@708
    89
alpar@718
    90
  T.reset();
alpar@708
    91
  vector<Node> nodes;
alpar@708
    92
  addBiDirHiperCube(G,dim,nodes);
alpar@718
    93
alpar@718
    94
  PrintTime("GENGRAPH",T);
alpar@718
    95
alpar@708
    96
  T.reset();
alpar@708
    97
  Graph::EdgeMap<int> map(G);
alpar@729
    98
  for(int i=0;i<5;i++) {
alpar@708
    99
    Primes P;
alpar@708
   100
    for(int i=0;i<dim*(1<<dim);i++) P();
alpar@708
   101
    
alpar@708
   102
    //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
alpar@708
   103
    for(int i=0;i<dim*(1<<dim);i++)
alpar@708
   104
      //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
alpar@708
   105
      map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
alpar@718
   106
  
alpar@718
   107
//     for(int i=0;i<(1<<dim);i++) {
alpar@718
   108
//       int mul= (1<<(numOfZeros(i,dim)/4));
alpar@718
   109
//       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
alpar@718
   110
// 	map[e]*=mul;
alpar@718
   111
//     }
alpar@708
   112
  }
alpar@708
   113
  
alpar@718
   114
  PrintTime("GENLENGTHS",T);
alpar@718
   115
alpar@708
   116
  T.reset();
alpar@708
   117
  {
alpar@708
   118
    Dijkstra<Graph> Dij(G,map);
alpar@729
   119
    for(int i=0;i<10;i++)
alpar@729
   120
      Dij.run(nodes[0]);
alpar@708
   121
  }
alpar@718
   122
  PrintTime("DIJKSTRA",T);
alpar@718
   123
alpar@718
   124
  T.reset();
alpar@718
   125
  {
alpar@718
   126
   Graph::EdgeMap<int> flow(G);
alpar@708
   127
   
alpar@729
   128
    MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
alpar@729
   129
    for(int i=0;i<10;i++)
alpar@729
   130
      MF.run(MF.NO_FLOW);
alpar@718
   131
  }
alpar@718
   132
  PrintTime("PREFLOW",T);
alpar@718
   133
alpar@708
   134
}