source: lemon-0.x/benchmark/bench_tools.h @ 1958:5be9c1ca0252

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_BENCH_TEST_H
#define LEMON_BENCH_TEST_H

#include<vector>
#include<iostream>

#include<lemon/graph_utils.h>
#include<lemon/time_measure.h>

///A primitive primtest

///\bug 2 is not a prime according to this function!
///
///\bug This function should go out of header file. I'm making it
/// inline for now.
inline bool isPrim(int n)
{
  if(n%2) {
    for(int k=3;n/k>=k;k+=2)
      if(!(n%k)) return false;
    return true;
  }
  return false;
}

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

///\bug This function should go out of header file. I'm making it
/// inline for now.
inline int nextPrim(int n)
{
  for(n+=!(n%2);!isPrim(n);n+=2) ;
  return n;
}


/// Class to generate consecutive primes
class Primes 
{
  std::vector<int> primes;
  int n;
  
  bool isPrime(int m) 
  {
    for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false;
    return true;
  }
public:
  Primes() : n(1) {}
  
  int operator() ()
    {
      if(primes.size()==0) {
        primes.push_back(2);
        return 2;
      }
      else {
        do n+=2; while(!isPrime(n));
        primes.push_back(n);
        return n;
      }
    }
};

inline void PrintTime(char *ID,lemon::Timer &T) 
{
  lemon::TimeStamp S(T);
  std::cout << ID << ' ' << S.userTime() << ' '
            << S.systemTime() << ' ' << S.realTime() << std::endl;
}



///
template<class Graph>
void addHyperCube(Graph &G,int dim,std::vector<typename Graph::Node> &nodes)
{
  GRAPH_TYPEDEFS(typename Graph);
  
  std::vector<int> bits(dim+1);
  bits[0]=1;
  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
  
  for(int i=0;i<bits[dim];i++) {
    nodes.push_back(G.addNode());
    for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
  }
}

///
template<class Graph>
void addBiDirHyperCube(Graph &G,int dim,std::vector<typename Graph::Node>&nodes)
{
  GRAPH_TYPEDEFS(typename Graph);
  
  std::vector<int> bits(dim+1);
  bits[0]=1;
  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
  
  for(int i=0;i<bits[dim];i++) {
    nodes.push_back(G.addNode());
    for(int j=0;j<dim;j++) if(i&bits[j]) {
      G.addEdge(nodes[i-bits[j]],nodes[i]);
      G.addEdge(nodes[i],nodes[i-bits[j]]);
    }
    
  }
}  

#endif