Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/generators/directed.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 # -*- coding: utf-8 -*-
2 # Copyright (C) 2006-2019 by
3 # Aric Hagberg <hagberg@lanl.gov>
4 # Dan Schult <dschult@colgate.edu>
5 # Pieter Swart <swart@lanl.gov>
6 # Copyright (C) 2009 by Willem Ligtenberg <W.P.A.Ligtenberg@tue.nl>
7 # All rights reserved.
8 # BSD license.
9 #
10 # Authors: Aric Hagberg (hagberg@lanl.gov)
11 # Willem Ligtenberg (W.P.A.Ligtenberg@tue.nl)
12 """
13 Generators for some directed graphs, including growing network (GN) graphs and
14 scale-free graphs.
15
16 """
17
18 from collections import Counter
19
20 import networkx as nx
21 from networkx.generators.classic import empty_graph
22 from networkx.utils import discrete_sequence
23 from networkx.utils import weighted_choice
24 from networkx.utils import py_random_state
25
26 __all__ = ['gn_graph', 'gnc_graph', 'gnr_graph', 'random_k_out_graph',
27 'scale_free_graph']
28
29
30 @py_random_state(3)
31 def gn_graph(n, kernel=None, create_using=None, seed=None):
32 """Returns the growing network (GN) digraph with `n` nodes.
33
34 The GN graph is built by adding nodes one at a time with a link to one
35 previously added node. The target node for the link is chosen with
36 probability based on degree. The default attachment kernel is a linear
37 function of the degree of a node.
38
39 The graph is always a (directed) tree.
40
41 Parameters
42 ----------
43 n : int
44 The number of nodes for the generated graph.
45 kernel : function
46 The attachment kernel.
47 create_using : NetworkX graph constructor, optional (default DiGraph)
48 Graph type to create. If graph instance, then cleared before populated.
49 seed : integer, random_state, or None (default)
50 Indicator of random number generation state.
51 See :ref:`Randomness<randomness>`.
52
53 Examples
54 --------
55 To create the undirected GN graph, use the :meth:`~DiGraph.to_directed`
56 method::
57
58 >>> D = nx.gn_graph(10) # the GN graph
59 >>> G = D.to_undirected() # the undirected version
60
61 To specify an attachment kernel, use the `kernel` keyword argument::
62
63 >>> D = nx.gn_graph(10, kernel=lambda x: x ** 1.5) # A_k = k^1.5
64
65 References
66 ----------
67 .. [1] P. L. Krapivsky and S. Redner,
68 Organization of Growing Random Networks,
69 Phys. Rev. E, 63, 066123, 2001.
70 """
71 G = empty_graph(1, create_using, default=nx.DiGraph)
72 if not G.is_directed():
73 raise nx.NetworkXError("create_using must indicate a Directed Graph")
74
75 if kernel is None:
76 def kernel(x): return x
77
78 if n == 1:
79 return G
80
81 G.add_edge(1, 0) # get started
82 ds = [1, 1] # degree sequence
83
84 for source in range(2, n):
85 # compute distribution from kernel and degree
86 dist = [kernel(d) for d in ds]
87 # choose target from discrete distribution
88 target = discrete_sequence(1, distribution=dist, seed=seed)[0]
89 G.add_edge(source, target)
90 ds.append(1) # the source has only one link (degree one)
91 ds[target] += 1 # add one to the target link degree
92 return G
93
94
95 @py_random_state(3)
96 def gnr_graph(n, p, create_using=None, seed=None):
97 """Returns the growing network with redirection (GNR) digraph with `n`
98 nodes and redirection probability `p`.
99
100 The GNR graph is built by adding nodes one at a time with a link to one
101 previously added node. The previous target node is chosen uniformly at
102 random. With probabiliy `p` the link is instead "redirected" to the
103 successor node of the target.
104
105 The graph is always a (directed) tree.
106
107 Parameters
108 ----------
109 n : int
110 The number of nodes for the generated graph.
111 p : float
112 The redirection probability.
113 create_using : NetworkX graph constructor, optional (default DiGraph)
114 Graph type to create. If graph instance, then cleared before populated.
115 seed : integer, random_state, or None (default)
116 Indicator of random number generation state.
117 See :ref:`Randomness<randomness>`.
118
119 Examples
120 --------
121 To create the undirected GNR graph, use the :meth:`~DiGraph.to_directed`
122 method::
123
124 >>> D = nx.gnr_graph(10, 0.5) # the GNR graph
125 >>> G = D.to_undirected() # the undirected version
126
127 References
128 ----------
129 .. [1] P. L. Krapivsky and S. Redner,
130 Organization of Growing Random Networks,
131 Phys. Rev. E, 63, 066123, 2001.
132 """
133 G = empty_graph(1, create_using, default=nx.DiGraph)
134 if not G.is_directed():
135 raise nx.NetworkXError("create_using must indicate a Directed Graph")
136
137 if n == 1:
138 return G
139
140 for source in range(1, n):
141 target = seed.randrange(0, source)
142 if seed.random() < p and target != 0:
143 target = next(G.successors(target))
144 G.add_edge(source, target)
145 return G
146
147
148 @py_random_state(2)
149 def gnc_graph(n, create_using=None, seed=None):
150 """Returns the growing network with copying (GNC) digraph with `n` nodes.
151
152 The GNC graph is built by adding nodes one at a time with a link to one
153 previously added node (chosen uniformly at random) and to all of that
154 node's successors.
155
156 Parameters
157 ----------
158 n : int
159 The number of nodes for the generated graph.
160 create_using : NetworkX graph constructor, optional (default DiGraph)
161 Graph type to create. If graph instance, then cleared before populated.
162 seed : integer, random_state, or None (default)
163 Indicator of random number generation state.
164 See :ref:`Randomness<randomness>`.
165
166 References
167 ----------
168 .. [1] P. L. Krapivsky and S. Redner,
169 Network Growth by Copying,
170 Phys. Rev. E, 71, 036118, 2005k.},
171 """
172 G = empty_graph(1, create_using, default=nx.DiGraph)
173 if not G.is_directed():
174 raise nx.NetworkXError("create_using must indicate a Directed Graph")
175
176 if n == 1:
177 return G
178
179 for source in range(1, n):
180 target = seed.randrange(0, source)
181 for succ in G.successors(target):
182 G.add_edge(source, succ)
183 G.add_edge(source, target)
184 return G
185
186
187 @py_random_state(7)
188 def scale_free_graph(n, alpha=0.41, beta=0.54, gamma=0.05, delta_in=0.2,
189 delta_out=0, create_using=None, seed=None):
190 """Returns a scale-free directed graph.
191
192 Parameters
193 ----------
194 n : integer
195 Number of nodes in graph
196 alpha : float
197 Probability for adding a new node connected to an existing node
198 chosen randomly according to the in-degree distribution.
199 beta : float
200 Probability for adding an edge between two existing nodes.
201 One existing node is chosen randomly according the in-degree
202 distribution and the other chosen randomly according to the out-degree
203 distribution.
204 gamma : float
205 Probability for adding a new node connected to an existing node
206 chosen randomly according to the out-degree distribution.
207 delta_in : float
208 Bias for choosing nodes from in-degree distribution.
209 delta_out : float
210 Bias for choosing nodes from out-degree distribution.
211 create_using : NetworkX graph constructor, optional
212 The default is a MultiDiGraph 3-cycle.
213 If a graph instance, use it without clearing first.
214 If a graph constructor, call it to construct an empty graph.
215 seed : integer, random_state, or None (default)
216 Indicator of random number generation state.
217 See :ref:`Randomness<randomness>`.
218
219 Examples
220 --------
221 Create a scale-free graph on one hundred nodes::
222
223 >>> G = nx.scale_free_graph(100)
224
225 Notes
226 -----
227 The sum of `alpha`, `beta`, and `gamma` must be 1.
228
229 References
230 ----------
231 .. [1] B. Bollobás, C. Borgs, J. Chayes, and O. Riordan,
232 Directed scale-free graphs,
233 Proceedings of the fourteenth annual ACM-SIAM Symposium on
234 Discrete Algorithms, 132--139, 2003.
235 """
236
237 def _choose_node(G, distribution, delta, psum):
238 cumsum = 0.0
239 # normalization
240 r = seed.random()
241 for n, d in distribution:
242 cumsum += (d + delta) / psum
243 if r < cumsum:
244 break
245 return n
246
247 if create_using is None or not hasattr(create_using, '_adj'):
248 # start with 3-cycle
249 G = nx.empty_graph(3, create_using, default=nx.MultiDiGraph)
250 G.add_edges_from([(0, 1), (1, 2), (2, 0)])
251 else:
252 G = create_using
253 if not (G.is_directed() and G.is_multigraph()):
254 raise nx.NetworkXError("MultiDiGraph required in create_using")
255
256 if alpha <= 0:
257 raise ValueError('alpha must be > 0.')
258 if beta <= 0:
259 raise ValueError('beta must be > 0.')
260 if gamma <= 0:
261 raise ValueError('gamma must be > 0.')
262
263 if abs(alpha + beta + gamma - 1.0) >= 1e-9:
264 raise ValueError('alpha+beta+gamma must equal 1.')
265
266 number_of_edges = G.number_of_edges()
267 while len(G) < n:
268 psum_in = number_of_edges + delta_in * len(G)
269 psum_out = number_of_edges + delta_out * len(G)
270 r = seed.random()
271 # random choice in alpha,beta,gamma ranges
272 if r < alpha:
273 # alpha
274 # add new node v
275 v = len(G)
276 # choose w according to in-degree and delta_in
277 w = _choose_node(G, G.in_degree(), delta_in, psum_in)
278 elif r < alpha + beta:
279 # beta
280 # choose v according to out-degree and delta_out
281 v = _choose_node(G, G.out_degree(), delta_out, psum_out)
282 # choose w according to in-degree and delta_in
283 w = _choose_node(G, G.in_degree(), delta_in, psum_in)
284 else:
285 # gamma
286 # choose v according to out-degree and delta_out
287 v = _choose_node(G, G.out_degree(), delta_out, psum_out)
288 # add new node w
289 w = len(G)
290 G.add_edge(v, w)
291 number_of_edges += 1
292 return G
293
294
295 @py_random_state(4)
296 def random_uniform_k_out_graph(n, k, self_loops=True, with_replacement=True,
297 seed=None):
298 """Returns a random `k`-out graph with uniform attachment.
299
300 A random `k`-out graph with uniform attachment is a multidigraph
301 generated by the following algorithm. For each node *u*, choose
302 `k` nodes *v* uniformly at random (with replacement). Add a
303 directed edge joining *u* to *v*.
304
305 Parameters
306 ----------
307 n : int
308 The number of nodes in the returned graph.
309
310 k : int
311 The out-degree of each node in the returned graph.
312
313 self_loops : bool
314 If True, self-loops are allowed when generating the graph.
315
316 with_replacement : bool
317 If True, neighbors are chosen with replacement and the
318 returned graph will be a directed multigraph. Otherwise,
319 neighbors are chosen without replacement and the returned graph
320 will be a directed graph.
321
322 seed : integer, random_state, or None (default)
323 Indicator of random number generation state.
324 See :ref:`Randomness<randomness>`.
325
326 Returns
327 -------
328 NetworkX graph
329 A `k`-out-regular directed graph generated according to the
330 above algorithm. It will be a multigraph if and only if
331 `with_replacement` is True.
332
333 Raises
334 ------
335 ValueError
336 If `with_replacement` is False and `k` is greater than
337 `n`.
338
339 See also
340 --------
341 random_k_out_graph
342
343 Notes
344 -----
345 The return digraph or multidigraph may not be strongly connected, or
346 even weakly connected.
347
348 If `with_replacement` is True, this function is similar to
349 :func:`random_k_out_graph`, if that function had parameter `alpha`
350 set to positive infinity.
351
352 """
353 if with_replacement:
354 create_using = nx.MultiDiGraph()
355
356 def sample(v, nodes):
357 if not self_loops:
358 nodes = nodes - {v}
359 return (seed.choice(list(nodes)) for i in range(k))
360
361 else:
362 create_using = nx.DiGraph()
363
364 def sample(v, nodes):
365 if not self_loops:
366 nodes = nodes - {v}
367 return seed.sample(nodes, k)
368
369 G = nx.empty_graph(n, create_using)
370 nodes = set(G)
371 for u in G:
372 G.add_edges_from((u, v) for v in sample(u, nodes))
373 return G
374
375
376 @py_random_state(4)
377 def random_k_out_graph(n, k, alpha, self_loops=True, seed=None):
378 """Returns a random `k`-out graph with preferential attachment.
379
380 A random `k`-out graph with preferential attachment is a
381 multidigraph generated by the following algorithm.
382
383 1. Begin with an empty digraph, and initially set each node to have
384 weight `alpha`.
385 2. Choose a node `u` with out-degree less than `k` uniformly at
386 random.
387 3. Choose a node `v` from with probability proportional to its
388 weight.
389 4. Add a directed edge from `u` to `v`, and increase the weight
390 of `v` by one.
391 5. If each node has out-degree `k`, halt, otherwise repeat from
392 step 2.
393
394 For more information on this model of random graph, see [1].
395
396 Parameters
397 ----------
398 n : int
399 The number of nodes in the returned graph.
400
401 k : int
402 The out-degree of each node in the returned graph.
403
404 alpha : float
405 A positive :class:`float` representing the initial weight of
406 each vertex. A higher number means that in step 3 above, nodes
407 will be chosen more like a true uniformly random sample, and a
408 lower number means that nodes are more likely to be chosen as
409 their in-degree increases. If this parameter is not positive, a
410 :exc:`ValueError` is raised.
411
412 self_loops : bool
413 If True, self-loops are allowed when generating the graph.
414
415 seed : integer, random_state, or None (default)
416 Indicator of random number generation state.
417 See :ref:`Randomness<randomness>`.
418
419 Returns
420 -------
421 :class:`~networkx.classes.MultiDiGraph`
422 A `k`-out-regular multidigraph generated according to the above
423 algorithm.
424
425 Raises
426 ------
427 ValueError
428 If `alpha` is not positive.
429
430 Notes
431 -----
432 The returned multidigraph may not be strongly connected, or even
433 weakly connected.
434
435 References
436 ----------
437 [1]: Peterson, Nicholas R., and Boris Pittel.
438 "Distance between two random `k`-out digraphs, with and without
439 preferential attachment."
440 arXiv preprint arXiv:1311.5961 (2013).
441 <https://arxiv.org/abs/1311.5961>
442
443 """
444 if alpha < 0:
445 raise ValueError('alpha must be positive')
446 G = nx.empty_graph(n, create_using=nx.MultiDiGraph)
447 weights = Counter({v: alpha for v in G})
448 for i in range(k * n):
449 u = seed.choice([v for v, d in G.out_degree() if d < k])
450 # If self-loops are not allowed, make the source node `u` have
451 # weight zero.
452 if not self_loops:
453 adjustment = Counter({u: weights[u]})
454 else:
455 adjustment = Counter()
456 v = weighted_choice(weights - adjustment, seed=seed)
457 G.add_edge(u, v)
458 weights[v] += 1
459 return G