benchmark/bench_tools.h
author ladanyi
Tue, 14 Jun 2005 23:21:31 +0000
changeset 1491 340514805e40
parent 979 b5fb023cdb7b
child 1689 f1795dafe42c
permissions -rw-r--r--
ignore generated files
alpar@711
     1
// -*- mode:C++ -*-
alpar@921
     2
#ifndef LEMON_BENCH_TEST_H
alpar@921
     3
#define LEMON_BENCH_TEST_H
alpar@711
     4
alpar@711
     5
#include<vector>
alpar@718
     6
#include<iostream>
alpar@718
     7
alpar@921
     8
#include<lemon/time_measure.h>
alpar@711
     9
alpar@711
    10
///An experimental typedef factory
alpar@711
    11
#define GRAPH_TYPEDEF_FACTORY(Graph) \
alpar@711
    12
   typedef typename Graph::   Node      Node;\
alpar@750
    13
   typedef typename Graph::   NodeIt    NodeIt;\
alpar@711
    14
   typedef typename Graph::   Edge      Edge;\
alpar@711
    15
   typedef typename Graph::   EdgeIt    EdgeIt;\
alpar@711
    16
   typedef typename Graph:: InEdgeIt  InEdgeIt;\
alpar@711
    17
   typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@711
    18
alpar@711
    19
#define GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph) \
alpar@711
    20
   typedef Graph::   Node      Node;\
alpar@750
    21
   typedef Graph::   NodeIt    NodeIt;\
alpar@711
    22
   typedef Graph::   Edge      Edge;\
alpar@711
    23
   typedef Graph::   EdgeIt    EdgeIt;\
alpar@711
    24
   typedef Graph:: InEdgeIt  InEdgeIt;\
alpar@711
    25
   typedef Graph::OutEdgeIt OutEdgeIt;
alpar@711
    26
 
alpar@711
    27
alpar@711
    28
///A primitive primtest
alpar@718
    29
alpar@718
    30
///\bug 2 is not a prime according to this function!
klao@979
    31
///
klao@979
    32
///\bug This function should go out of header file. I'm making it
klao@979
    33
/// inline for now.
klao@979
    34
inline bool isPrim(int n)
alpar@711
    35
{
alpar@711
    36
  if(n%2) {
alpar@711
    37
    for(int k=3;n/k>=k;k+=2)
alpar@711
    38
      if(!(n%k)) return false;
alpar@711
    39
    return true;
alpar@711
    40
  }
alpar@711
    41
  return false;
alpar@711
    42
}
alpar@711
    43
alpar@711
    44
///Finds the smallest prime not less then \c n.
klao@979
    45
klao@979
    46
///\bug This function should go out of header file. I'm making it
klao@979
    47
/// inline for now.
klao@979
    48
inline int nextPrim(int n)
alpar@711
    49
{
alpar@711
    50
  for(n+=!(n%2);!isPrim(n);n+=2) ;
alpar@711
    51
  return n;
alpar@711
    52
}
alpar@711
    53
alpar@711
    54
alpar@711
    55
/// Class to generate consecutive primes
alpar@711
    56
class Primes 
alpar@711
    57
{
alpar@711
    58
  std::vector<int> primes;
alpar@711
    59
  int n;
alpar@711
    60
  
alpar@711
    61
  bool isPrime(int m) 
alpar@711
    62
  {
alpar@711
    63
    for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false;
alpar@711
    64
    return true;
alpar@711
    65
  }
alpar@711
    66
public:
alpar@711
    67
  Primes() : n(1) {}
alpar@711
    68
  
alpar@711
    69
  int operator() ()
alpar@711
    70
    {
alpar@711
    71
      if(primes.size()==0) {
alpar@711
    72
	primes.push_back(2);
alpar@711
    73
	return 2;
alpar@711
    74
      }
alpar@711
    75
      else {
alpar@711
    76
	do n+=2; while(!isPrime(n));
alpar@711
    77
	primes.push_back(n);
alpar@711
    78
	return n;
alpar@711
    79
      }
alpar@711
    80
    }
alpar@711
    81
};
alpar@711
    82
alpar@921
    83
inline void PrintTime(char *ID,lemon::Timer &T) 
alpar@718
    84
{
alpar@921
    85
  lemon::TimeStamp S(T);
alpar@718
    86
  std::cout << ID << ' ' << S.getUserTime() << ' '
alpar@718
    87
	    << S.getSystemTime() << ' ' << S.getRealTime() << std::endl;
alpar@718
    88
}
alpar@718
    89
alpar@742
    90
alpar@742
    91
alpar@742
    92
///
alpar@742
    93
template<class Graph>
alpar@742
    94
void addHiperCube(Graph &G,int dim,std::vector<typename Graph::Node> &nodes)
alpar@742
    95
{
alpar@742
    96
  GRAPH_TYPEDEF_FACTORY(Graph);
alpar@718
    97
  
alpar@742
    98
  std::vector<int> bits(dim+1);
alpar@742
    99
  bits[0]=1;
alpar@742
   100
  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
alpar@742
   101
  
alpar@742
   102
  for(int i=0;i<bits[dim];i++) {
alpar@742
   103
    nodes.push_back(G.addNode());
alpar@742
   104
    for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
alpar@742
   105
  }
alpar@742
   106
}
alpar@742
   107
alpar@742
   108
///
alpar@742
   109
template<class Graph>
alpar@742
   110
void addBiDirHiperCube(Graph &G,int dim,std::vector<typename Graph::Node>&nodes)
alpar@742
   111
{
alpar@742
   112
  GRAPH_TYPEDEF_FACTORY(Graph);
alpar@742
   113
  
alpar@742
   114
  std::vector<int> bits(dim+1);
alpar@742
   115
  bits[0]=1;
alpar@742
   116
  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
alpar@742
   117
  
alpar@742
   118
  for(int i=0;i<bits[dim];i++) {
alpar@742
   119
    nodes.push_back(G.addNode());
alpar@742
   120
    for(int j=0;j<dim;j++) if(i&bits[j]) {
alpar@742
   121
      G.addEdge(nodes[i-bits[j]],nodes[i]);
alpar@742
   122
      G.addEdge(nodes[i],nodes[i-bits[j]]);
alpar@742
   123
    }
alpar@742
   124
    
alpar@742
   125
  }
alpar@742
   126
}  
alpar@711
   127
alpar@711
   128
#endif