Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/utils/random_sequence.py: 26%

1""" 

2Utilities for generating random numbers, random sequences, and 

3random selections. 

4""" 

5 

6import networkx as nx 

7from networkx.utils import py_random_state 

8 

9__all__ = [ 

10 "powerlaw_sequence", 

11 "zipf_rv", 

12 "cumulative_distribution", 

13 "discrete_sequence", 

14 "random_weighted_sample", 

15 "weighted_choice", 

16] 

17 

18 

19# The same helpers for choosing random sequences from distributions 

20# uses Python's random module 

21# https://docs.python.org/3/library/random.html 

22 

23 

24@py_random_state(2) 

25def powerlaw_sequence(n, exponent=2.0, seed=None): 

26 """ 

27 Return sample sequence of length n from a power law distribution. 

28 """ 

29 return [seed.paretovariate(exponent - 1) for i in range(n)] 

30 

31 

32@py_random_state(2) 

33def zipf_rv(alpha, xmin=1, seed=None): 

34 r"""Returns a random value chosen from the Zipf distribution. 

35 

36 The return value is an integer drawn from the probability distribution 

37 

38 .. math:: 

39 

40 p(x)=\frac{x^{-\alpha}}{\zeta(\alpha, x_{\min})}, 

41 

42 where $\zeta(\alpha, x_{\min})$ is the Hurwitz zeta function. 

43 

44 Parameters 

45 ---------- 

46 alpha : float 

47 Exponent value of the distribution 

48 xmin : int 

49 Minimum value 

50 seed : integer, random_state, or None (default) 

51 Indicator of random number generation state. 

52 See :ref:`Randomness<randomness>`. 

53 

54 Returns 

55 ------- 

56 x : int 

57 Random value from Zipf distribution 

58 

59 Raises 

60 ------ 

61 ValueError: 

62 If xmin < 1 or 

63 If alpha <= 1 

64 

65 Notes 

66 ----- 

67 The rejection algorithm generates random values for a the power-law 

68 distribution in uniformly bounded expected time dependent on 

69 parameters. See [1]_ for details on its operation. 

70 

71 Examples 

72 -------- 

73 >>> nx.utils.zipf_rv(alpha=2, xmin=3, seed=42) 

74 8 

75 

76 References 

77 ---------- 

78 .. [1] Luc Devroye, Non-Uniform Random Variate Generation, 

79 Springer-Verlag, New York, 1986. 

80 """ 

81 if xmin < 1: 

82 raise ValueError("xmin < 1") 

83 if alpha <= 1: 

84 raise ValueError("a <= 1.0") 

85 a1 = alpha - 1.0 

86 b = 2**a1 

87 while True: 

88 u = 1.0 - seed.random() # u in (0,1] 

89 v = seed.random() # v in [0,1) 

90 x = int(xmin * u ** -(1.0 / a1)) 

91 t = (1.0 + (1.0 / x)) ** a1 

92 if v * x * (t - 1.0) / (b - 1.0) <= t / b: 

93 break 

94 return x 

95 

96 

97def cumulative_distribution(distribution): 

98 """Returns normalized cumulative distribution from discrete distribution.""" 

99 

100 cdf = [0.0] 

101 psum = sum(distribution) 

102 for i in range(len(distribution)): 

103 cdf.append(cdf[i] + distribution[i] / psum) 

104 return cdf 

105 

106 

107@py_random_state(3) 

108def discrete_sequence(n, distribution=None, cdistribution=None, seed=None): 

109 """ 

110 Return sample sequence of length n from a given discrete distribution 

111 or discrete cumulative distribution. 

112 

113 One of the following must be specified. 

114 

115 distribution = histogram of values, will be normalized 

116 

117 cdistribution = normalized discrete cumulative distribution 

118 

119 """ 

120 import bisect 

121 

122 if cdistribution is not None: 

123 cdf = cdistribution 

124 elif distribution is not None: 

125 cdf = cumulative_distribution(distribution) 

126 else: 

127 raise nx.NetworkXError( 

128 "discrete_sequence: distribution or cdistribution missing" 

129 ) 

130 

131 # get a uniform random number 

132 inputseq = [seed.random() for i in range(n)] 

133 

134 # choose from CDF 

135 seq = [bisect.bisect_left(cdf, s) - 1 for s in inputseq] 

136 return seq 

137 

138 

139@py_random_state(2) 

140def random_weighted_sample(mapping, k, seed=None): 

141 """Returns k items without replacement from a weighted sample. 

142 

143 The input is a dictionary of items with weights as values. 

144 """ 

145 if k > len(mapping): 

146 raise ValueError("sample larger than population") 

147 sample = set() 

148 while len(sample) < k: 

149 sample.add(weighted_choice(mapping, seed)) 

150 return list(sample) 

151 

152 

153@py_random_state(1) 

154def weighted_choice(mapping, seed=None): 

155 """Returns a single element from a weighted sample. 

156 

157 The input is a dictionary of items with weights as values. 

158 """ 

159 # use roulette method 

160 rnd = seed.random() * sum(mapping.values()) 

161 for k, w in mapping.items(): 

162 rnd -= w 

163 if rnd < 0: 

164 return k