| author | deba |
| Wed, 02 Nov 2005 15:27:38 +0000 | |
| changeset 1754 | 4bf5ceb49023 |
| parent 1435 | 8e85e6bbefdf |
| child 1756 | b1f441f24d08 |
| 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! |
| klao@979 | 31 |
/// |
| klao@979 | 32 |
///\bug This function should go out of header file. I'm making it |
| klao@979 | 33 |
/// inline for now. |
| klao@979 | 34 |
inline bool isPrim(int n) |
| alpar@711 | 35 |
{
|
| alpar@711 | 36 |
if(n%2) {
|
| alpar@711 | 37 |
for(int k=3;n/k>=k;k+=2) |
| alpar@711 | 38 |
if(!(n%k)) return false; |
| alpar@711 | 39 |
return true; |
| alpar@711 | 40 |
} |
| alpar@711 | 41 |
return false; |
| alpar@711 | 42 |
} |
| alpar@711 | 43 |
|
| alpar@711 | 44 |
///Finds the smallest prime not less then \c n. |
| klao@979 | 45 |
|
| klao@979 | 46 |
///\bug This function should go out of header file. I'm making it |
| klao@979 | 47 |
/// inline for now. |
| klao@979 | 48 |
inline int nextPrim(int n) |
| alpar@711 | 49 |
{
|
| alpar@711 | 50 |
for(n+=!(n%2);!isPrim(n);n+=2) ; |
| alpar@711 | 51 |
return n; |
| alpar@711 | 52 |
} |
| alpar@711 | 53 |
|
| alpar@711 | 54 |
|
| alpar@711 | 55 |
/// Class to generate consecutive primes |
| alpar@711 | 56 |
class Primes |
| alpar@711 | 57 |
{
|
| alpar@711 | 58 |
std::vector<int> primes; |
| alpar@711 | 59 |
int n; |
| alpar@711 | 60 |
|
| alpar@711 | 61 |
bool isPrime(int m) |
| alpar@711 | 62 |
{
|
| alpar@711 | 63 |
for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false; |
| alpar@711 | 64 |
return true; |
| alpar@711 | 65 |
} |
| alpar@711 | 66 |
public: |
| alpar@711 | 67 |
Primes() : n(1) {}
|
| alpar@711 | 68 |
|
| alpar@711 | 69 |
int operator() () |
| alpar@711 | 70 |
{
|
| alpar@711 | 71 |
if(primes.size()==0) {
|
| alpar@711 | 72 |
primes.push_back(2); |
| alpar@711 | 73 |
return 2; |
| alpar@711 | 74 |
} |
| alpar@711 | 75 |
else {
|
| alpar@711 | 76 |
do n+=2; while(!isPrime(n)); |
| alpar@711 | 77 |
primes.push_back(n); |
| alpar@711 | 78 |
return n; |
| alpar@711 | 79 |
} |
| alpar@711 | 80 |
} |
| alpar@711 | 81 |
}; |
| alpar@711 | 82 |
|
| alpar@921 | 83 |
inline void PrintTime(char *ID,lemon::Timer &T) |
| alpar@718 | 84 |
{
|
| alpar@921 | 85 |
lemon::TimeStamp S(T); |
| alpar@1689 | 86 |
std::cout << ID << ' ' << S.userTime() << ' ' |
| alpar@1689 | 87 |
<< S.systemTime() << ' ' << S.realTime() << std::endl; |
| alpar@718 | 88 |
} |
| alpar@718 | 89 |
|
| alpar@742 | 90 |
|
| alpar@742 | 91 |
|
| alpar@742 | 92 |
/// |
| alpar@742 | 93 |
template<class Graph> |
| alpar@1689 | 94 |
void addHyperCube(Graph &G,int dim,std::vector<typename Graph::Node> &nodes) |
| alpar@742 | 95 |
{
|
| alpar@742 | 96 |
GRAPH_TYPEDEF_FACTORY(Graph); |
| alpar@718 | 97 |
|
| alpar@742 | 98 |
std::vector<int> bits(dim+1); |
| alpar@742 | 99 |
bits[0]=1; |
| alpar@742 | 100 |
for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1]; |
| alpar@742 | 101 |
|
| alpar@742 | 102 |
for(int i=0;i<bits[dim];i++) {
|
| alpar@742 | 103 |
nodes.push_back(G.addNode()); |
| alpar@742 | 104 |
for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]); |
| alpar@742 | 105 |
} |
| alpar@742 | 106 |
} |
| alpar@742 | 107 |
|
| alpar@742 | 108 |
/// |
| alpar@742 | 109 |
template<class Graph> |
| alpar@1689 | 110 |
void addBiDirHyperCube(Graph &G,int dim,std::vector<typename Graph::Node>&nodes) |
| alpar@742 | 111 |
{
|
| alpar@742 | 112 |
GRAPH_TYPEDEF_FACTORY(Graph); |
| alpar@742 | 113 |
|
| alpar@742 | 114 |
std::vector<int> bits(dim+1); |
| alpar@742 | 115 |
bits[0]=1; |
| alpar@742 | 116 |
for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1]; |
| alpar@742 | 117 |
|
| alpar@742 | 118 |
for(int i=0;i<bits[dim];i++) {
|
| alpar@742 | 119 |
nodes.push_back(G.addNode()); |
| alpar@742 | 120 |
for(int j=0;j<dim;j++) if(i&bits[j]) {
|
| alpar@742 | 121 |
G.addEdge(nodes[i-bits[j]],nodes[i]); |
| alpar@742 | 122 |
G.addEdge(nodes[i],nodes[i-bits[j]]); |
| alpar@742 | 123 |
} |
| alpar@742 | 124 |
|
| alpar@742 | 125 |
} |
| alpar@742 | 126 |
} |
| alpar@711 | 127 |
|
| alpar@711 | 128 |
#endif |