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}