Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/utils/random_sequence.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # Copyright (C) 2004-2019 by
2 # Aric Hagberg <hagberg@lanl.gov>
3 # Dan Schult <dschult@colgate.edu>
4 # Pieter Swart <swart@lanl.gov>
5 # All rights reserved.
6 # BSD license.
7 #
8 # Authors: Aric Hagberg (hagberg@lanl.gov)
9 # Dan Schult (dschult@colgate.edu)
10 # Ben Edwards (bedwards@cs.unm.edu)
11 """
12 Utilities for generating random numbers, random sequences, and
13 random selections.
14 """
15
16 import random
17 import sys
18 import networkx as nx
19 from networkx.utils import py_random_state
20
21
22 # The same helpers for choosing random sequences from distributions
23 # uses Python's random module
24 # https://docs.python.org/2/library/random.html
25
26 @py_random_state(2)
27 def powerlaw_sequence(n, exponent=2.0, seed=None):
28 """
29 Return sample sequence of length n from a power law distribution.
30 """
31 return [seed.paretovariate(exponent - 1) for i in range(n)]
32
33
34 @py_random_state(2)
35 def zipf_rv(alpha, xmin=1, seed=None):
36 r"""Returns a random value chosen from the Zipf distribution.
37
38 The return value is an integer drawn from the probability distribution
39
40 .. math::
41
42 p(x)=\frac{x^{-\alpha}}{\zeta(\alpha, x_{\min})},
43
44 where $\zeta(\alpha, x_{\min})$ is the Hurwitz zeta function.
45
46 Parameters
47 ----------
48 alpha : float
49 Exponent value of the distribution
50 xmin : int
51 Minimum value
52 seed : integer, random_state, or None (default)
53 Indicator of random number generation state.
54 See :ref:`Randomness<randomness>`.
55
56 Returns
57 -------
58 x : int
59 Random value from Zipf distribution
60
61 Raises
62 ------
63 ValueError:
64 If xmin < 1 or
65 If alpha <= 1
66
67 Notes
68 -----
69 The rejection algorithm generates random values for a the power-law
70 distribution in uniformly bounded expected time dependent on
71 parameters. See [1]_ for details on its operation.
72
73 Examples
74 --------
75 >>> nx.zipf_rv(alpha=2, xmin=3, seed=42) # doctest: +SKIP
76
77 References
78 ----------
79 .. [1] Luc Devroye, Non-Uniform Random Variate Generation,
80 Springer-Verlag, New York, 1986.
81 """
82 if xmin < 1:
83 raise ValueError("xmin < 1")
84 if alpha <= 1:
85 raise ValueError("a <= 1.0")
86 a1 = alpha - 1.0
87 b = 2**a1
88 while True:
89 u = 1.0 - seed.random() # u in (0,1]
90 v = seed.random() # v in [0,1)
91 x = int(xmin * u**-(1.0 / a1))
92 t = (1.0 + (1.0 / x))**a1
93 if v * x * (t - 1.0) / (b - 1.0) <= t / b:
94 break
95 return x
96
97
98 def cumulative_distribution(distribution):
99 """Returns normalized cumulative distribution from discrete distribution."""
100
101 cdf = [0.0]
102 psum = float(sum(distribution))
103 for i in range(0, len(distribution)):
104 cdf.append(cdf[i] + distribution[i] / psum)
105 return cdf
106
107
108 @py_random_state(3)
109 def discrete_sequence(n, distribution=None, cdistribution=None, seed=None):
110 """
111 Return sample sequence of length n from a given discrete distribution
112 or discrete cumulative distribution.
113
114 One of the following must be specified.
115
116 distribution = histogram of values, will be normalized
117
118 cdistribution = normalized discrete cumulative distribution
119
120 """
121 import bisect
122
123 if cdistribution is not None:
124 cdf = cdistribution
125 elif distribution is not None:
126 cdf = cumulative_distribution(distribution)
127 else:
128 raise nx.NetworkXError(
129 "discrete_sequence: distribution or cdistribution missing")
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)
140 def 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)
154 def 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