COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/bench_tools.h @ 1901:723b2b81d900

Last change on this file since 1901:723b2b81d900 was 1756:b1f441f24d08, checked in by Alpar Juttner, 15 years ago

GRAPH_TYPEDEFS and UNDIRGRAPH_TYPEDEFS macros added to graph_utils.h.

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