Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/generators/degree_seq.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 """Generate graphs with a given degree sequence or expected degree sequence. | |
2 """ | |
3 | |
4 import heapq | |
5 from itertools import chain | |
6 from itertools import combinations | |
7 from itertools import zip_longest | |
8 import math | |
9 from operator import itemgetter | |
10 | |
11 import networkx as nx | |
12 from networkx.utils import random_weighted_sample, py_random_state | |
13 | |
14 __all__ = [ | |
15 "configuration_model", | |
16 "directed_configuration_model", | |
17 "expected_degree_graph", | |
18 "havel_hakimi_graph", | |
19 "directed_havel_hakimi_graph", | |
20 "degree_sequence_tree", | |
21 "random_degree_sequence_graph", | |
22 ] | |
23 | |
24 chaini = chain.from_iterable | |
25 | |
26 | |
27 def _to_stublist(degree_sequence): | |
28 """Returns a list of degree-repeated node numbers. | |
29 | |
30 ``degree_sequence`` is a list of nonnegative integers representing | |
31 the degrees of nodes in a graph. | |
32 | |
33 This function returns a list of node numbers with multiplicities | |
34 according to the given degree sequence. For example, if the first | |
35 element of ``degree_sequence`` is ``3``, then the first node number, | |
36 ``0``, will appear at the head of the returned list three times. The | |
37 node numbers are assumed to be the numbers zero through | |
38 ``len(degree_sequence) - 1``. | |
39 | |
40 Examples | |
41 -------- | |
42 | |
43 >>> degree_sequence = [1, 2, 3] | |
44 >>> _to_stublist(degree_sequence) | |
45 [0, 1, 1, 2, 2, 2] | |
46 | |
47 If a zero appears in the sequence, that means the node exists but | |
48 has degree zero, so that number will be skipped in the returned | |
49 list:: | |
50 | |
51 >>> degree_sequence = [2, 0, 1] | |
52 >>> _to_stublist(degree_sequence) | |
53 [0, 0, 2] | |
54 | |
55 """ | |
56 return list(chaini([n] * d for n, d in enumerate(degree_sequence))) | |
57 | |
58 | |
59 def _configuration_model( | |
60 deg_sequence, create_using, directed=False, in_deg_sequence=None, seed=None | |
61 ): | |
62 """Helper function for generating either undirected or directed | |
63 configuration model graphs. | |
64 | |
65 ``deg_sequence`` is a list of nonnegative integers representing the | |
66 degree of the node whose label is the index of the list element. | |
67 | |
68 ``create_using`` see :func:`~networkx.empty_graph`. | |
69 | |
70 ``directed`` and ``in_deg_sequence`` are required if you want the | |
71 returned graph to be generated using the directed configuration | |
72 model algorithm. If ``directed`` is ``False``, then ``deg_sequence`` | |
73 is interpreted as the degree sequence of an undirected graph and | |
74 ``in_deg_sequence`` is ignored. Otherwise, if ``directed`` is | |
75 ``True``, then ``deg_sequence`` is interpreted as the out-degree | |
76 sequence and ``in_deg_sequence`` as the in-degree sequence of a | |
77 directed graph. | |
78 | |
79 .. note:: | |
80 | |
81 ``deg_sequence`` and ``in_deg_sequence`` need not be the same | |
82 length. | |
83 | |
84 ``seed`` is a random.Random or numpy.random.RandomState instance | |
85 | |
86 This function returns a graph, directed if and only if ``directed`` | |
87 is ``True``, generated according to the configuration model | |
88 algorithm. For more information on the algorithm, see the | |
89 :func:`configuration_model` or :func:`directed_configuration_model` | |
90 functions. | |
91 | |
92 """ | |
93 n = len(deg_sequence) | |
94 G = nx.empty_graph(n, create_using) | |
95 # If empty, return the null graph immediately. | |
96 if n == 0: | |
97 return G | |
98 # Build a list of available degree-repeated nodes. For example, | |
99 # for degree sequence [3, 2, 1, 1, 1], the "stub list" is | |
100 # initially [0, 0, 0, 1, 1, 2, 3, 4], that is, node 0 has degree | |
101 # 3 and thus is repeated 3 times, etc. | |
102 # | |
103 # Also, shuffle the stub list in order to get a random sequence of | |
104 # node pairs. | |
105 if directed: | |
106 pairs = zip_longest(deg_sequence, in_deg_sequence, fillvalue=0) | |
107 # Unzip the list of pairs into a pair of lists. | |
108 out_deg, in_deg = zip(*pairs) | |
109 | |
110 out_stublist = _to_stublist(out_deg) | |
111 in_stublist = _to_stublist(in_deg) | |
112 | |
113 seed.shuffle(out_stublist) | |
114 seed.shuffle(in_stublist) | |
115 else: | |
116 stublist = _to_stublist(deg_sequence) | |
117 # Choose a random balanced bipartition of the stublist, which | |
118 # gives a random pairing of nodes. In this implementation, we | |
119 # shuffle the list and then split it in half. | |
120 n = len(stublist) | |
121 half = n // 2 | |
122 seed.shuffle(stublist) | |
123 out_stublist, in_stublist = stublist[:half], stublist[half:] | |
124 G.add_edges_from(zip(out_stublist, in_stublist)) | |
125 return G | |
126 | |
127 | |
128 @py_random_state(2) | |
129 def configuration_model(deg_sequence, create_using=None, seed=None): | |
130 """Returns a random graph with the given degree sequence. | |
131 | |
132 The configuration model generates a random pseudograph (graph with | |
133 parallel edges and self loops) by randomly assigning edges to | |
134 match the given degree sequence. | |
135 | |
136 Parameters | |
137 ---------- | |
138 deg_sequence : list of nonnegative integers | |
139 Each list entry corresponds to the degree of a node. | |
140 create_using : NetworkX graph constructor, optional (default MultiGraph) | |
141 Graph type to create. If graph instance, then cleared before populated. | |
142 seed : integer, random_state, or None (default) | |
143 Indicator of random number generation state. | |
144 See :ref:`Randomness<randomness>`. | |
145 | |
146 Returns | |
147 ------- | |
148 G : MultiGraph | |
149 A graph with the specified degree sequence. | |
150 Nodes are labeled starting at 0 with an index | |
151 corresponding to the position in deg_sequence. | |
152 | |
153 Raises | |
154 ------ | |
155 NetworkXError | |
156 If the degree sequence does not have an even sum. | |
157 | |
158 See Also | |
159 -------- | |
160 is_graphical | |
161 | |
162 Notes | |
163 ----- | |
164 As described by Newman [1]_. | |
165 | |
166 A non-graphical degree sequence (not realizable by some simple | |
167 graph) is allowed since this function returns graphs with self | |
168 loops and parallel edges. An exception is raised if the degree | |
169 sequence does not have an even sum. | |
170 | |
171 This configuration model construction process can lead to | |
172 duplicate edges and loops. You can remove the self-loops and | |
173 parallel edges (see below) which will likely result in a graph | |
174 that doesn't have the exact degree sequence specified. | |
175 | |
176 The density of self-loops and parallel edges tends to decrease as | |
177 the number of nodes increases. However, typically the number of | |
178 self-loops will approach a Poisson distribution with a nonzero mean, | |
179 and similarly for the number of parallel edges. Consider a node | |
180 with *k* stubs. The probability of being joined to another stub of | |
181 the same node is basically (*k* - *1*) / *N*, where *k* is the | |
182 degree and *N* is the number of nodes. So the probability of a | |
183 self-loop scales like *c* / *N* for some constant *c*. As *N* grows, | |
184 this means we expect *c* self-loops. Similarly for parallel edges. | |
185 | |
186 References | |
187 ---------- | |
188 .. [1] M.E.J. Newman, "The structure and function of complex networks", | |
189 SIAM REVIEW 45-2, pp 167-256, 2003. | |
190 | |
191 Examples | |
192 -------- | |
193 You can create a degree sequence following a particular distribution | |
194 by using the one of the distribution functions in | |
195 :mod:`~networkx.utils.random_sequence` (or one of your own). For | |
196 example, to create an undirected multigraph on one hundred nodes | |
197 with degree sequence chosen from the power law distribution: | |
198 | |
199 >>> sequence = nx.random_powerlaw_tree_sequence(100, tries=5000) | |
200 >>> G = nx.configuration_model(sequence) | |
201 >>> len(G) | |
202 100 | |
203 >>> actual_degrees = [d for v, d in G.degree()] | |
204 >>> actual_degrees == sequence | |
205 True | |
206 | |
207 The returned graph is a multigraph, which may have parallel | |
208 edges. To remove any parallel edges from the returned graph: | |
209 | |
210 >>> G = nx.Graph(G) | |
211 | |
212 Similarly, to remove self-loops: | |
213 | |
214 >>> G.remove_edges_from(nx.selfloop_edges(G)) | |
215 | |
216 """ | |
217 if sum(deg_sequence) % 2 != 0: | |
218 msg = "Invalid degree sequence: sum of degrees must be even, not odd" | |
219 raise nx.NetworkXError(msg) | |
220 | |
221 G = nx.empty_graph(0, create_using, default=nx.MultiGraph) | |
222 if G.is_directed(): | |
223 raise nx.NetworkXNotImplemented("not implemented for directed graphs") | |
224 | |
225 G = _configuration_model(deg_sequence, G, seed=seed) | |
226 | |
227 return G | |
228 | |
229 | |
230 @py_random_state(3) | |
231 def directed_configuration_model( | |
232 in_degree_sequence, out_degree_sequence, create_using=None, seed=None | |
233 ): | |
234 """Returns a directed_random graph with the given degree sequences. | |
235 | |
236 The configuration model generates a random directed pseudograph | |
237 (graph with parallel edges and self loops) by randomly assigning | |
238 edges to match the given degree sequences. | |
239 | |
240 Parameters | |
241 ---------- | |
242 in_degree_sequence : list of nonnegative integers | |
243 Each list entry corresponds to the in-degree of a node. | |
244 out_degree_sequence : list of nonnegative integers | |
245 Each list entry corresponds to the out-degree of a node. | |
246 create_using : NetworkX graph constructor, optional (default MultiDiGraph) | |
247 Graph type to create. If graph instance, then cleared before populated. | |
248 seed : integer, random_state, or None (default) | |
249 Indicator of random number generation state. | |
250 See :ref:`Randomness<randomness>`. | |
251 | |
252 Returns | |
253 ------- | |
254 G : MultiDiGraph | |
255 A graph with the specified degree sequences. | |
256 Nodes are labeled starting at 0 with an index | |
257 corresponding to the position in deg_sequence. | |
258 | |
259 Raises | |
260 ------ | |
261 NetworkXError | |
262 If the degree sequences do not have the same sum. | |
263 | |
264 See Also | |
265 -------- | |
266 configuration_model | |
267 | |
268 Notes | |
269 ----- | |
270 Algorithm as described by Newman [1]_. | |
271 | |
272 A non-graphical degree sequence (not realizable by some simple | |
273 graph) is allowed since this function returns graphs with self | |
274 loops and parallel edges. An exception is raised if the degree | |
275 sequences does not have the same sum. | |
276 | |
277 This configuration model construction process can lead to | |
278 duplicate edges and loops. You can remove the self-loops and | |
279 parallel edges (see below) which will likely result in a graph | |
280 that doesn't have the exact degree sequence specified. This | |
281 "finite-size effect" decreases as the size of the graph increases. | |
282 | |
283 References | |
284 ---------- | |
285 .. [1] Newman, M. E. J. and Strogatz, S. H. and Watts, D. J. | |
286 Random graphs with arbitrary degree distributions and their applications | |
287 Phys. Rev. E, 64, 026118 (2001) | |
288 | |
289 Examples | |
290 -------- | |
291 One can modify the in- and out-degree sequences from an existing | |
292 directed graph in order to create a new directed graph. For example, | |
293 here we modify the directed path graph: | |
294 | |
295 >>> D = nx.DiGraph([(0, 1), (1, 2), (2, 3)]) | |
296 >>> din = list(d for n, d in D.in_degree()) | |
297 >>> dout = list(d for n, d in D.out_degree()) | |
298 >>> din.append(1) | |
299 >>> dout[0] = 2 | |
300 >>> # We now expect an edge from node 0 to a new node, node 3. | |
301 ... D = nx.directed_configuration_model(din, dout) | |
302 | |
303 The returned graph is a directed multigraph, which may have parallel | |
304 edges. To remove any parallel edges from the returned graph: | |
305 | |
306 >>> D = nx.DiGraph(D) | |
307 | |
308 Similarly, to remove self-loops: | |
309 | |
310 >>> D.remove_edges_from(nx.selfloop_edges(D)) | |
311 | |
312 """ | |
313 if sum(in_degree_sequence) != sum(out_degree_sequence): | |
314 msg = "Invalid degree sequences: sequences must have equal sums" | |
315 raise nx.NetworkXError(msg) | |
316 | |
317 if create_using is None: | |
318 create_using = nx.MultiDiGraph | |
319 | |
320 G = _configuration_model( | |
321 out_degree_sequence, | |
322 create_using, | |
323 directed=True, | |
324 in_deg_sequence=in_degree_sequence, | |
325 seed=seed, | |
326 ) | |
327 | |
328 name = "directed configuration_model {} nodes {} edges" | |
329 return G | |
330 | |
331 | |
332 @py_random_state(1) | |
333 def expected_degree_graph(w, seed=None, selfloops=True): | |
334 r"""Returns a random graph with given expected degrees. | |
335 | |
336 Given a sequence of expected degrees $W=(w_0,w_1,\ldots,w_{n-1})$ | |
337 of length $n$ this algorithm assigns an edge between node $u$ and | |
338 node $v$ with probability | |
339 | |
340 .. math:: | |
341 | |
342 p_{uv} = \frac{w_u w_v}{\sum_k w_k} . | |
343 | |
344 Parameters | |
345 ---------- | |
346 w : list | |
347 The list of expected degrees. | |
348 selfloops: bool (default=True) | |
349 Set to False to remove the possibility of self-loop edges. | |
350 seed : integer, random_state, or None (default) | |
351 Indicator of random number generation state. | |
352 See :ref:`Randomness<randomness>`. | |
353 | |
354 Returns | |
355 ------- | |
356 Graph | |
357 | |
358 Examples | |
359 -------- | |
360 >>> z = [10 for i in range(100)] | |
361 >>> G = nx.expected_degree_graph(z) | |
362 | |
363 Notes | |
364 ----- | |
365 The nodes have integer labels corresponding to index of expected degrees | |
366 input sequence. | |
367 | |
368 The complexity of this algorithm is $\mathcal{O}(n+m)$ where $n$ is the | |
369 number of nodes and $m$ is the expected number of edges. | |
370 | |
371 The model in [1]_ includes the possibility of self-loop edges. | |
372 Set selfloops=False to produce a graph without self loops. | |
373 | |
374 For finite graphs this model doesn't produce exactly the given | |
375 expected degree sequence. Instead the expected degrees are as | |
376 follows. | |
377 | |
378 For the case without self loops (selfloops=False), | |
379 | |
380 .. math:: | |
381 | |
382 E[deg(u)] = \sum_{v \ne u} p_{uv} | |
383 = w_u \left( 1 - \frac{w_u}{\sum_k w_k} \right) . | |
384 | |
385 | |
386 NetworkX uses the standard convention that a self-loop edge counts 2 | |
387 in the degree of a node, so with self loops (selfloops=True), | |
388 | |
389 .. math:: | |
390 | |
391 E[deg(u)] = \sum_{v \ne u} p_{uv} + 2 p_{uu} | |
392 = w_u \left( 1 + \frac{w_u}{\sum_k w_k} \right) . | |
393 | |
394 References | |
395 ---------- | |
396 .. [1] Fan Chung and L. Lu, Connected components in random graphs with | |
397 given expected degree sequences, Ann. Combinatorics, 6, | |
398 pp. 125-145, 2002. | |
399 .. [2] Joel Miller and Aric Hagberg, | |
400 Efficient generation of networks with given expected degrees, | |
401 in Algorithms and Models for the Web-Graph (WAW 2011), | |
402 Alan Frieze, Paul Horn, and Paweł Prałat (Eds), LNCS 6732, | |
403 pp. 115-126, 2011. | |
404 """ | |
405 n = len(w) | |
406 G = nx.empty_graph(n) | |
407 | |
408 # If there are no nodes are no edges in the graph, return the empty graph. | |
409 if n == 0 or max(w) == 0: | |
410 return G | |
411 | |
412 rho = 1 / sum(w) | |
413 # Sort the weights in decreasing order. The original order of the | |
414 # weights dictates the order of the (integer) node labels, so we | |
415 # need to remember the permutation applied in the sorting. | |
416 order = sorted(enumerate(w), key=itemgetter(1), reverse=True) | |
417 mapping = {c: u for c, (u, v) in enumerate(order)} | |
418 seq = [v for u, v in order] | |
419 last = n | |
420 if not selfloops: | |
421 last -= 1 | |
422 for u in range(last): | |
423 v = u | |
424 if not selfloops: | |
425 v += 1 | |
426 factor = seq[u] * rho | |
427 p = min(seq[v] * factor, 1) | |
428 while v < n and p > 0: | |
429 if p != 1: | |
430 r = seed.random() | |
431 v += int(math.floor(math.log(r, 1 - p))) | |
432 if v < n: | |
433 q = min(seq[v] * factor, 1) | |
434 if seed.random() < q / p: | |
435 G.add_edge(mapping[u], mapping[v]) | |
436 v += 1 | |
437 p = q | |
438 return G | |
439 | |
440 | |
441 def havel_hakimi_graph(deg_sequence, create_using=None): | |
442 """Returns a simple graph with given degree sequence constructed | |
443 using the Havel-Hakimi algorithm. | |
444 | |
445 Parameters | |
446 ---------- | |
447 deg_sequence: list of integers | |
448 Each integer corresponds to the degree of a node (need not be sorted). | |
449 create_using : NetworkX graph constructor, optional (default=nx.Graph) | |
450 Graph type to create. If graph instance, then cleared before populated. | |
451 Directed graphs are not allowed. | |
452 | |
453 Raises | |
454 ------ | |
455 NetworkXException | |
456 For a non-graphical degree sequence (i.e. one | |
457 not realizable by some simple graph). | |
458 | |
459 Notes | |
460 ----- | |
461 The Havel-Hakimi algorithm constructs a simple graph by | |
462 successively connecting the node of highest degree to other nodes | |
463 of highest degree, resorting remaining nodes by degree, and | |
464 repeating the process. The resulting graph has a high | |
465 degree-associativity. Nodes are labeled 1,.., len(deg_sequence), | |
466 corresponding to their position in deg_sequence. | |
467 | |
468 The basic algorithm is from Hakimi [1]_ and was generalized by | |
469 Kleitman and Wang [2]_. | |
470 | |
471 References | |
472 ---------- | |
473 .. [1] Hakimi S., On Realizability of a Set of Integers as | |
474 Degrees of the Vertices of a Linear Graph. I, | |
475 Journal of SIAM, 10(3), pp. 496-506 (1962) | |
476 .. [2] Kleitman D.J. and Wang D.L. | |
477 Algorithms for Constructing Graphs and Digraphs with Given Valences | |
478 and Factors Discrete Mathematics, 6(1), pp. 79-88 (1973) | |
479 """ | |
480 if not nx.is_graphical(deg_sequence): | |
481 raise nx.NetworkXError("Invalid degree sequence") | |
482 | |
483 p = len(deg_sequence) | |
484 G = nx.empty_graph(p, create_using) | |
485 if G.is_directed(): | |
486 raise nx.NetworkXError("Directed graphs are not supported") | |
487 num_degs = [[] for i in range(p)] | |
488 dmax, dsum, n = 0, 0, 0 | |
489 for d in deg_sequence: | |
490 # Process only the non-zero integers | |
491 if d > 0: | |
492 num_degs[d].append(n) | |
493 dmax, dsum, n = max(dmax, d), dsum + d, n + 1 | |
494 # Return graph if no edges | |
495 if n == 0: | |
496 return G | |
497 | |
498 modstubs = [(0, 0)] * (dmax + 1) | |
499 # Successively reduce degree sequence by removing the maximum degree | |
500 while n > 0: | |
501 # Retrieve the maximum degree in the sequence | |
502 while len(num_degs[dmax]) == 0: | |
503 dmax -= 1 | |
504 # If there are not enough stubs to connect to, then the sequence is | |
505 # not graphical | |
506 if dmax > n - 1: | |
507 raise nx.NetworkXError("Non-graphical integer sequence") | |
508 | |
509 # Remove largest stub in list | |
510 source = num_degs[dmax].pop() | |
511 n -= 1 | |
512 # Reduce the next dmax largest stubs | |
513 mslen = 0 | |
514 k = dmax | |
515 for i in range(dmax): | |
516 while len(num_degs[k]) == 0: | |
517 k -= 1 | |
518 target = num_degs[k].pop() | |
519 G.add_edge(source, target) | |
520 n -= 1 | |
521 if k > 1: | |
522 modstubs[mslen] = (k - 1, target) | |
523 mslen += 1 | |
524 # Add back to the list any nonzero stubs that were removed | |
525 for i in range(mslen): | |
526 (stubval, stubtarget) = modstubs[i] | |
527 num_degs[stubval].append(stubtarget) | |
528 n += 1 | |
529 | |
530 return G | |
531 | |
532 | |
533 def directed_havel_hakimi_graph(in_deg_sequence, out_deg_sequence, create_using=None): | |
534 """Returns a directed graph with the given degree sequences. | |
535 | |
536 Parameters | |
537 ---------- | |
538 in_deg_sequence : list of integers | |
539 Each list entry corresponds to the in-degree of a node. | |
540 out_deg_sequence : list of integers | |
541 Each list entry corresponds to the out-degree of a node. | |
542 create_using : NetworkX graph constructor, optional (default DiGraph) | |
543 Graph type to create. If graph instance, then cleared before populated. | |
544 | |
545 Returns | |
546 ------- | |
547 G : DiGraph | |
548 A graph with the specified degree sequences. | |
549 Nodes are labeled starting at 0 with an index | |
550 corresponding to the position in deg_sequence | |
551 | |
552 Raises | |
553 ------ | |
554 NetworkXError | |
555 If the degree sequences are not digraphical. | |
556 | |
557 See Also | |
558 -------- | |
559 configuration_model | |
560 | |
561 Notes | |
562 ----- | |
563 Algorithm as described by Kleitman and Wang [1]_. | |
564 | |
565 References | |
566 ---------- | |
567 .. [1] D.J. Kleitman and D.L. Wang | |
568 Algorithms for Constructing Graphs and Digraphs with Given Valences | |
569 and Factors Discrete Mathematics, 6(1), pp. 79-88 (1973) | |
570 """ | |
571 in_deg_sequence = nx.utils.make_list_of_ints(in_deg_sequence) | |
572 out_deg_sequence = nx.utils.make_list_of_ints(out_deg_sequence) | |
573 | |
574 # Process the sequences and form two heaps to store degree pairs with | |
575 # either zero or nonzero out degrees | |
576 sumin, sumout = 0, 0 | |
577 nin, nout = len(in_deg_sequence), len(out_deg_sequence) | |
578 maxn = max(nin, nout) | |
579 G = nx.empty_graph(maxn, create_using, default=nx.DiGraph) | |
580 if maxn == 0: | |
581 return G | |
582 maxin = 0 | |
583 stubheap, zeroheap = [], [] | |
584 for n in range(maxn): | |
585 in_deg, out_deg = 0, 0 | |
586 if n < nout: | |
587 out_deg = out_deg_sequence[n] | |
588 if n < nin: | |
589 in_deg = in_deg_sequence[n] | |
590 if in_deg < 0 or out_deg < 0: | |
591 raise nx.NetworkXError( | |
592 "Invalid degree sequences. Sequence values must be positive." | |
593 ) | |
594 sumin, sumout, maxin = sumin + in_deg, sumout + out_deg, max(maxin, in_deg) | |
595 if in_deg > 0: | |
596 stubheap.append((-1 * out_deg, -1 * in_deg, n)) | |
597 elif out_deg > 0: | |
598 zeroheap.append((-1 * out_deg, n)) | |
599 if sumin != sumout: | |
600 raise nx.NetworkXError( | |
601 "Invalid degree sequences. Sequences must have equal sums." | |
602 ) | |
603 heapq.heapify(stubheap) | |
604 heapq.heapify(zeroheap) | |
605 | |
606 modstubs = [(0, 0, 0)] * (maxin + 1) | |
607 # Successively reduce degree sequence by removing the maximum | |
608 while stubheap: | |
609 # Remove first value in the sequence with a non-zero in degree | |
610 (freeout, freein, target) = heapq.heappop(stubheap) | |
611 freein *= -1 | |
612 if freein > len(stubheap) + len(zeroheap): | |
613 raise nx.NetworkXError("Non-digraphical integer sequence") | |
614 | |
615 # Attach arcs from the nodes with the most stubs | |
616 mslen = 0 | |
617 for i in range(freein): | |
618 if zeroheap and (not stubheap or stubheap[0][0] > zeroheap[0][0]): | |
619 (stubout, stubsource) = heapq.heappop(zeroheap) | |
620 stubin = 0 | |
621 else: | |
622 (stubout, stubin, stubsource) = heapq.heappop(stubheap) | |
623 if stubout == 0: | |
624 raise nx.NetworkXError("Non-digraphical integer sequence") | |
625 G.add_edge(stubsource, target) | |
626 # Check if source is now totally connected | |
627 if stubout + 1 < 0 or stubin < 0: | |
628 modstubs[mslen] = (stubout + 1, stubin, stubsource) | |
629 mslen += 1 | |
630 | |
631 # Add the nodes back to the heaps that still have available stubs | |
632 for i in range(mslen): | |
633 stub = modstubs[i] | |
634 if stub[1] < 0: | |
635 heapq.heappush(stubheap, stub) | |
636 else: | |
637 heapq.heappush(zeroheap, (stub[0], stub[2])) | |
638 if freeout < 0: | |
639 heapq.heappush(zeroheap, (freeout, target)) | |
640 | |
641 return G | |
642 | |
643 | |
644 def degree_sequence_tree(deg_sequence, create_using=None): | |
645 """Make a tree for the given degree sequence. | |
646 | |
647 A tree has #nodes-#edges=1 so | |
648 the degree sequence must have | |
649 len(deg_sequence)-sum(deg_sequence)/2=1 | |
650 """ | |
651 # The sum of the degree sequence must be even (for any undirected graph). | |
652 degree_sum = sum(deg_sequence) | |
653 if degree_sum % 2 != 0: | |
654 msg = "Invalid degree sequence: sum of degrees must be even, not odd" | |
655 raise nx.NetworkXError(msg) | |
656 if len(deg_sequence) - degree_sum // 2 != 1: | |
657 msg = ( | |
658 "Invalid degree sequence: tree must have number of nodes equal" | |
659 " to one less than the number of edges" | |
660 ) | |
661 raise nx.NetworkXError(msg) | |
662 G = nx.empty_graph(0, create_using) | |
663 if G.is_directed(): | |
664 raise nx.NetworkXError("Directed Graph not supported") | |
665 | |
666 # Sort all degrees greater than 1 in decreasing order. | |
667 # | |
668 # TODO Does this need to be sorted in reverse order? | |
669 deg = sorted((s for s in deg_sequence if s > 1), reverse=True) | |
670 | |
671 # make path graph as backbone | |
672 n = len(deg) + 2 | |
673 nx.add_path(G, range(n)) | |
674 last = n | |
675 | |
676 # add the leaves | |
677 for source in range(1, n - 1): | |
678 nedges = deg.pop() - 2 | |
679 for target in range(last, last + nedges): | |
680 G.add_edge(source, target) | |
681 last += nedges | |
682 | |
683 # in case we added one too many | |
684 if len(G) > len(deg_sequence): | |
685 G.remove_node(0) | |
686 return G | |
687 | |
688 | |
689 @py_random_state(1) | |
690 def random_degree_sequence_graph(sequence, seed=None, tries=10): | |
691 r"""Returns a simple random graph with the given degree sequence. | |
692 | |
693 If the maximum degree $d_m$ in the sequence is $O(m^{1/4})$ then the | |
694 algorithm produces almost uniform random graphs in $O(m d_m)$ time | |
695 where $m$ is the number of edges. | |
696 | |
697 Parameters | |
698 ---------- | |
699 sequence : list of integers | |
700 Sequence of degrees | |
701 seed : integer, random_state, or None (default) | |
702 Indicator of random number generation state. | |
703 See :ref:`Randomness<randomness>`. | |
704 tries : int, optional | |
705 Maximum number of tries to create a graph | |
706 | |
707 Returns | |
708 ------- | |
709 G : Graph | |
710 A graph with the specified degree sequence. | |
711 Nodes are labeled starting at 0 with an index | |
712 corresponding to the position in the sequence. | |
713 | |
714 Raises | |
715 ------ | |
716 NetworkXUnfeasible | |
717 If the degree sequence is not graphical. | |
718 NetworkXError | |
719 If a graph is not produced in specified number of tries | |
720 | |
721 See Also | |
722 -------- | |
723 is_graphical, configuration_model | |
724 | |
725 Notes | |
726 ----- | |
727 The generator algorithm [1]_ is not guaranteed to produce a graph. | |
728 | |
729 References | |
730 ---------- | |
731 .. [1] Moshen Bayati, Jeong Han Kim, and Amin Saberi, | |
732 A sequential algorithm for generating random graphs. | |
733 Algorithmica, Volume 58, Number 4, 860-910, | |
734 DOI: 10.1007/s00453-009-9340-1 | |
735 | |
736 Examples | |
737 -------- | |
738 >>> sequence = [1, 2, 2, 3] | |
739 >>> G = nx.random_degree_sequence_graph(sequence, seed=42) | |
740 >>> sorted(d for n, d in G.degree()) | |
741 [1, 2, 2, 3] | |
742 """ | |
743 DSRG = DegreeSequenceRandomGraph(sequence, seed) | |
744 for try_n in range(tries): | |
745 try: | |
746 return DSRG.generate() | |
747 except nx.NetworkXUnfeasible: | |
748 pass | |
749 raise nx.NetworkXError(f"failed to generate graph in {tries} tries") | |
750 | |
751 | |
752 class DegreeSequenceRandomGraph: | |
753 # class to generate random graphs with a given degree sequence | |
754 # use random_degree_sequence_graph() | |
755 def __init__(self, degree, rng): | |
756 if not nx.is_graphical(degree): | |
757 raise nx.NetworkXUnfeasible("degree sequence is not graphical") | |
758 self.rng = rng | |
759 self.degree = list(degree) | |
760 # node labels are integers 0,...,n-1 | |
761 self.m = sum(self.degree) / 2.0 # number of edges | |
762 try: | |
763 self.dmax = max(self.degree) # maximum degree | |
764 except ValueError: | |
765 self.dmax = 0 | |
766 | |
767 def generate(self): | |
768 # remaining_degree is mapping from int->remaining degree | |
769 self.remaining_degree = dict(enumerate(self.degree)) | |
770 # add all nodes to make sure we get isolated nodes | |
771 self.graph = nx.Graph() | |
772 self.graph.add_nodes_from(self.remaining_degree) | |
773 # remove zero degree nodes | |
774 for n, d in list(self.remaining_degree.items()): | |
775 if d == 0: | |
776 del self.remaining_degree[n] | |
777 if len(self.remaining_degree) > 0: | |
778 # build graph in three phases according to how many unmatched edges | |
779 self.phase1() | |
780 self.phase2() | |
781 self.phase3() | |
782 return self.graph | |
783 | |
784 def update_remaining(self, u, v, aux_graph=None): | |
785 # decrement remaining nodes, modify auxiliary graph if in phase3 | |
786 if aux_graph is not None: | |
787 # remove edges from auxiliary graph | |
788 aux_graph.remove_edge(u, v) | |
789 if self.remaining_degree[u] == 1: | |
790 del self.remaining_degree[u] | |
791 if aux_graph is not None: | |
792 aux_graph.remove_node(u) | |
793 else: | |
794 self.remaining_degree[u] -= 1 | |
795 if self.remaining_degree[v] == 1: | |
796 del self.remaining_degree[v] | |
797 if aux_graph is not None: | |
798 aux_graph.remove_node(v) | |
799 else: | |
800 self.remaining_degree[v] -= 1 | |
801 | |
802 def p(self, u, v): | |
803 # degree probability | |
804 return 1 - self.degree[u] * self.degree[v] / (4.0 * self.m) | |
805 | |
806 def q(self, u, v): | |
807 # remaining degree probability | |
808 norm = float(max(self.remaining_degree.values())) ** 2 | |
809 return self.remaining_degree[u] * self.remaining_degree[v] / norm | |
810 | |
811 def suitable_edge(self): | |
812 """Returns True if and only if an arbitrary remaining node can | |
813 potentially be joined with some other remaining node. | |
814 | |
815 """ | |
816 nodes = iter(self.remaining_degree) | |
817 u = next(nodes) | |
818 return any(v not in self.graph[u] for v in nodes) | |
819 | |
820 def phase1(self): | |
821 # choose node pairs from (degree) weighted distribution | |
822 rem_deg = self.remaining_degree | |
823 while sum(rem_deg.values()) >= 2 * self.dmax ** 2: | |
824 u, v = sorted(random_weighted_sample(rem_deg, 2, self.rng)) | |
825 if self.graph.has_edge(u, v): | |
826 continue | |
827 if self.rng.random() < self.p(u, v): # accept edge | |
828 self.graph.add_edge(u, v) | |
829 self.update_remaining(u, v) | |
830 | |
831 def phase2(self): | |
832 # choose remaining nodes uniformly at random and use rejection sampling | |
833 remaining_deg = self.remaining_degree | |
834 rng = self.rng | |
835 while len(remaining_deg) >= 2 * self.dmax: | |
836 while True: | |
837 u, v = sorted(rng.sample(remaining_deg.keys(), 2)) | |
838 if self.graph.has_edge(u, v): | |
839 continue | |
840 if rng.random() < self.q(u, v): | |
841 break | |
842 if rng.random() < self.p(u, v): # accept edge | |
843 self.graph.add_edge(u, v) | |
844 self.update_remaining(u, v) | |
845 | |
846 def phase3(self): | |
847 # build potential remaining edges and choose with rejection sampling | |
848 potential_edges = combinations(self.remaining_degree, 2) | |
849 # build auxiliary graph of potential edges not already in graph | |
850 H = nx.Graph( | |
851 [(u, v) for (u, v) in potential_edges if not self.graph.has_edge(u, v)] | |
852 ) | |
853 rng = self.rng | |
854 while self.remaining_degree: | |
855 if not self.suitable_edge(): | |
856 raise nx.NetworkXUnfeasible("no suitable edges left") | |
857 while True: | |
858 u, v = sorted(rng.choice(list(H.edges()))) | |
859 if rng.random() < self.q(u, v): | |
860 break | |
861 if rng.random() < self.p(u, v): # accept edge | |
862 self.graph.add_edge(u, v) | |
863 self.update_remaining(u, v, aux_graph=H) |