Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/utils/random_sequence.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Utilities for generating random numbers, random sequences, and | |
3 random selections. | |
4 """ | |
5 | |
6 import networkx as nx | |
7 from networkx.utils import py_random_state | |
8 | |
9 | |
10 # The same helpers for choosing random sequences from distributions | |
11 # uses Python's random module | |
12 # https://docs.python.org/3/library/random.html | |
13 | |
14 | |
15 @py_random_state(2) | |
16 def powerlaw_sequence(n, exponent=2.0, seed=None): | |
17 """ | |
18 Return sample sequence of length n from a power law distribution. | |
19 """ | |
20 return [seed.paretovariate(exponent - 1) for i in range(n)] | |
21 | |
22 | |
23 @py_random_state(2) | |
24 def zipf_rv(alpha, xmin=1, seed=None): | |
25 r"""Returns a random value chosen from the Zipf distribution. | |
26 | |
27 The return value is an integer drawn from the probability distribution | |
28 | |
29 .. math:: | |
30 | |
31 p(x)=\frac{x^{-\alpha}}{\zeta(\alpha, x_{\min})}, | |
32 | |
33 where $\zeta(\alpha, x_{\min})$ is the Hurwitz zeta function. | |
34 | |
35 Parameters | |
36 ---------- | |
37 alpha : float | |
38 Exponent value of the distribution | |
39 xmin : int | |
40 Minimum value | |
41 seed : integer, random_state, or None (default) | |
42 Indicator of random number generation state. | |
43 See :ref:`Randomness<randomness>`. | |
44 | |
45 Returns | |
46 ------- | |
47 x : int | |
48 Random value from Zipf distribution | |
49 | |
50 Raises | |
51 ------ | |
52 ValueError: | |
53 If xmin < 1 or | |
54 If alpha <= 1 | |
55 | |
56 Notes | |
57 ----- | |
58 The rejection algorithm generates random values for a the power-law | |
59 distribution in uniformly bounded expected time dependent on | |
60 parameters. See [1]_ for details on its operation. | |
61 | |
62 Examples | |
63 -------- | |
64 >>> nx.utils.zipf_rv(alpha=2, xmin=3, seed=42) | |
65 8 | |
66 | |
67 References | |
68 ---------- | |
69 .. [1] Luc Devroye, Non-Uniform Random Variate Generation, | |
70 Springer-Verlag, New York, 1986. | |
71 """ | |
72 if xmin < 1: | |
73 raise ValueError("xmin < 1") | |
74 if alpha <= 1: | |
75 raise ValueError("a <= 1.0") | |
76 a1 = alpha - 1.0 | |
77 b = 2 ** a1 | |
78 while True: | |
79 u = 1.0 - seed.random() # u in (0,1] | |
80 v = seed.random() # v in [0,1) | |
81 x = int(xmin * u ** -(1.0 / a1)) | |
82 t = (1.0 + (1.0 / x)) ** a1 | |
83 if v * x * (t - 1.0) / (b - 1.0) <= t / b: | |
84 break | |
85 return x | |
86 | |
87 | |
88 def cumulative_distribution(distribution): | |
89 """Returns normalized cumulative distribution from discrete distribution.""" | |
90 | |
91 cdf = [0.0] | |
92 psum = float(sum(distribution)) | |
93 for i in range(0, len(distribution)): | |
94 cdf.append(cdf[i] + distribution[i] / psum) | |
95 return cdf | |
96 | |
97 | |
98 @py_random_state(3) | |
99 def discrete_sequence(n, distribution=None, cdistribution=None, seed=None): | |
100 """ | |
101 Return sample sequence of length n from a given discrete distribution | |
102 or discrete cumulative distribution. | |
103 | |
104 One of the following must be specified. | |
105 | |
106 distribution = histogram of values, will be normalized | |
107 | |
108 cdistribution = normalized discrete cumulative distribution | |
109 | |
110 """ | |
111 import bisect | |
112 | |
113 if cdistribution is not None: | |
114 cdf = cdistribution | |
115 elif distribution is not None: | |
116 cdf = cumulative_distribution(distribution) | |
117 else: | |
118 raise nx.NetworkXError( | |
119 "discrete_sequence: distribution or cdistribution missing" | |
120 ) | |
121 | |
122 # get a uniform random number | |
123 inputseq = [seed.random() for i in range(n)] | |
124 | |
125 # choose from CDF | |
126 seq = [bisect.bisect_left(cdf, s) - 1 for s in inputseq] | |
127 return seq | |
128 | |
129 | |
130 @py_random_state(2) | |
131 def random_weighted_sample(mapping, k, seed=None): | |
132 """Returns k items without replacement from a weighted sample. | |
133 | |
134 The input is a dictionary of items with weights as values. | |
135 """ | |
136 if k > len(mapping): | |
137 raise ValueError("sample larger than population") | |
138 sample = set() | |
139 while len(sample) < k: | |
140 sample.add(weighted_choice(mapping, seed)) | |
141 return list(sample) | |
142 | |
143 | |
144 @py_random_state(1) | |
145 def weighted_choice(mapping, seed=None): | |
146 """Returns a single element from a weighted sample. | |
147 | |
148 The input is a dictionary of items with weights as values. | |
149 """ | |
150 # use roulette method | |
151 rnd = seed.random() * sum(mapping.values()) | |
152 for k, w in mapping.items(): | |
153 rnd -= w | |
154 if rnd < 0: | |
155 return k |