| author | alpar |
| Thu, 26 Jan 2006 06:44:22 +0000 | |
| changeset 1908 | e225719bde6b |
| parent 1689 | f1795dafe42c |
| child 1956 | a055123339d5 |
| permissions | -rw-r--r-- |
| alpar@711 | 1 |
// -*- mode:C++ -*- |
| alpar@921 | 2 |
#ifndef LEMON_BENCH_TEST_H |
| alpar@921 | 3 |
#define LEMON_BENCH_TEST_H |
| alpar@711 | 4 |
|
| alpar@711 | 5 |
#include<vector> |
| alpar@718 | 6 |
#include<iostream> |
| alpar@718 | 7 |
|
| alpar@1756 | 8 |
#include<lemon/graph_utils.h> |
| alpar@921 | 9 |
#include<lemon/time_measure.h> |
| alpar@711 | 10 |
|
| alpar@711 | 11 |
///A primitive primtest |
| alpar@718 | 12 |
|
| alpar@718 | 13 |
///\bug 2 is not a prime according to this function! |
| klao@979 | 14 |
/// |
| klao@979 | 15 |
///\bug This function should go out of header file. I'm making it |
| klao@979 | 16 |
/// inline for now. |
| klao@979 | 17 |
inline bool isPrim(int n) |
| alpar@711 | 18 |
{
|
| alpar@711 | 19 |
if(n%2) {
|
| alpar@711 | 20 |
for(int k=3;n/k>=k;k+=2) |
| alpar@711 | 21 |
if(!(n%k)) return false; |
| alpar@711 | 22 |
return true; |
| alpar@711 | 23 |
} |
| alpar@711 | 24 |
return false; |
| alpar@711 | 25 |
} |
| alpar@711 | 26 |
|
| alpar@711 | 27 |
///Finds the smallest prime not less then \c n. |
| klao@979 | 28 |
|
| klao@979 | 29 |
///\bug This function should go out of header file. I'm making it |
| klao@979 | 30 |
/// inline for now. |
| klao@979 | 31 |
inline int nextPrim(int n) |
| alpar@711 | 32 |
{
|
| alpar@711 | 33 |
for(n+=!(n%2);!isPrim(n);n+=2) ; |
| alpar@711 | 34 |
return n; |
| alpar@711 | 35 |
} |
| alpar@711 | 36 |
|
| alpar@711 | 37 |
|
| alpar@711 | 38 |
/// Class to generate consecutive primes |
| alpar@711 | 39 |
class Primes |
| alpar@711 | 40 |
{
|
| alpar@711 | 41 |
std::vector<int> primes; |
| alpar@711 | 42 |
int n; |
| alpar@711 | 43 |
|
| alpar@711 | 44 |
bool isPrime(int m) |
| alpar@711 | 45 |
{
|
| alpar@711 | 46 |
for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false; |
| alpar@711 | 47 |
return true; |
| alpar@711 | 48 |
} |
| alpar@711 | 49 |
public: |
| alpar@711 | 50 |
Primes() : n(1) {}
|
| alpar@711 | 51 |
|
| alpar@711 | 52 |
int operator() () |
| alpar@711 | 53 |
{
|
| alpar@711 | 54 |
if(primes.size()==0) {
|
| alpar@711 | 55 |
primes.push_back(2); |
| alpar@711 | 56 |
return 2; |
| alpar@711 | 57 |
} |
| alpar@711 | 58 |
else {
|
| alpar@711 | 59 |
do n+=2; while(!isPrime(n)); |
| alpar@711 | 60 |
primes.push_back(n); |
| alpar@711 | 61 |
return n; |
| alpar@711 | 62 |
} |
| alpar@711 | 63 |
} |
| alpar@711 | 64 |
}; |
| alpar@711 | 65 |
|
| alpar@921 | 66 |
inline void PrintTime(char *ID,lemon::Timer &T) |
| alpar@718 | 67 |
{
|
| alpar@921 | 68 |
lemon::TimeStamp S(T); |
| alpar@1689 | 69 |
std::cout << ID << ' ' << S.userTime() << ' ' |
| alpar@1689 | 70 |
<< S.systemTime() << ' ' << S.realTime() << std::endl; |
| alpar@718 | 71 |
} |
| alpar@718 | 72 |
|
| alpar@742 | 73 |
|
| alpar@742 | 74 |
|
| alpar@742 | 75 |
/// |
| alpar@742 | 76 |
template<class Graph> |
| alpar@1689 | 77 |
void addHyperCube(Graph &G,int dim,std::vector<typename Graph::Node> &nodes) |
| alpar@742 | 78 |
{
|
| alpar@1756 | 79 |
GRAPH_TYPEDEFS(typename Graph); |
| alpar@718 | 80 |
|
| alpar@742 | 81 |
std::vector<int> bits(dim+1); |
| alpar@742 | 82 |
bits[0]=1; |
| alpar@742 | 83 |
for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1]; |
| alpar@742 | 84 |
|
| alpar@742 | 85 |
for(int i=0;i<bits[dim];i++) {
|
| alpar@742 | 86 |
nodes.push_back(G.addNode()); |
| alpar@742 | 87 |
for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]); |
| alpar@742 | 88 |
} |
| alpar@742 | 89 |
} |
| alpar@742 | 90 |
|
| alpar@742 | 91 |
/// |
| alpar@742 | 92 |
template<class Graph> |
| alpar@1689 | 93 |
void addBiDirHyperCube(Graph &G,int dim,std::vector<typename Graph::Node>&nodes) |
| alpar@742 | 94 |
{
|
| alpar@1756 | 95 |
GRAPH_TYPEDEFS(typename Graph); |
| alpar@742 | 96 |
|
| alpar@742 | 97 |
std::vector<int> bits(dim+1); |
| alpar@742 | 98 |
bits[0]=1; |
| alpar@742 | 99 |
for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1]; |
| alpar@742 | 100 |
|
| alpar@742 | 101 |
for(int i=0;i<bits[dim];i++) {
|
| alpar@742 | 102 |
nodes.push_back(G.addNode()); |
| alpar@742 | 103 |
for(int j=0;j<dim;j++) if(i&bits[j]) {
|
| alpar@742 | 104 |
G.addEdge(nodes[i-bits[j]],nodes[i]); |
| alpar@742 | 105 |
G.addEdge(nodes[i],nodes[i-bits[j]]); |
| alpar@742 | 106 |
} |
| alpar@742 | 107 |
|
| alpar@742 | 108 |
} |
| alpar@742 | 109 |
} |
| alpar@711 | 110 |
|
| alpar@711 | 111 |
#endif |