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