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