COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/bench_tools.h @ 742:235fd36336b7

Last change on this file since 742:235fd36336b7 was 742:235fd36336b7, checked in by Alpar Juttner, 16 years ago
  • bfs-bench added
  • hypercube generators moved to bench-tools.h
  • new benchmark script
File size: 2.6 KB
Line 
1// -*- mode:C++ -*-
2#ifndef HUGO_BENCH_TEST_H
3#define HUGO_BENCH_TEST_H
4
5#include<vector>
6#include<iostream>
7
8#include<hugo/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    NodeIn;\
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    NodeIn;\
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!
31bool isPrim(int n)
32{
33  if(n%2) {
34    for(int k=3;n/k>=k;k+=2)
35      if(!(n%k)) return false;
36    return true;
37  }
38  return false;
39}
40
41///Finds the smallest prime not less then \c n.
42int nextPrim(int n)
43{
44  for(n+=!(n%2);!isPrim(n);n+=2) ;
45  return n;
46}
47
48
49/// Class to generate consecutive primes
50class Primes
51{
52  std::vector<int> primes;
53  int n;
54 
55  bool isPrime(int m)
56  {
57    for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false;
58    return true;
59  }
60public:
61  Primes() : n(1) {}
62 
63  int operator() ()
64    {
65      if(primes.size()==0) {
66        primes.push_back(2);
67        return 2;
68      }
69      else {
70        do n+=2; while(!isPrime(n));
71        primes.push_back(n);
72        return n;
73      }
74    }
75};
76
77inline void PrintTime(char *ID,hugo::Timer &T)
78{
79  hugo::TimeStamp S(T);
80  std::cout << ID << ' ' << S.getUserTime() << ' '
81            << S.getSystemTime() << ' ' << S.getRealTime() << std::endl;
82}
83
84
85
86///
87template<class Graph>
88void addHiperCube(Graph &G,int dim,std::vector<typename Graph::Node> &nodes)
89{
90  GRAPH_TYPEDEF_FACTORY(Graph);
91 
92  std::vector<int> bits(dim+1);
93  bits[0]=1;
94  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
95 
96  for(int i=0;i<bits[dim];i++) {
97    nodes.push_back(G.addNode());
98    for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
99  }
100}
101
102///
103template<class Graph>
104void addBiDirHiperCube(Graph &G,int dim,std::vector<typename Graph::Node>&nodes)
105{
106  GRAPH_TYPEDEF_FACTORY(Graph);
107 
108  std::vector<int> bits(dim+1);
109  bits[0]=1;
110  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
111 
112  for(int i=0;i<bits[dim];i++) {
113    nodes.push_back(G.addNode());
114    for(int j=0;j<dim;j++) if(i&bits[j]) {
115      G.addEdge(nodes[i-bits[j]],nodes[i]);
116      G.addEdge(nodes[i],nodes[i-bits[j]]);
117    }
118   
119  }
120
121
122#endif
Note: See TracBrowser for help on using the repository browser.