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

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

     2 #ifndef LEMON_BENCH_TEST_H

     3 #define LEMON_BENCH_TEST_H

     5 #include<vector>

     6 #include<iostream>

     8 #include<lemon/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 ///

    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 }

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

    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 }

    55 /// Class to generate consecutive primes

    56 class Primes

    57 {

    58   std::vector<int> primes;

    59   int n;

    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) {}

    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 };

    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 }

    92 ///

    93 template<class Graph>

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

    95 {

    96   GRAPH_TYPEDEF_FACTORY(Graph);

    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];

   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 }

   108 ///

   109 template<class Graph>

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

   111 {

   112   GRAPH_TYPEDEF_FACTORY(Graph);

   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];

   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     }

   125   }

   126 }

   128 #endif

author	hegyi
	Sun, 07 Aug 2005 22:14:59 +0000
changeset 1617	c17d61f77319
parent 979	b5fb023cdb7b
child 1689	f1795dafe42c
permissions	-rw-r--r--