lemon-0.x: src/benchmark/bench_tools.h@a4bb28813570

     1 // -*- mode:C++ -*-

     2 #ifndef HUGO_BENCH_TEST_H

     3 #define HUGO_BENCH_TEST_H

     5 #include<vector>

     6 #include<iostream>

     8 #include<hugo/time_measure.h>

    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;

    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;

    28 ///A primitive primtest

    30 ///\bug 2 is not a prime according to this function!

    31 bool isPrim(int n)

    32 {

    33   if(n%2) {

    34     for(int k=3;n/k>=k;k+=2)

    35       if(!(n%k)) return false;

    36     return true;

    37   }

    38   return false;

    39 }

    41 ///Finds the smallest prime not less then \c n.

    42 int nextPrim(int n)

    43 {

    44   for(n+=!(n%2);!isPrim(n);n+=2) ;

    45   return n;

    46 }

    49 /// Class to generate consecutive primes

    50 class Primes

    51 {

    52   std::vector<int> primes;

    53   int n;

    55   bool isPrime(int m)

    56   {

    57     for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false;

    58     return true;

    59   }

    60 public:

    61   Primes() : n(1) {}

    63   int operator() ()

    64     {

    65       if(primes.size()==0) {

    66 	primes.push_back(2);

    67 	return 2;

    68       }

    69       else {

    70 	do n+=2; while(!isPrime(n));

    71 	primes.push_back(n);

    72 	return n;

    73       }

    74     }

    75 };

    77 inline void PrintTime(char *ID,hugo::Timer &T)

    78 {

    79   hugo::TimeStamp S(T);

    80   std::cout << ID << ' ' << S.getUserTime() << ' '

    81 	    << S.getSystemTime() << ' ' << S.getRealTime() << std::endl;

    82 }

    86 ///

    87 template<class Graph>

    88 void addHiperCube(Graph &G,int dim,std::vector<typename Graph::Node> &nodes)

    89 {

    90   GRAPH_TYPEDEF_FACTORY(Graph);

    92   std::vector<int> bits(dim+1);

    93   bits[0]=1;

    94   for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];

    96   for(int i=0;i<bits[dim];i++) {

    97     nodes.push_back(G.addNode());

    98     for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);

    99   }

   100 }

   102 ///

   103 template<class Graph>

   104 void addBiDirHiperCube(Graph &G,int dim,std::vector<typename Graph::Node>&nodes)

   105 {

   106   GRAPH_TYPEDEF_FACTORY(Graph);

   108   std::vector<int> bits(dim+1);

   109   bits[0]=1;

   110   for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];

   112   for(int i=0;i<bits[dim];i++) {

   113     nodes.push_back(G.addNode());

   114     for(int j=0;j<dim;j++) if(i&bits[j]) {

   115       G.addEdge(nodes[i-bits[j]],nodes[i]);

   116       G.addEdge(nodes[i],nodes[i-bits[j]]);

   117     }

   119   }

   120 }

   122 #endif

author	alpar
	Mon, 13 Sep 2004 17:20:03 +0000
changeset 842	a4bb28813570
parent 742	235fd36336b7
child 921	818510fa3d99
permissions	-rw-r--r--