1.1 --- a/lemon/Makefile.am Mon Oct 02 14:41:53 2006 +0000
1.2 +++ b/lemon/Makefile.am Mon Oct 02 16:11:00 2006 +0000
1.3 @@ -12,8 +12,8 @@
1.4 lemon/base.cc \
1.5 lemon/color.cc \
1.6 lemon/eps.cc \
1.7 - lemon/bits/mingw32_rand.cc \
1.8 - lemon/bits/mingw32_time.cc
1.9 + lemon/bits/mingw32_time.cc \
1.10 + lemon/random.cc
1.11
1.12 lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS)
1.13 lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS)
1.14 @@ -86,6 +86,7 @@
1.15 lemon/prim.h \
1.16 lemon/radix_heap.h \
1.17 lemon/radix_sort.h \
1.18 + lemon/random.h \
1.19 lemon/refptr.h \
1.20 lemon/simann.h \
1.21 lemon/smart_graph.h \
1.22 @@ -112,7 +113,6 @@
1.23 lemon/bits/item_reader.h \
1.24 lemon/bits/item_writer.h \
1.25 lemon/bits/map_extender.h \
1.26 - lemon/bits/mingw32_rand.h \
1.27 lemon/bits/mingw32_time.h \
1.28 lemon/bits/traits.h \
1.29 lemon/bits/utility.h \
2.1 --- a/lemon/bits/mingw32_rand.cc Mon Oct 02 14:41:53 2006 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,83 +0,0 @@
2.4 -#ifdef WIN32
2.5 -
2.6 -#include <lemon/bits/mingw32_rand.h>
2.7 -
2.8 -
2.9 -static unsigned short _mingw_rand_state[10];
2.10 -
2.11 -void _mingw_rand_next_state(unsigned short xsubi[3]) {
2.12 - _mingw_rand_state[8] = _mingw_rand_state[9] = 0;
2.13 - _mingw_rand_state[7] = _mingw_rand_state[6];
2.14 - for (int i = 0; i < 3; ++i) {
2.15 - unsigned long val = 0;
2.16 - for (int j = 0; i + j < 3; ++j) {
2.17 - val += (unsigned long)_mingw_rand_state[7 + i + j]
2.18 - + (unsigned long)xsubi[i] * (unsigned long)_mingw_rand_state[3 + j];
2.19 - _mingw_rand_state[7 + i + j] = val;
2.20 - val >>= 16;
2.21 - }
2.22 - }
2.23 - xsubi[0] = _mingw_rand_state[6];
2.24 - xsubi[1] = _mingw_rand_state[7];
2.25 - xsubi[2] = _mingw_rand_state[8];
2.26 -}
2.27 -
2.28 -long int lrand48(void) {
2.29 - return nrand48(_mingw_rand_state);
2.30 -}
2.31 -
2.32 -long int nrand48(unsigned short xsubi[3]) {
2.33 - _mingw_rand_next_state(xsubi);
2.34 - return ((long)(xsubi[2] & ( (1 << 15) - 1) ) << 16) | (long)xsubi[1];
2.35 -}
2.36 -
2.37 -double drand48(void) {
2.38 - return erand48(_mingw_rand_state);
2.39 -}
2.40 -
2.41 -double erand48(unsigned short xsubi[3]) {
2.42 - return (double)nrand48(xsubi) / (1 << 31);
2.43 -}
2.44 -
2.45 -
2.46 -long int mrand48(void) {
2.47 - return jrand48(_mingw_rand_state);
2.48 -}
2.49 -
2.50 -long int jrand48(unsigned short xsubi[3]) {
2.51 - _mingw_rand_next_state(xsubi);
2.52 - return ((long)xsubi[2] << 16) | (long)xsubi[1];
2.53 -}
2.54 -
2.55 -void srand48(long int seedval) {
2.56 - _mingw_rand_state[0] = 0x330E;
2.57 - _mingw_rand_state[1] = seedval & ( (1 << 16) - 1);
2.58 - _mingw_rand_state[2] = seedval >> 16;
2.59 - _mingw_rand_state[3] = 0xE66D;
2.60 - _mingw_rand_state[4] = 0xDEEC;
2.61 - _mingw_rand_state[5] = 0x0005;
2.62 - _mingw_rand_state[6] = 0x000B;
2.63 -}
2.64 -
2.65 -unsigned short *seed48(unsigned short seed16v[3]) {
2.66 - _mingw_rand_state[7] = _mingw_rand_state[0];
2.67 - _mingw_rand_state[8] = _mingw_rand_state[1];
2.68 - _mingw_rand_state[9] = _mingw_rand_state[2];
2.69 - _mingw_rand_state[0] = seed16v[0];
2.70 - _mingw_rand_state[1] = seed16v[1];
2.71 - _mingw_rand_state[2] = seed16v[2];
2.72 - return _mingw_rand_state + 7;
2.73 -}
2.74 -
2.75 -void lcong48(unsigned short param[7]) {
2.76 - _mingw_rand_state[0] = param[0];
2.77 - _mingw_rand_state[1] = param[1];
2.78 - _mingw_rand_state[2] = param[2];
2.79 - _mingw_rand_state[3] = param[3];
2.80 - _mingw_rand_state[4] = param[4];
2.81 - _mingw_rand_state[5] = param[5];
2.82 - _mingw_rand_state[6] = param[6];
2.83 -}
2.84 -
2.85 -
2.86 -#endif
3.1 --- a/lemon/bits/mingw32_rand.h Mon Oct 02 14:41:53 2006 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,37 +0,0 @@
3.4 -/* -*- C++ -*-
3.5 - *
3.6 - * This file is a part of LEMON, a generic C++ optimization library
3.7 - *
3.8 - * Copyright (C) 2003-2006
3.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 - *
3.12 - * Permission to use, modify and distribute this software is granted
3.13 - * provided that this copyright notice appears in all copies. For
3.14 - * precise terms see the accompanying LICENSE file.
3.15 - *
3.16 - * This software is provided "AS IS" with no warranty of any kind,
3.17 - * express or implied, and with no claim as to its suitability for any
3.18 - * purpose.
3.19 - *
3.20 - */
3.21 -
3.22 -#ifndef LEMON_BITS_MINGW32_RAND_H
3.23 -#define LEMON_BITS_MINGW32_RAND_H
3.24 -
3.25 -
3.26 -#ifdef WIN32
3.27 -
3.28 -double drand48(void);
3.29 -double erand48(unsigned short xsubi[3]);
3.30 -long int lrand48(void);
3.31 -long int nrand48(unsigned short xsubi[3]);
3.32 -long int mrand48(void);
3.33 -long int jrand48(unsigned short xsubi[3]);
3.34 -void srand48(long int seedval);
3.35 -unsigned short *seed48(unsigned short seed16v[3]);
3.36 -void lcong48(unsigned short param[7]);
3.37 -
3.38 -#endif
3.39 -
3.40 -#endif
4.1 --- a/lemon/hypercube_graph.h Mon Oct 02 14:41:53 2006 +0000
4.2 +++ b/lemon/hypercube_graph.h Mon Oct 02 16:11:00 2006 +0000
4.3 @@ -260,8 +260,8 @@
4.4 /// HyperCubeGraph graph(DIM);
4.5 /// dim2::Point<double> base[DIM];
4.6 /// for (int k = 0; k < DIM; ++k) {
4.7 - /// base[k].x = rand() / (RAND_MAX + 1.0);
4.8 - /// base[k].y = rand() / (RAND_MAX + 1.0);
4.9 + /// base[k].x = random.getReal();
4.10 + /// base[k].y = random.getReal();
4.11 /// }
4.12 /// HyperCubeGraph::HyperMap<dim2::Point<double> >
4.13 /// pos(graph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/lemon/random.cc Mon Oct 02 16:11:00 2006 +0000
5.3 @@ -0,0 +1,5 @@
5.4 +#include <lemon/random.h>
5.5 +
5.6 +namespace lemon {
5.7 + Random rnd;
5.8 +}
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/lemon/random.h Mon Oct 02 16:11:00 2006 +0000
6.3 @@ -0,0 +1,511 @@
6.4 +/* -*- C++ -*-
6.5 + *
6.6 + * This file is a part of LEMON, a generic C++ optimization library
6.7 + *
6.8 + * Copyright (C) 2003-2006
6.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.11 + *
6.12 + * Permission to use, modify and distribute this software is granted
6.13 + * provided that this copyright notice appears in all copies. For
6.14 + * precise terms see the accompanying LICENSE file.
6.15 + *
6.16 + * This software is provided "AS IS" with no warranty of any kind,
6.17 + * express or implied, and with no claim as to its suitability for any
6.18 + * purpose.
6.19 + *
6.20 + */
6.21 +
6.22 +#ifndef LEMON_RANDOM_H
6.23 +#define LEMON_RANDOM_H
6.24 +
6.25 +#include <algorithm>
6.26 +
6.27 +#include <ctime>
6.28 +#include <cmath>
6.29 +#include <cmath>
6.30 +
6.31 +///\ingroup misc
6.32 +///\file
6.33 +///\brief Mersenne Twister random number generator
6.34 +///
6.35 +///\author Balazs Dezso
6.36 +
6.37 +namespace lemon {
6.38 +
6.39 +#if WORD_BIT == 32
6.40 +
6.41 + /// \ingroup misc
6.42 + ///
6.43 + /// \brief Mersenne Twister random number generator
6.44 + ///
6.45 + /// The Mersenne Twister is a twisted generalized feedback
6.46 + /// shift-register generator of Matsumoto and Nishimura. The period of
6.47 + /// this generator is \f$ 2^{19937} - 1 \f$ and it is equi-distributed in
6.48 + /// 623 dimensions. The time performance of this generator is comparable
6.49 + /// to the commonly used generators.
6.50 + ///
6.51 + /// \author Balazs Dezso
6.52 + class Random {
6.53 +
6.54 + static const int length = 624;
6.55 + static const int shift = 397;
6.56 +
6.57 + public:
6.58 +
6.59 + static const unsigned long min = 0ul;
6.60 + static const unsigned long max = ~0ul;
6.61 +
6.62 + /// \brief Constructor
6.63 + ///
6.64 + /// Constructor with time dependent seeding.
6.65 + Random() { initState(std::time(0)); }
6.66 +
6.67 + /// \brief Constructor
6.68 + ///
6.69 + /// Constructor
6.70 + Random(unsigned long seed) { initState(seed); }
6.71 +
6.72 + /// \brief Copy constructor
6.73 + ///
6.74 + /// Copy constructor. The generated sequence will be identical to
6.75 + /// the other sequence.
6.76 + Random(const Random& other) {
6.77 + std::copy(other.state, other.state + length, state);
6.78 + current = state + (other.current - other.state);
6.79 + }
6.80 +
6.81 + /// \brief Assign operator
6.82 + ///
6.83 + /// Assign operator. The generated sequence will be identical to
6.84 + /// the other sequence.
6.85 + Random& operator=(const Random& other) {
6.86 + if (&other != this) {
6.87 + std::copy(other.state, other.state + length, state);
6.88 + current = state + (other.current - other.state);
6.89 + }
6.90 + return *this;
6.91 + }
6.92 +
6.93 + /// \brief Returns an unsigned random number
6.94 + ///
6.95 + /// It returns an unsigned integer random number from the range
6.96 + /// \f$ \{0, 1, \dots, 2^{32} - 1\} \f$.
6.97 + unsigned long getUnsigned() {
6.98 + if (current == state) fillState();
6.99 + --current;
6.100 + unsigned long rnd = *current;
6.101 + rnd ^= (rnd >> 11);
6.102 + rnd ^= (rnd << 7) & 0x9D2C5680ul;
6.103 + rnd ^= (rnd << 15) & 0xEFC60000ul;
6.104 + rnd ^= (rnd >> 18);
6.105 + return rnd;
6.106 + }
6.107 +
6.108 + /// \brief Returns a random number
6.109 + ///
6.110 + /// It returns an integer random number from the range
6.111 + /// \f$ \{-2^{31}, \dots, 2^{31} - 1\} \f$.
6.112 + long getInt() {
6.113 + return (long)getUnsigned();
6.114 + }
6.115 +
6.116 + /// \brief Returns an unsigned integer random number
6.117 + ///
6.118 + /// It returns an unsigned integer random number from the range
6.119 + /// \f$ \{0, 1, \dots, 2^{31} - 1\} \f$.
6.120 + long getNatural() {
6.121 + return (long)(getUnsigned() >> 1);
6.122 + }
6.123 +
6.124 + /// \brief Returns a random bool
6.125 + ///
6.126 + /// It returns a random bool.
6.127 + bool getBool() {
6.128 + return (bool)(getUnsigned() & 1);
6.129 + }
6.130 +
6.131 + /// \brief Returns a real random number
6.132 + ///
6.133 + /// It returns a real random number from the range
6.134 + /// \f$ [0, 1) \f$. The double will have 32 significant bits.
6.135 + double getReal() {
6.136 + return std::ldexp((double)getUnsigned(), -32);
6.137 + }
6.138 +
6.139 + /// \brief Returns a real random number
6.140 + ///
6.141 + /// It returns a real random number from the range
6.142 + /// \f$ [0, 1) \f$. The double will have 53 significant bits,
6.143 + /// but it is slower than the \c getReal().
6.144 + double getPrecReal() {
6.145 + return std::ldexp((double)(getUnsigned() >> 5), -27) +
6.146 + std::ldexp((double)(getUnsigned() >> 6), -53);
6.147 + }
6.148 +
6.149 + /// \brief Returns an unsigned random number from a given range
6.150 + ///
6.151 + /// It returns an unsigned integer random number from the range
6.152 + /// \f$ \{0, 1, \dots, n - 1\} \f$.
6.153 + unsigned long getUnsigned(unsigned long n) {
6.154 + unsigned long mask = n - 1, rnd;
6.155 + mask |= mask >> 1;
6.156 + mask |= mask >> 2;
6.157 + mask |= mask >> 4;
6.158 + mask |= mask >> 8;
6.159 + mask |= mask >> 16;
6.160 + do rnd = getUnsigned() & mask; while (rnd >= n);
6.161 + return rnd;
6.162 + }
6.163 +
6.164 + /// \brief Returns a random number from a given range
6.165 + ///
6.166 + /// It returns an unsigned integer random number from the range
6.167 + /// \f$ \{0, 1, \dots, n - 1\} \f$.
6.168 + long getInt(long n) {
6.169 + long mask = n - 1, rnd;
6.170 + mask |= mask >> 1;
6.171 + mask |= mask >> 2;
6.172 + mask |= mask >> 4;
6.173 + mask |= mask >> 8;
6.174 + mask |= mask >> 16;
6.175 + do rnd = getUnsigned() & mask; while (rnd >= n);
6.176 + return rnd;
6.177 + }
6.178 +
6.179 + private:
6.180 +
6.181 + void initState(unsigned long seed) {
6.182 + static const unsigned long mul = 0x6c078965ul;
6.183 +
6.184 + current = state;
6.185 +
6.186 + unsigned long *curr = state + length - 1;
6.187 + curr[0] = seed; --curr;
6.188 + for (int i = 1; i < length; ++i) {
6.189 + curr[0] = (mul * ( curr[1] ^ (curr[1] >> 30) ) + i);
6.190 + --curr;
6.191 + }
6.192 + }
6.193 +
6.194 + void fillState() {
6.195 + static const unsigned long mask[2] = { 0x0ul, 0x9908B0DFul };
6.196 + static const unsigned long loMask = (1ul << 31) - 1;
6.197 + static const unsigned long hiMask = ~loMask;
6.198 +
6.199 + current = state + length;
6.200 +
6.201 + register unsigned long *curr = state + length - 1;
6.202 + register long num;
6.203 +
6.204 + num = length - shift;
6.205 + while (num--) {
6.206 + curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^
6.207 + curr[- shift] ^ mask[curr[-1] & 1ul];
6.208 + --curr;
6.209 + }
6.210 + num = shift - 1;
6.211 + while (num--) {
6.212 + curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^
6.213 + curr[length - shift] ^ mask[curr[-1] & 1ul];
6.214 + --curr;
6.215 + }
6.216 + curr[0] = (((curr[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
6.217 + curr[length - shift] ^ mask[curr[length - 1] & 1ul];
6.218 +
6.219 + }
6.220 +
6.221 + unsigned long *current;
6.222 + unsigned long state[length];
6.223 +
6.224 + };
6.225 +
6.226 +#elif WORD_BIT == 64
6.227 +
6.228 + /// \brief Mersenne Twister random number generator
6.229 + ///
6.230 + /// The Mersenne Twister is a twisted generalized feedback
6.231 + /// shift-register generator of Matsumoto and Nishimura. The period of
6.232 + /// this generator is \f$ 2^{19937} - 1 \f$ and it is equi-distributed in
6.233 + /// 311 dimensions. The time performance of this generator is comparable
6.234 + /// to the commonly used generators.
6.235 + class Random {
6.236 +
6.237 + static const int length = 312;
6.238 + static const int shift = 156;
6.239 +
6.240 + public:
6.241 +
6.242 + static const unsigned long min = 0ul;
6.243 + static const unsigned long max = ~0ul;
6.244 +
6.245 + /// \brief Constructor
6.246 + ///
6.247 + /// Constructor with time dependent seeding.
6.248 + Random() { initState(std::time(0)); }
6.249 +
6.250 + /// \brief Constructor
6.251 + ///
6.252 + /// Constructor
6.253 + Random(unsigned long seed) { initState(seed); }
6.254 +
6.255 + /// \brief Copy constructor
6.256 + ///
6.257 + /// Copy constructor. The generated sequence will be identical to
6.258 + /// the other sequence.
6.259 + Random(const Random& other) {
6.260 + std::copy(other.state, other.state + length, state);
6.261 + current = state + (other.current - other.state);
6.262 + }
6.263 +
6.264 + /// \brief Assign operator
6.265 + ///
6.266 + /// Assign operator. The generated sequence will be identical to
6.267 + /// the other sequence.
6.268 + Random& operator=(const Random& other) {
6.269 + if (&other != this) {
6.270 + std::copy(other.state, other.state + length, state);
6.271 + current = state + (other.current - other.state);
6.272 + }
6.273 + return *this;
6.274 + }
6.275 +
6.276 + /// \brief Returns an unsigned random number
6.277 + ///
6.278 + /// It returns an unsigned integer random number from the range
6.279 + /// \f$ \{0, 1, \dots, 2^{64} - 1\} \f$.
6.280 + unsigned long getUnsigned() {
6.281 + if (current == state) fillState();
6.282 + --current;
6.283 + unsigned long rnd = *current;
6.284 + rnd ^= (rnd >> 29) & 0x5555555555555555ul;
6.285 + rnd ^= (rnd << 17) & 0x71D67FFFEDA60000ul;
6.286 + rnd ^= (rnd << 37) & 0xFFF7EEE000000000ul;
6.287 + rnd ^= (rnd >> 43);
6.288 + return rnd;
6.289 + }
6.290 +
6.291 + /// \brief Returns a random number
6.292 + ///
6.293 + /// It returns an integer random number from the range
6.294 + /// \f$ \{-2^{63}, \dots, 2^{63} - 1\} \f$.
6.295 + long getInt() {
6.296 + return (long)getUnsigned();
6.297 + }
6.298 +
6.299 + /// \brief Returns an unsigned integer random number
6.300 + ///
6.301 + /// It returns an unsigned integer random number from the range
6.302 + /// \f$ \{0, 1, \dots, 2^{63} - 1\} \f$.
6.303 + long getNatural() {
6.304 + return (long)(getUnsigned() >> 1);
6.305 + }
6.306 +
6.307 + /// \brief Returns a random bool
6.308 + ///
6.309 + /// It returns a random bool.
6.310 + bool getBool() {
6.311 + return (bool)(getUnsigned() & 1);
6.312 + }
6.313 +
6.314 + /// \brief Returns a real random number
6.315 + ///
6.316 + /// It returns a real random number from the range
6.317 + /// \f$ [0, 1) \f$.
6.318 + double getReal() {
6.319 + return std::ldexp((double)(getUnsigned() >> 11), -53);
6.320 + }
6.321 +
6.322 + /// \brief Returns a real random number
6.323 + ///
6.324 + /// It returns a real random number from the range
6.325 + /// \f$ [0, 1) \f$. This function is identical to the \c getReal().
6.326 + double getPrecReal() {
6.327 + return getReal();
6.328 + }
6.329 +
6.330 + /// \brief Returns an unsigned random number from a given range
6.331 + ///
6.332 + /// It returns an unsigned integer random number from the range
6.333 + /// \f$ \{0, 1, \dots, n - 1\} \f$.
6.334 + unsigned long getUnsigned(unsigned long n) {
6.335 + unsigned long mask = n - 1, rnd;
6.336 + mask |= mask >> 1;
6.337 + mask |= mask >> 2;
6.338 + mask |= mask >> 4;
6.339 + mask |= mask >> 8;
6.340 + mask |= mask >> 16;
6.341 + mask |= mask >> 32;
6.342 + do rnd = getUnsigned() & mask; while (rnd >= n);
6.343 + return rnd;
6.344 + }
6.345 +
6.346 + /// \brief Returns a random number from a given range
6.347 + ///
6.348 + /// It returns an unsigned integer random number from the range
6.349 + /// \f$ \{0, 1, \dots, n - 1\} \f$.
6.350 + long getInt(long n) {
6.351 + long mask = n - 1, rnd;
6.352 + mask |= mask >> 1;
6.353 + mask |= mask >> 2;
6.354 + mask |= mask >> 4;
6.355 + mask |= mask >> 8;
6.356 + mask |= mask >> 16;
6.357 + mask |= mask >> 32;
6.358 + do rnd = getUnsigned() & mask; while (rnd >= n);
6.359 + return rnd;
6.360 + }
6.361 +
6.362 + private:
6.363 +
6.364 + void initState(unsigned long seed) {
6.365 +
6.366 + static const unsigned long mul = 0x5851F42D4C957F2Dul;
6.367 +
6.368 + current = state;
6.369 +
6.370 + unsigned long *curr = state + length - 1;
6.371 + curr[0] = seed; --curr;
6.372 + for (int i = 1; i < length; ++i) {
6.373 + curr[0] = (mul * ( curr[1] ^ (curr[1] >> 62) ) + i);
6.374 + --curr;
6.375 + }
6.376 + }
6.377 +
6.378 + void fillState() {
6.379 + static const unsigned long mask[2] = { 0x0ul, 0xB5026F5AA96619E9ul };
6.380 + static const unsigned long loMask = (1ul << 31) - 1;
6.381 + static const unsigned long hiMask = ~loMask;
6.382 +
6.383 + current = state + length;
6.384 +
6.385 + register unsigned long *curr = state + length - 1;
6.386 + register int num;
6.387 +
6.388 + num = length - shift;
6.389 + while (num--) {
6.390 + curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^
6.391 + curr[- shift] ^ mask[curr[-1] & 1ul];
6.392 + --curr;
6.393 + }
6.394 + num = shift - 1;
6.395 + while (num--) {
6.396 + curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^
6.397 + curr[length - shift] ^ mask[curr[-1] & 1ul];
6.398 + --curr;
6.399 + }
6.400 + curr[0] = (((curr[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
6.401 + curr[length - shift] ^ mask[curr[length - 1] & 1ul];
6.402 +
6.403 + }
6.404 +
6.405 + unsigned long *current;
6.406 + unsigned long state[length];
6.407 +
6.408 + };
6.409 +
6.410 +#else
6.411 +
6.412 + /// \brief Mersenne Twister random number generator
6.413 + ///
6.414 + /// The Mersenne Twister is a twisted generalized feedback
6.415 + /// shift-register generator of Matsumoto and Nishimura. There is
6.416 + /// two different implementation in the Lemon library, one for
6.417 + /// 32-bit processors and one for 64-bit processors. The period of
6.418 + /// the generated sequence is \f$ 2^{19937} - 1 \f$, the generated
6.419 + /// sequence of 32-bit random numbers is equi-distributed in 623
6.420 + /// dimensions. The time performance of this generator is comparable
6.421 + /// to the commonly used generators.
6.422 + class Random {
6.423 + public:
6.424 +
6.425 + static const unsigned long min = 0ul;
6.426 + static const unsigned long max = ~0ul;
6.427 +
6.428 + /// \brief Constructor
6.429 + ///
6.430 + /// Constructor with time dependent seeding.
6.431 + Random() {}
6.432 +
6.433 + /// \brief Constructor
6.434 + ///
6.435 + /// Constructor
6.436 + Random(unsigned long seed) {}
6.437 +
6.438 + /// \brief Copy constructor
6.439 + ///
6.440 + /// Copy constructor. The generated sequence will be identical to
6.441 + /// the other sequence.
6.442 + Random(const Random& other) {}
6.443 +
6.444 + /// \brief Assign operator
6.445 + ///
6.446 + /// Assign operator. The generated sequence will be identical to
6.447 + /// the other sequence.
6.448 + Random& operator=(const Random& other) { return *this; }
6.449 +
6.450 + /// \brief Returns an unsigned random number
6.451 + ///
6.452 + /// It returns an unsigned integer random number from the range
6.453 + /// \f$ \{0, 1, \dots, 2^{64} - 1\} \f$ for 64-bit processors and from
6.454 + /// \f$ \{0, 1, \dots, 2^{32} - 1\} \f$ for 32-bit processors.
6.455 + unsigned long getUnsigned() { return 0ul; }
6.456 +
6.457 + /// \brief Returns a random number
6.458 + ///
6.459 + /// It returns an integer random number from the range
6.460 + /// \f$ \{-2^{63}, \dots, 2^{63} - 1\} \f$ for 64-bit processors and from
6.461 + /// \f$ \{-2^{31}, \dots, 2^{31} - 1\} \f$ for 32-bit processors.
6.462 + long getInt() { return 0l; }
6.463 +
6.464 + /// \brief Returns an unsigned integer random number
6.465 + ///
6.466 + /// It returns an unsigned integer random number from the range
6.467 + /// \f$ \{0, 1, \dots, 2^{63} - 1\} \f$ for 64-bit processors and
6.468 + /// from \f$ \{0, 1, \dots, 2^{31} - 1\} \f$ for 32-bit processors.
6.469 + long getNatural() { return 0l; }
6.470 +
6.471 + /// \brief Returns a random bool
6.472 + ///
6.473 + /// It returns a random bool.
6.474 + bool getBool() { return false; }
6.475 +
6.476 + /// \brief Returns a real random number
6.477 + ///
6.478 + /// It returns a real random number from the range
6.479 + /// \f$ [0, 1) \f$. For 32-bit processors the generated random
6.480 + /// number will just have 32 significant bits.
6.481 + double getReal() { return 0.0; }
6.482 +
6.483 + /// \brief Returns a real random number
6.484 + ///
6.485 + /// It returns a real random number from the range
6.486 + /// \f$ [0, 1) \f$. This function returns random numbers with 53
6.487 + /// significant bits for 32-bit processors. For 64-bit processors
6.488 + /// it is identical to the \c getReal().
6.489 + double getPrecReal() { return 0.0; }
6.490 +
6.491 + /// \brief Returns an unsigned random number from a given range
6.492 + ///
6.493 + /// It returns an unsigned integer random number from the range
6.494 + /// \f$ \{0, 1, \dots, n - 1\} \f$.
6.495 + unsigned long getUnsigned(unsigned long n) { return 0; }
6.496 +
6.497 + /// \brief Returns a random number from a given range
6.498 + ///
6.499 + /// It returns an unsigned integer random number from the range
6.500 + /// \f$ \{0, 1, \dots, n - 1\} \f$.
6.501 + long getInt(long n) { return 0; }
6.502 +
6.503 + };
6.504 +
6.505 +#endif
6.506 +
6.507 + /// \brief Global random number generator instance
6.508 + ///
6.509 + /// A global mersenne twister random number generator instance
6.510 + extern Random rnd;
6.511 +
6.512 +}
6.513 +
6.514 +#endif
7.1 --- a/lemon/simann.h Mon Oct 02 14:41:53 2006 +0000
7.2 +++ b/lemon/simann.h Mon Oct 02 16:11:00 2006 +0000
7.3 @@ -31,10 +31,7 @@
7.4 #include <cmath>
7.5 #include <limits>
7.6 #include <lemon/time_measure.h>
7.7 -
7.8 -#ifdef WIN32
7.9 -#include <lemon/bits/mingw32_rand.h>
7.10 -#endif
7.11 +#include <lemon/random.h>
7.12
7.13 namespace lemon {
7.14
7.15 @@ -241,7 +238,6 @@
7.16 double _temp = 1000.0, double _ann_fact = 0.9999) : max_iter(_max_iter),
7.17 max_no_impr(_max_no_impr), temp(_temp), ann_fact(_ann_fact)
7.18 {
7.19 - srand48(time(0));
7.20 }
7.21 /// \brief This is called when a neighbouring state gets accepted.
7.22 void acceptEvent() {}
7.23 @@ -261,7 +257,7 @@
7.24 /// \brief Decides whether to accept the current solution or not.
7.25 bool accept() {
7.26 double cost_diff = simann->getCurrCost() - simann->getPrevCost();
7.27 - return (drand48() <= exp(-(cost_diff / temp)));
7.28 + return (rnd.getReal() <= exp(-(cost_diff / temp)));
7.29 }
7.30 /// \brief Destructor.
7.31 virtual ~SimpleController() {}
7.32 @@ -321,7 +317,6 @@
7.33 alpha(_alpha), beta(_beta), gamma(_gamma), end_time(_end_time),
7.34 ann_fact(_ann_fact), init_ann_fact(_ann_fact), start(false)
7.35 {
7.36 - srand48(time(0));
7.37 }
7.38 /// \brief Does initializations before each run.
7.39 void init() {
7.40 @@ -370,7 +365,7 @@
7.41 }
7.42 else {
7.43 double cost_diff = simann->getCurrCost() - simann->getPrevCost();
7.44 - return (drand48() <= exp(-(cost_diff / temp)));
7.45 + return (rnd.getReal() <= exp(-(cost_diff / temp)));
7.46 }
7.47 }
7.48 /// \brief Destructor.
8.1 --- a/test/graph_utils_test.h Mon Oct 02 14:41:53 2006 +0000
8.2 +++ b/test/graph_utils_test.h Mon Oct 02 16:11:00 2006 +0000
8.3 @@ -50,15 +50,14 @@
8.4 typedef typename Graph::NodeIt NodeIt;
8.5 typedef typename Graph::EdgeIt EdgeIt;
8.6 Graph graph;
8.7 - srand(time(0));
8.8 for (int i = 0; i < 10; ++i) {
8.9 graph.addNode();
8.10 }
8.11 DescriptorMap<Graph, Node> nodes(graph);
8.12 typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
8.13 for (int i = 0; i < 100; ++i) {
8.14 - int src = (int)(rand() / (RAND_MAX + 1.0) * invNodes.size());
8.15 - int trg = (int)(rand() / (RAND_MAX + 1.0) * invNodes.size());
8.16 + int src = rnd.getInt(invNodes.size());
8.17 + int trg = rnd.getInt(invNodes.size());
8.18 graph.addEdge(invNodes[src], invNodes[trg]);
8.19 }
8.20 typename Graph::template EdgeMap<bool> found(graph, false);
9.1 --- a/test/heap_test.h Mon Oct 02 14:41:53 2006 +0000
9.2 +++ b/test/heap_test.h Mon Oct 02 16:11:00 2006 +0000
9.3 @@ -45,7 +45,7 @@
9.4 std::vector<int> v(n);
9.5
9.6 for (int i = 0; i < n; ++i) {
9.7 - v[i] = rand() % 1000;
9.8 + v[i] = rnd.getInt(1000);
9.9 heap.push(i, v[i]);
9.10 }
9.11 std::sort(v.begin(), v.end());
9.12 @@ -65,11 +65,11 @@
9.13 std::vector<int> v(n);
9.14
9.15 for (int i = 0; i < n; ++i) {
9.16 - v[i] = rand() % 1000;
9.17 + v[i] = rnd.getInt(1000);
9.18 heap.push(i, v[i]);
9.19 }
9.20 for (int i = 0; i < n; ++i) {
9.21 - v[i] += rand() % 1000;
9.22 + v[i] += rnd.getInt(1000);
9.23 heap.increase(i, v[i]);
9.24 }
9.25 std::sort(v.begin(), v.end());
10.1 --- a/test/test_tools.h Mon Oct 02 14:41:53 2006 +0000
10.2 +++ b/test/test_tools.h Mon Oct 02 16:11:00 2006 +0000
10.3 @@ -28,6 +28,8 @@
10.4 #include <lemon/concept_check.h>
10.5 #include <lemon/concept/graph.h>
10.6
10.7 +#include <lemon/random.h>
10.8 +
10.9 using namespace lemon;
10.10
10.11 //! \ingroup misc
10.12 @@ -176,16 +178,8 @@
10.13 return n;
10.14 }
10.15
10.16 -int _urandom_init() {
10.17 - int seed = time(0);
10.18 - srand(seed);
10.19 - return seed;
10.20 -}
10.21 -
10.22 int urandom(int n) {
10.23 - static int seed = _urandom_init();
10.24 - ignore_unused_variable_warning(seed);
10.25 - return (int)(rand() / (1.0 + RAND_MAX) * n);
10.26 + return rnd.getInt(n);
10.27 }
10.28
10.29 #endif