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