# source:lemon-0.x/benchmark/bench_tools.h@1956:a055123339d5

Last change on this file since 1956:a055123339d5 was 1956:a055123339d5, checked in by Alpar Juttner, 15 years ago

File size: 2.7 KB
Line
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_BENCH_TEST_H
20#define LEMON_BENCH_TEST_H
21
22#include<vector>
23#include<iostream>
24
25#include<lemon/graph_utils.h>
26#include<lemon/time_measure.h>
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_TYPEDEFS(typename 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++) {
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_TYPEDEFS(typename 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++) {