001/*
002 * Copyright 2006 - 2013
003 *     Stefan Balev     <stefan.balev@graphstream-project.org>
004 *     Julien Baudry    <julien.baudry@graphstream-project.org>
005 *     Antoine Dutot    <antoine.dutot@graphstream-project.org>
006 *     Yoann Pigné      <yoann.pigne@graphstream-project.org>
007 *     Guilhelm Savin   <guilhelm.savin@graphstream-project.org>
008 * 
009 * This file is part of GraphStream <http://graphstream-project.org>.
010 * 
011 * GraphStream is a library whose purpose is to handle static or dynamic
012 * graph, create them from scratch, file or any source and display them.
013 * 
014 * This program is free software distributed under the terms of two licenses, the
015 * CeCILL-C license that fits European law, and the GNU Lesser General Public
016 * License. You can  use, modify and/ or redistribute the software under the terms
017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by
019 * the Free Software Foundation, either version 3 of the License, or (at your
020 * option) any later version.
021 * 
022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY
023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
024 * PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more details.
025 * 
026 * You should have received a copy of the GNU Lesser General Public License
027 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
028 * 
029 * The fact that you are presently reading this means that you have had
030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms.
031 */
032package org.graphstream.algorithm.util;
033
034import java.util.HashSet;
035import java.util.Random;
036import java.util.Set;
037
038/**
039 * This class provides several static methods for generating random numbers and
040 * sets
041 */
042public class RandomTools {
043
044        /**
045         * Returns a pseudorandom number drawn from exponential distribution with
046         * mean 1.
047         * 
048         * Uses the von Neumann's exponential generator.
049         * 
050         * @param rnd
051         *            source of randomness
052         * @return a pseudorandom number drawn from exponential distribution with
053         *         mean 1.
054         * @complexity O(1) average complexity. The expected number of uniformly
055         *             distributed numbers used is e^2 / (e - 1)
056         * 
057         */
058        public static double exponential(Random rnd) {
059                double y, w, u;
060                int z, k;
061                z = -1;
062                do {
063                        w = y = rnd.nextDouble();
064                        k = 1;
065                        while (true) {
066                                u = rnd.nextDouble();
067                                if (u > w)
068                                        break;
069                                w = u;
070                                k++;
071                        }
072                        z++;
073                } while ((k & 1) == 0);
074                return z + y;
075        }
076
077        /**
078         * Returns a pseudorandom number drawn from binomial distribution B(n, p).
079         * 
080         * Uses a simple waiting time method based on exponential distribution.
081         * 
082         * @param n
083         *            number of tries
084         * @param p
085         *            success probability
086         * @param rnd
087         *            source of randomness
088         * @return a pseudorandom number drawn from binomial distribution
089         * @complexity Average complexity O(np)
090         */
091        public static int binomial(int n, double p, Random rnd) {
092                double q = -Math.log(1 - p);
093                int x = 0;
094                double s = 0;
095                do {
096                        s += exponential(rnd) / (n - x);
097                        x++;
098                } while (s <= q);
099                return x - 1;
100        }
101
102        /**
103         * Generates a pseudorandom subset of size k of the set {0, 1,...,n - 1}.
104         * Each element has the same chance to be chosen.
105         * 
106         * Uses Floyd's method of subset generation with only k iterations. Note
107         * that the quality of this generator is limited by Java's random generator.
108         * Java stores the internal state in 48 bits, so in the best case we can
109         * only generate 2^48 different subsets.
110         * 
111         * @param n
112         *            the size of the initial set
113         * @param k
114         *            the size of the generated set
115         * @param subset
116         *            if not null, this set is cleared and the result is stored
117         *            here. This avoids creations of sets at each call of this
118         *            method
119         * @param rnd
120         *            source of randomness
121         * @return a pseudorandom subset of size k of the set {0, 1,...,n}
122         * @complexity Depends on the set implementation. If add and lookup
123         *             operations take constant time, the complexity is O(k)
124         */
125        public static Set<Integer> randomKsubset(int n, int k, Set<Integer> subset,
126                        Random rnd) {
127                if (subset == null)
128                        subset = new HashSet<Integer>(4 * k / 3 + 1);
129                else
130                        subset.clear();
131                for (int i = n - k; i < n; i++) {
132                        int j = rnd.nextInt(i + 1);
133                        subset.add(subset.contains(j) ? i : j);
134                }
135                return subset;
136        }
137
138        /**
139         * Generates a pseudorandom subset of the set {0, 1,...,n - 1}. Each element
140         * is chosen with probability p.
141         * 
142         * @param n
143         *            the size of the initial set
144         * @param p
145         *            the probability to choose each element
146         * @param subset
147         *            if not null, this set is cleared and the result is stored
148         *            here. This avoids creations of sets at each call of this
149         *            method
150         * @param rnd
151         *            source of randomness
152         * @return a pseudorandom subset of the set {0, 1,...,n}.
153         * @complexity Depends on the set implementation. If add and lookup
154         *             operations take constant time, the complexity is O(np)
155         */
156        public static Set<Integer> randomPsubset(int n, double p,
157                        Set<Integer> subset, Random rnd) {
158                return randomKsubset(n, binomial(n, p, rnd), subset, rnd);
159        }
160}