COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/bench_tools.h @ 1847:7cbc12e42482

Last change on this file since 1847:7cbc12e42482 was 1756:b1f441f24d08, checked in by Alpar Juttner, 16 years ago

GRAPH_TYPEDEFS and UNDIRGRAPH_TYPEDEFS macros added to graph_utils.h.

File size: 2.1 KB
RevLine 
[711]1// -*- mode:C++ -*-
[921]2#ifndef LEMON_BENCH_TEST_H
3#define LEMON_BENCH_TEST_H
[711]4
5#include<vector>
[718]6#include<iostream>
7
[1756]8#include<lemon/graph_utils.h>
[921]9#include<lemon/time_measure.h>
[711]10
11///A primitive primtest
[718]12
13///\bug 2 is not a prime according to this function!
[979]14///
15///\bug This function should go out of header file. I'm making it
16/// inline for now.
17inline bool isPrim(int n)
[711]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.
[979]28
29///\bug This function should go out of header file. I'm making it
30/// inline for now.
31inline int nextPrim(int n)
[711]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
[921]66inline void PrintTime(char *ID,lemon::Timer &T)
[718]67{
[921]68  lemon::TimeStamp S(T);
[1689]69  std::cout << ID << ' ' << S.userTime() << ' '
70            << S.systemTime() << ' ' << S.realTime() << std::endl;
[718]71}
72
[742]73
74
75///
76template<class Graph>
[1689]77void addHyperCube(Graph &G,int dim,std::vector<typename Graph::Node> &nodes)
[742]78{
[1756]79  GRAPH_TYPEDEFS(typename Graph);
[718]80 
[742]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>
[1689]93void addBiDirHyperCube(Graph &G,int dim,std::vector<typename Graph::Node>&nodes)
[742]94{
[1756]95  GRAPH_TYPEDEFS(typename Graph);
[742]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
[711]110
111#endif
Note: See TracBrowser for help on using the repository browser.