COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/bench_tools.h @ 1712:4fb435ad31cf

Last change on this file since 1712:4fb435ad31cf was 1689:f1795dafe42c, checked in by Alpar Juttner, 15 years ago
  • runningTimeTest(): a tool to measure running times more precisely.
  • TimeStamp? now uses double to count cpu-times
  • 'get's removed from the query functions of Times and TimeStamp?
File size: 2.7 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/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.
34inline 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.
48inline 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
56class 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  }
66public:
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
83inline void PrintTime(char *ID,lemon::Timer &T)
84{
85  lemon::TimeStamp S(T);
86  std::cout << ID << ' ' << S.userTime() << ' '
87            << S.systemTime() << ' ' << S.realTime() << std::endl;
88}
89
90
91
92///
93template<class Graph>
94void addHyperCube(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///
109template<class Graph>
110void addBiDirHyperCube(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
Note: See TracBrowser for help on using the repository browser.