---

randomizer.h

/****************************************************
 *  Bachelor Project:                               *
 *  External Memory Minimum Spanning Trees          *
 *  by Dominik Schultes <mail@dominik-schultes.de>  *
 *                                                  *
 *                randomizer.h                      *
 *                                                  *
 *  May 22, 2003                                    *
 ****************************************************/


#ifndef RANDOMIZER_H
#define RANDOMIZER_H

class RandomizerLinearCongruence
{
 public:
    RandomizerLinearCongruence(NodeCount noOfNodes)
        {determineNextPrime(noOfNodes);}

    NodeID operator()(NodeID nodeID) const {
        typedef unsigned long long int bigNumber;
        
        bigNumber x = nodeID;
        const bigNumber a = 321321;
        const bigNumber c = 1;
        bigNumber m = _prime;

        // the linear congruential method
        return (a * x + c) % m;
    }
    
 private:
    NodeCount _prime;

    void determineNextPrime(NodeCount noOfNodes) {
        NodeCount p;
        for (p = noOfNodes-1; ! isPrime(p); p++);
        _prime = p;
    }

    bool isPrime(NodeCount p) const {
        for (NodeCount i=2; i <= std::sqrt((double)p); i++) {
            if (p % i == 0) return false;
        }
        return true;
    }
};


class RandomizerFeistel
{
 public:
    RandomizerFeistel(NodeCount noOfNodes) {
        // compute the next integer >= the square root of the given number of nodes
        _sqRoot = (NodeID)std::sqrt((double)noOfNodes);
        if ((NodeCount)_sqRoot * _sqRoot < noOfNodes) _sqRoot++;
        // initialize the table of random numbers (used by the Feistel permutations)
        initRandomNumbers();
    }

    NodeID operator()(NodeID nodeID) const {
        // Split the given number into two parts
        int a = nodeID / _sqRoot;
        int b = nodeID % _sqRoot;

        // Perform the Feistel permutations
        for (int i=0; i<_noOfIterations; i++) {
            int newA = b;
            b = a + randomNumbers[i][b];
            if (b >= _sqRoot) b -= _sqRoot; // mod _sqRoot
            a = newA;
        }

        // Recombine a and b to obtain the result
        return a * _sqRoot + b;
    }
        
 private:
    static const int _noOfIterations = 2;
    
    static const int _maxSqRoot = 0x10000;

    NodeID _sqRoot;

    int randomNumbers[_noOfIterations][_maxSqRoot];

    void initRandomNumbers() {
        for (int i=0; i<_noOfIterations; i++)
            for (int j=0; j<_maxSqRoot; j++) {
                // each random number is an integer in {0,...,_sqRoot-1}
                randomNumbers[i][j] = (int)(rand() / (double)(RAND_MAX+1.0) * _sqRoot);
            }
    }
};


template <typename Bijection = RandomizerLinearCongruence>
class Randomizer
{
 public:
    Randomizer(NodeCount noOfNodes)
        : _noOfNodes( noOfNodes ), _bijection( noOfNodes )
        {}

    RelabeledEdge randomize(const Edge &edge) const {
        return RelabeledEdge(randomize(edge.source()),randomize(edge.target()),
                             edge.weight(),edge.source(),edge.target());
    }
        
 private:
    NodeCount _noOfNodes;

    Bijection _bijection;

    NodeID randomize(NodeID nodeID) const {
        NodeID x = nodeID;
        
        // The application of the underlying bijection is repeated
        // until the result is in the correct co-domain.
        do {
            x = _bijection( x );
        } while (x >= _noOfNodes);
        
        return x;
    }
    
};

#endif // RANDOMIZER_H

---