alpar@1956: /* -*- C++ -*-
alpar@1956:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2391:  * Copyright (C) 2003-2007
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1956:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1956:  *
alpar@1956:  * Permission to use, modify and distribute this software is granted
alpar@1956:  * provided that this copyright notice appears in all copies. For
alpar@1956:  * precise terms see the accompanying LICENSE file.
alpar@1956:  *
alpar@1956:  * This software is provided "AS IS" with no warranty of any kind,
alpar@1956:  * express or implied, and with no claim as to its suitability for any
alpar@1956:  * purpose.
alpar@1956:  *
alpar@1956:  */
alpar@1956: 
alpar@921: #ifndef LEMON_BENCH_TEST_H
alpar@921: #define LEMON_BENCH_TEST_H
alpar@711: 
alpar@711: #include<vector>
alpar@718: #include<iostream>
alpar@718: 
alpar@1756: #include<lemon/graph_utils.h>
alpar@921: #include<lemon/time_measure.h>
alpar@711: 
alpar@711: ///A primitive primtest
alpar@718: 
alpar@718: ///\bug 2 is not a prime according to this function!
klao@979: ///
klao@979: ///\bug This function should go out of header file. I'm making it
klao@979: /// inline for now.
klao@979: inline bool isPrim(int n)
alpar@711: {
alpar@711:   if(n%2) {
alpar@711:     for(int k=3;n/k>=k;k+=2)
alpar@711:       if(!(n%k)) return false;
alpar@711:     return true;
alpar@711:   }
alpar@711:   return false;
alpar@711: }
alpar@711: 
alpar@711: ///Finds the smallest prime not less then \c n.
klao@979: 
klao@979: ///\bug This function should go out of header file. I'm making it
klao@979: /// inline for now.
klao@979: inline int nextPrim(int n)
alpar@711: {
alpar@711:   for(n+=!(n%2);!isPrim(n);n+=2) ;
alpar@711:   return n;
alpar@711: }
alpar@711: 
alpar@711: 
alpar@711: /// Class to generate consecutive primes
alpar@711: class Primes 
alpar@711: {
alpar@711:   std::vector<int> primes;
alpar@711:   int n;
alpar@711:   
alpar@711:   bool isPrime(int m) 
alpar@711:   {
alpar@711:     for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false;
alpar@711:     return true;
alpar@711:   }
alpar@711: public:
alpar@711:   Primes() : n(1) {}
alpar@711:   
alpar@711:   int operator() ()
alpar@711:     {
alpar@711:       if(primes.size()==0) {
alpar@711: 	primes.push_back(2);
alpar@711: 	return 2;
alpar@711:       }
alpar@711:       else {
alpar@711: 	do n+=2; while(!isPrime(n));
alpar@711: 	primes.push_back(n);
alpar@711: 	return n;
alpar@711:       }
alpar@711:     }
alpar@711: };
alpar@711: 
deba@2386: inline void PrintTime(const char *ID, lemon::Timer &T) 
alpar@718: {
alpar@921:   lemon::TimeStamp S(T);
alpar@1689:   std::cout << ID << ' ' << S.userTime() << ' '
alpar@1689: 	    << S.systemTime() << ' ' << S.realTime() << std::endl;
alpar@718: }
alpar@718: 
alpar@742: 
alpar@742: 
alpar@742: ///
alpar@742: template<class Graph>
alpar@1689: void addHyperCube(Graph &G,int dim,std::vector<typename Graph::Node> &nodes)
alpar@742: {
alpar@1756:   GRAPH_TYPEDEFS(typename Graph);
alpar@718:   
alpar@742:   std::vector<int> bits(dim+1);
alpar@742:   bits[0]=1;
alpar@742:   for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
alpar@742:   
alpar@742:   for(int i=0;i<bits[dim];i++) {
alpar@742:     nodes.push_back(G.addNode());
alpar@742:     for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
alpar@742:   }
alpar@742: }
alpar@742: 
alpar@742: ///
alpar@742: template<class Graph>
alpar@1689: void addBiDirHyperCube(Graph &G,int dim,std::vector<typename Graph::Node>&nodes)
alpar@742: {
alpar@1756:   GRAPH_TYPEDEFS(typename Graph);
alpar@742:   
alpar@742:   std::vector<int> bits(dim+1);
alpar@742:   bits[0]=1;
alpar@742:   for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
alpar@742:   
alpar@742:   for(int i=0;i<bits[dim];i++) {
alpar@742:     nodes.push_back(G.addNode());
alpar@742:     for(int j=0;j<dim;j++) if(i&bits[j]) {
alpar@742:       G.addEdge(nodes[i-bits[j]],nodes[i]);
alpar@742:       G.addEdge(nodes[i],nodes[i-bits[j]]);
alpar@742:     }
alpar@742:     
alpar@742:   }
alpar@742: }  
alpar@711: 
alpar@711: #endif