lemon-0.x: benchmark/bench_tools.h@cb082cdf3667

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

     2 #ifndef LEMON_BENCH_TEST_H

     3 #define LEMON_BENCH_TEST_H

     5 #include<vector>

     6 #include<iostream>

     8 #include<lemon/graph_utils.h>

     9 #include<lemon/time_measure.h>

    11 ///A primitive primtest

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

    14 ///

    15 ///\bug This function should go out of header file. I'm making it

    16 /// inline for now.

    17 inline bool isPrim(int n)

    18 {

    19   if(n%2) {

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

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

    22     return true;

    23   }

    24   return false;

    25 }

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

    29 ///\bug This function should go out of header file. I'm making it

    30 /// inline for now.

    31 inline int nextPrim(int n)

    32 {

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

    34   return n;

    35 }

    38 /// Class to generate consecutive primes

    39 class Primes

    40 {

    41   std::vector<int> primes;

    42   int n;

    44   bool isPrime(int m)

    45   {

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

    47     return true;

    48   }

    49 public:

    50   Primes() : n(1) {}

    52   int operator() ()

    53     {

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

    55 	primes.push_back(2);

    56 	return 2;

    57       }

    58       else {

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

    60 	primes.push_back(n);

    61 	return n;

    62       }

    63     }

    64 };

    66 inline void PrintTime(char *ID,lemon::Timer &T)

    67 {

    68   lemon::TimeStamp S(T);

    69   std::cout << ID << ' ' << S.userTime() << ' '

    70 	    << S.systemTime() << ' ' << S.realTime() << std::endl;

    71 }

    75 ///

    76 template<class Graph>

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

    78 {

    79   GRAPH_TYPEDEFS(typename Graph);

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

    82   bits[0]=1;

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

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

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

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

    88   }

    89 }

    91 ///

    92 template<class Graph>

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

    94 {

    95   GRAPH_TYPEDEFS(typename Graph);

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

    98   bits[0]=1;

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

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

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

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

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

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

   106     }

   108   }

   109 }

   111 #endif

author	hegyi
	Mon, 21 Nov 2005 18:03:20 +0000
changeset 1823	cb082cdf3667
parent 1689	f1795dafe42c
child 1956	a055123339d5
permissions	-rw-r--r--