| author | alpar |
| Thu, 30 Sep 2004 08:13:51 +0000 | |
| changeset 924 | ccb657556d84 |
| parent 750 | 2713723d2210 |
| child 979 | b5fb023cdb7b |
| 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@921 | 8 |
#include<lemon/time_measure.h> |
| alpar@711 | 9 |
|
| alpar@711 | 10 |
///An experimental typedef factory |
| alpar@711 | 11 |
#define GRAPH_TYPEDEF_FACTORY(Graph) \ |
| alpar@711 | 12 |
typedef typename Graph:: Node Node;\ |
| alpar@750 | 13 |
typedef typename Graph:: NodeIt NodeIt;\ |
| alpar@711 | 14 |
typedef typename Graph:: Edge Edge;\ |
| alpar@711 | 15 |
typedef typename Graph:: EdgeIt EdgeIt;\ |
| alpar@711 | 16 |
typedef typename Graph:: InEdgeIt InEdgeIt;\ |
| alpar@711 | 17 |
typedef typename Graph::OutEdgeIt OutEdgeIt; |
| alpar@711 | 18 |
|
| alpar@711 | 19 |
#define GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph) \ |
| alpar@711 | 20 |
typedef Graph:: Node Node;\ |
| alpar@750 | 21 |
typedef Graph:: NodeIt NodeIt;\ |
| alpar@711 | 22 |
typedef Graph:: Edge Edge;\ |
| alpar@711 | 23 |
typedef Graph:: EdgeIt EdgeIt;\ |
| alpar@711 | 24 |
typedef Graph:: InEdgeIt InEdgeIt;\ |
| alpar@711 | 25 |
typedef Graph::OutEdgeIt OutEdgeIt; |
| alpar@711 | 26 |
|
| alpar@711 | 27 |
|
| alpar@711 | 28 |
///A primitive primtest |
| alpar@718 | 29 |
|
| alpar@718 | 30 |
///\bug 2 is not a prime according to this function! |
| alpar@711 | 31 |
bool isPrim(int n) |
| alpar@711 | 32 |
{
|
| alpar@711 | 33 |
if(n%2) {
|
| alpar@711 | 34 |
for(int k=3;n/k>=k;k+=2) |
| alpar@711 | 35 |
if(!(n%k)) return false; |
| alpar@711 | 36 |
return true; |
| alpar@711 | 37 |
} |
| alpar@711 | 38 |
return false; |
| alpar@711 | 39 |
} |
| alpar@711 | 40 |
|
| alpar@711 | 41 |
///Finds the smallest prime not less then \c n. |
| alpar@711 | 42 |
int nextPrim(int n) |
| alpar@711 | 43 |
{
|
| alpar@711 | 44 |
for(n+=!(n%2);!isPrim(n);n+=2) ; |
| alpar@711 | 45 |
return n; |
| alpar@711 | 46 |
} |
| alpar@711 | 47 |
|
| alpar@711 | 48 |
|
| alpar@711 | 49 |
/// Class to generate consecutive primes |
| alpar@711 | 50 |
class Primes |
| alpar@711 | 51 |
{
|
| alpar@711 | 52 |
std::vector<int> primes; |
| alpar@711 | 53 |
int n; |
| alpar@711 | 54 |
|
| alpar@711 | 55 |
bool isPrime(int m) |
| alpar@711 | 56 |
{
|
| alpar@711 | 57 |
for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false; |
| alpar@711 | 58 |
return true; |
| alpar@711 | 59 |
} |
| alpar@711 | 60 |
public: |
| alpar@711 | 61 |
Primes() : n(1) {}
|
| alpar@711 | 62 |
|
| alpar@711 | 63 |
int operator() () |
| alpar@711 | 64 |
{
|
| alpar@711 | 65 |
if(primes.size()==0) {
|
| alpar@711 | 66 |
primes.push_back(2); |
| alpar@711 | 67 |
return 2; |
| alpar@711 | 68 |
} |
| alpar@711 | 69 |
else {
|
| alpar@711 | 70 |
do n+=2; while(!isPrime(n)); |
| alpar@711 | 71 |
primes.push_back(n); |
| alpar@711 | 72 |
return n; |
| alpar@711 | 73 |
} |
| alpar@711 | 74 |
} |
| alpar@711 | 75 |
}; |
| alpar@711 | 76 |
|
| alpar@921 | 77 |
inline void PrintTime(char *ID,lemon::Timer &T) |
| alpar@718 | 78 |
{
|
| alpar@921 | 79 |
lemon::TimeStamp S(T); |
| alpar@718 | 80 |
std::cout << ID << ' ' << S.getUserTime() << ' ' |
| alpar@718 | 81 |
<< S.getSystemTime() << ' ' << S.getRealTime() << std::endl; |
| alpar@718 | 82 |
} |
| alpar@718 | 83 |
|
| alpar@742 | 84 |
|
| alpar@742 | 85 |
|
| alpar@742 | 86 |
/// |
| alpar@742 | 87 |
template<class Graph> |
| alpar@742 | 88 |
void addHiperCube(Graph &G,int dim,std::vector<typename Graph::Node> &nodes) |
| alpar@742 | 89 |
{
|
| alpar@742 | 90 |
GRAPH_TYPEDEF_FACTORY(Graph); |
| alpar@718 | 91 |
|
| alpar@742 | 92 |
std::vector<int> bits(dim+1); |
| alpar@742 | 93 |
bits[0]=1; |
| alpar@742 | 94 |
for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1]; |
| alpar@742 | 95 |
|
| alpar@742 | 96 |
for(int i=0;i<bits[dim];i++) {
|
| alpar@742 | 97 |
nodes.push_back(G.addNode()); |
| alpar@742 | 98 |
for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]); |
| alpar@742 | 99 |
} |
| alpar@742 | 100 |
} |
| alpar@742 | 101 |
|
| alpar@742 | 102 |
/// |
| alpar@742 | 103 |
template<class Graph> |
| alpar@742 | 104 |
void addBiDirHiperCube(Graph &G,int dim,std::vector<typename Graph::Node>&nodes) |
| alpar@742 | 105 |
{
|
| alpar@742 | 106 |
GRAPH_TYPEDEF_FACTORY(Graph); |
| alpar@742 | 107 |
|
| alpar@742 | 108 |
std::vector<int> bits(dim+1); |
| alpar@742 | 109 |
bits[0]=1; |
| alpar@742 | 110 |
for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1]; |
| alpar@742 | 111 |
|
| alpar@742 | 112 |
for(int i=0;i<bits[dim];i++) {
|
| alpar@742 | 113 |
nodes.push_back(G.addNode()); |
| alpar@742 | 114 |
for(int j=0;j<dim;j++) if(i&bits[j]) {
|
| alpar@742 | 115 |
G.addEdge(nodes[i-bits[j]],nodes[i]); |
| alpar@742 | 116 |
G.addEdge(nodes[i],nodes[i-bits[j]]); |
| alpar@742 | 117 |
} |
| alpar@742 | 118 |
|
| alpar@742 | 119 |
} |
| alpar@742 | 120 |
} |
| alpar@711 | 121 |
|
| alpar@711 | 122 |
#endif |