Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/bipartite/generators.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 Generators and functions for bipartite graphs. | |
3 """ | |
4 import math | |
5 import numbers | |
6 from functools import reduce | |
7 import networkx as nx | |
8 from networkx.utils import nodes_or_number, py_random_state | |
9 | |
10 __all__ = [ | |
11 "configuration_model", | |
12 "havel_hakimi_graph", | |
13 "reverse_havel_hakimi_graph", | |
14 "alternating_havel_hakimi_graph", | |
15 "preferential_attachment_graph", | |
16 "random_graph", | |
17 "gnmk_random_graph", | |
18 "complete_bipartite_graph", | |
19 ] | |
20 | |
21 | |
22 @nodes_or_number([0, 1]) | |
23 def complete_bipartite_graph(n1, n2, create_using=None): | |
24 """Returns the complete bipartite graph `K_{n_1,n_2}`. | |
25 | |
26 The graph is composed of two partitions with nodes 0 to (n1 - 1) | |
27 in the first and nodes n1 to (n1 + n2 - 1) in the second. | |
28 Each node in the first is connected to each node in the second. | |
29 | |
30 Parameters | |
31 ---------- | |
32 n1 : integer | |
33 Number of nodes for node set A. | |
34 n2 : integer | |
35 Number of nodes for node set B. | |
36 create_using : NetworkX graph instance, optional | |
37 Return graph of this type. | |
38 | |
39 Notes | |
40 ----- | |
41 Node labels are the integers 0 to `n_1 + n_2 - 1`. | |
42 | |
43 The nodes are assigned the attribute 'bipartite' with the value 0 or 1 | |
44 to indicate which bipartite set the node belongs to. | |
45 | |
46 This function is not imported in the main namespace. | |
47 To use it use nx.bipartite.complete_bipartite_graph | |
48 """ | |
49 G = nx.empty_graph(0, create_using) | |
50 if G.is_directed(): | |
51 raise nx.NetworkXError("Directed Graph not supported") | |
52 | |
53 n1, top = n1 | |
54 n2, bottom = n2 | |
55 if isinstance(n2, numbers.Integral): | |
56 bottom = [n1 + i for i in bottom] | |
57 G.add_nodes_from(top, bipartite=0) | |
58 G.add_nodes_from(bottom, bipartite=1) | |
59 G.add_edges_from((u, v) for u in top for v in bottom) | |
60 G.graph["name"] = f"complete_bipartite_graph({n1},{n2})" | |
61 return G | |
62 | |
63 | |
64 @py_random_state(3) | |
65 def configuration_model(aseq, bseq, create_using=None, seed=None): | |
66 """Returns a random bipartite graph from two given degree sequences. | |
67 | |
68 Parameters | |
69 ---------- | |
70 aseq : list | |
71 Degree sequence for node set A. | |
72 bseq : list | |
73 Degree sequence for node set B. | |
74 create_using : NetworkX graph instance, optional | |
75 Return graph of this type. | |
76 seed : integer, random_state, or None (default) | |
77 Indicator of random number generation state. | |
78 See :ref:`Randomness<randomness>`. | |
79 | |
80 The graph is composed of two partitions. Set A has nodes 0 to | |
81 (len(aseq) - 1) and set B has nodes len(aseq) to (len(bseq) - 1). | |
82 Nodes from set A are connected to nodes in set B by choosing | |
83 randomly from the possible free stubs, one in A and one in B. | |
84 | |
85 Notes | |
86 ----- | |
87 The sum of the two sequences must be equal: sum(aseq)=sum(bseq) | |
88 If no graph type is specified use MultiGraph with parallel edges. | |
89 If you want a graph with no parallel edges use create_using=Graph() | |
90 but then the resulting degree sequences might not be exact. | |
91 | |
92 The nodes are assigned the attribute 'bipartite' with the value 0 or 1 | |
93 to indicate which bipartite set the node belongs to. | |
94 | |
95 This function is not imported in the main namespace. | |
96 To use it use nx.bipartite.configuration_model | |
97 """ | |
98 G = nx.empty_graph(0, create_using, default=nx.MultiGraph) | |
99 if G.is_directed(): | |
100 raise nx.NetworkXError("Directed Graph not supported") | |
101 | |
102 # length and sum of each sequence | |
103 lena = len(aseq) | |
104 lenb = len(bseq) | |
105 suma = sum(aseq) | |
106 sumb = sum(bseq) | |
107 | |
108 if not suma == sumb: | |
109 raise nx.NetworkXError( | |
110 f"invalid degree sequences, sum(aseq)!=sum(bseq),{suma},{sumb}" | |
111 ) | |
112 | |
113 G = _add_nodes_with_bipartite_label(G, lena, lenb) | |
114 | |
115 if len(aseq) == 0 or max(aseq) == 0: | |
116 return G # done if no edges | |
117 | |
118 # build lists of degree-repeated vertex numbers | |
119 stubs = [] | |
120 stubs.extend([[v] * aseq[v] for v in range(0, lena)]) | |
121 astubs = [] | |
122 astubs = [x for subseq in stubs for x in subseq] | |
123 | |
124 stubs = [] | |
125 stubs.extend([[v] * bseq[v - lena] for v in range(lena, lena + lenb)]) | |
126 bstubs = [] | |
127 bstubs = [x for subseq in stubs for x in subseq] | |
128 | |
129 # shuffle lists | |
130 seed.shuffle(astubs) | |
131 seed.shuffle(bstubs) | |
132 | |
133 G.add_edges_from([[astubs[i], bstubs[i]] for i in range(suma)]) | |
134 | |
135 G.name = "bipartite_configuration_model" | |
136 return G | |
137 | |
138 | |
139 def havel_hakimi_graph(aseq, bseq, create_using=None): | |
140 """Returns a bipartite graph from two given degree sequences using a | |
141 Havel-Hakimi style construction. | |
142 | |
143 The graph is composed of two partitions. Set A has nodes 0 to | |
144 (len(aseq) - 1) and set B has nodes len(aseq) to (len(bseq) - 1). | |
145 Nodes from the set A are connected to nodes in the set B by | |
146 connecting the highest degree nodes in set A to the highest degree | |
147 nodes in set B until all stubs are connected. | |
148 | |
149 Parameters | |
150 ---------- | |
151 aseq : list | |
152 Degree sequence for node set A. | |
153 bseq : list | |
154 Degree sequence for node set B. | |
155 create_using : NetworkX graph instance, optional | |
156 Return graph of this type. | |
157 | |
158 Notes | |
159 ----- | |
160 The sum of the two sequences must be equal: sum(aseq)=sum(bseq) | |
161 If no graph type is specified use MultiGraph with parallel edges. | |
162 If you want a graph with no parallel edges use create_using=Graph() | |
163 but then the resulting degree sequences might not be exact. | |
164 | |
165 The nodes are assigned the attribute 'bipartite' with the value 0 or 1 | |
166 to indicate which bipartite set the node belongs to. | |
167 | |
168 This function is not imported in the main namespace. | |
169 To use it use nx.bipartite.havel_hakimi_graph | |
170 """ | |
171 G = nx.empty_graph(0, create_using, default=nx.MultiGraph) | |
172 if G.is_directed(): | |
173 raise nx.NetworkXError("Directed Graph not supported") | |
174 | |
175 # length of the each sequence | |
176 naseq = len(aseq) | |
177 nbseq = len(bseq) | |
178 | |
179 suma = sum(aseq) | |
180 sumb = sum(bseq) | |
181 | |
182 if not suma == sumb: | |
183 raise nx.NetworkXError( | |
184 f"invalid degree sequences, sum(aseq)!=sum(bseq),{suma},{sumb}" | |
185 ) | |
186 | |
187 G = _add_nodes_with_bipartite_label(G, naseq, nbseq) | |
188 | |
189 if len(aseq) == 0 or max(aseq) == 0: | |
190 return G # done if no edges | |
191 | |
192 # build list of degree-repeated vertex numbers | |
193 astubs = [[aseq[v], v] for v in range(0, naseq)] | |
194 bstubs = [[bseq[v - naseq], v] for v in range(naseq, naseq + nbseq)] | |
195 astubs.sort() | |
196 while astubs: | |
197 (degree, u) = astubs.pop() # take of largest degree node in the a set | |
198 if degree == 0: | |
199 break # done, all are zero | |
200 # connect the source to largest degree nodes in the b set | |
201 bstubs.sort() | |
202 for target in bstubs[-degree:]: | |
203 v = target[1] | |
204 G.add_edge(u, v) | |
205 target[0] -= 1 # note this updates bstubs too. | |
206 if target[0] == 0: | |
207 bstubs.remove(target) | |
208 | |
209 G.name = "bipartite_havel_hakimi_graph" | |
210 return G | |
211 | |
212 | |
213 def reverse_havel_hakimi_graph(aseq, bseq, create_using=None): | |
214 """Returns a bipartite graph from two given degree sequences using a | |
215 Havel-Hakimi style construction. | |
216 | |
217 The graph is composed of two partitions. Set A has nodes 0 to | |
218 (len(aseq) - 1) and set B has nodes len(aseq) to (len(bseq) - 1). | |
219 Nodes from set A are connected to nodes in the set B by connecting | |
220 the highest degree nodes in set A to the lowest degree nodes in | |
221 set B until all stubs are connected. | |
222 | |
223 Parameters | |
224 ---------- | |
225 aseq : list | |
226 Degree sequence for node set A. | |
227 bseq : list | |
228 Degree sequence for node set B. | |
229 create_using : NetworkX graph instance, optional | |
230 Return graph of this type. | |
231 | |
232 Notes | |
233 ----- | |
234 The sum of the two sequences must be equal: sum(aseq)=sum(bseq) | |
235 If no graph type is specified use MultiGraph with parallel edges. | |
236 If you want a graph with no parallel edges use create_using=Graph() | |
237 but then the resulting degree sequences might not be exact. | |
238 | |
239 The nodes are assigned the attribute 'bipartite' with the value 0 or 1 | |
240 to indicate which bipartite set the node belongs to. | |
241 | |
242 This function is not imported in the main namespace. | |
243 To use it use nx.bipartite.reverse_havel_hakimi_graph | |
244 """ | |
245 G = nx.empty_graph(0, create_using, default=nx.MultiGraph) | |
246 if G.is_directed(): | |
247 raise nx.NetworkXError("Directed Graph not supported") | |
248 | |
249 # length of the each sequence | |
250 lena = len(aseq) | |
251 lenb = len(bseq) | |
252 suma = sum(aseq) | |
253 sumb = sum(bseq) | |
254 | |
255 if not suma == sumb: | |
256 raise nx.NetworkXError( | |
257 f"invalid degree sequences, sum(aseq)!=sum(bseq),{suma},{sumb}" | |
258 ) | |
259 | |
260 G = _add_nodes_with_bipartite_label(G, lena, lenb) | |
261 | |
262 if len(aseq) == 0 or max(aseq) == 0: | |
263 return G # done if no edges | |
264 | |
265 # build list of degree-repeated vertex numbers | |
266 astubs = [[aseq[v], v] for v in range(0, lena)] | |
267 bstubs = [[bseq[v - lena], v] for v in range(lena, lena + lenb)] | |
268 astubs.sort() | |
269 bstubs.sort() | |
270 while astubs: | |
271 (degree, u) = astubs.pop() # take of largest degree node in the a set | |
272 if degree == 0: | |
273 break # done, all are zero | |
274 # connect the source to the smallest degree nodes in the b set | |
275 for target in bstubs[0:degree]: | |
276 v = target[1] | |
277 G.add_edge(u, v) | |
278 target[0] -= 1 # note this updates bstubs too. | |
279 if target[0] == 0: | |
280 bstubs.remove(target) | |
281 | |
282 G.name = "bipartite_reverse_havel_hakimi_graph" | |
283 return G | |
284 | |
285 | |
286 def alternating_havel_hakimi_graph(aseq, bseq, create_using=None): | |
287 """Returns a bipartite graph from two given degree sequences using | |
288 an alternating Havel-Hakimi style construction. | |
289 | |
290 The graph is composed of two partitions. Set A has nodes 0 to | |
291 (len(aseq) - 1) and set B has nodes len(aseq) to (len(bseq) - 1). | |
292 Nodes from the set A are connected to nodes in the set B by | |
293 connecting the highest degree nodes in set A to alternatively the | |
294 highest and the lowest degree nodes in set B until all stubs are | |
295 connected. | |
296 | |
297 Parameters | |
298 ---------- | |
299 aseq : list | |
300 Degree sequence for node set A. | |
301 bseq : list | |
302 Degree sequence for node set B. | |
303 create_using : NetworkX graph instance, optional | |
304 Return graph of this type. | |
305 | |
306 Notes | |
307 ----- | |
308 The sum of the two sequences must be equal: sum(aseq)=sum(bseq) | |
309 If no graph type is specified use MultiGraph with parallel edges. | |
310 If you want a graph with no parallel edges use create_using=Graph() | |
311 but then the resulting degree sequences might not be exact. | |
312 | |
313 The nodes are assigned the attribute 'bipartite' with the value 0 or 1 | |
314 to indicate which bipartite set the node belongs to. | |
315 | |
316 This function is not imported in the main namespace. | |
317 To use it use nx.bipartite.alternating_havel_hakimi_graph | |
318 """ | |
319 G = nx.empty_graph(0, create_using, default=nx.MultiGraph) | |
320 if G.is_directed(): | |
321 raise nx.NetworkXError("Directed Graph not supported") | |
322 | |
323 # length of the each sequence | |
324 naseq = len(aseq) | |
325 nbseq = len(bseq) | |
326 suma = sum(aseq) | |
327 sumb = sum(bseq) | |
328 | |
329 if not suma == sumb: | |
330 raise nx.NetworkXError( | |
331 f"invalid degree sequences, sum(aseq)!=sum(bseq),{suma},{sumb}" | |
332 ) | |
333 | |
334 G = _add_nodes_with_bipartite_label(G, naseq, nbseq) | |
335 | |
336 if len(aseq) == 0 or max(aseq) == 0: | |
337 return G # done if no edges | |
338 # build list of degree-repeated vertex numbers | |
339 astubs = [[aseq[v], v] for v in range(0, naseq)] | |
340 bstubs = [[bseq[v - naseq], v] for v in range(naseq, naseq + nbseq)] | |
341 while astubs: | |
342 astubs.sort() | |
343 (degree, u) = astubs.pop() # take of largest degree node in the a set | |
344 if degree == 0: | |
345 break # done, all are zero | |
346 bstubs.sort() | |
347 small = bstubs[0 : degree // 2] # add these low degree targets | |
348 large = bstubs[(-degree + degree // 2) :] # now high degree targets | |
349 stubs = [x for z in zip(large, small) for x in z] # combine, sorry | |
350 if len(stubs) < len(small) + len(large): # check for zip truncation | |
351 stubs.append(large.pop()) | |
352 for target in stubs: | |
353 v = target[1] | |
354 G.add_edge(u, v) | |
355 target[0] -= 1 # note this updates bstubs too. | |
356 if target[0] == 0: | |
357 bstubs.remove(target) | |
358 | |
359 G.name = "bipartite_alternating_havel_hakimi_graph" | |
360 return G | |
361 | |
362 | |
363 @py_random_state(3) | |
364 def preferential_attachment_graph(aseq, p, create_using=None, seed=None): | |
365 """Create a bipartite graph with a preferential attachment model from | |
366 a given single degree sequence. | |
367 | |
368 The graph is composed of two partitions. Set A has nodes 0 to | |
369 (len(aseq) - 1) and set B has nodes starting with node len(aseq). | |
370 The number of nodes in set B is random. | |
371 | |
372 Parameters | |
373 ---------- | |
374 aseq : list | |
375 Degree sequence for node set A. | |
376 p : float | |
377 Probability that a new bottom node is added. | |
378 create_using : NetworkX graph instance, optional | |
379 Return graph of this type. | |
380 seed : integer, random_state, or None (default) | |
381 Indicator of random number generation state. | |
382 See :ref:`Randomness<randomness>`. | |
383 | |
384 References | |
385 ---------- | |
386 .. [1] Guillaume, J.L. and Latapy, M., | |
387 Bipartite graphs as models of complex networks. | |
388 Physica A: Statistical Mechanics and its Applications, | |
389 2006, 371(2), pp.795-813. | |
390 .. [2] Jean-Loup Guillaume and Matthieu Latapy, | |
391 Bipartite structure of all complex networks, | |
392 Inf. Process. Lett. 90, 2004, pg. 215-221 | |
393 https://doi.org/10.1016/j.ipl.2004.03.007 | |
394 | |
395 Notes | |
396 ----- | |
397 The nodes are assigned the attribute 'bipartite' with the value 0 or 1 | |
398 to indicate which bipartite set the node belongs to. | |
399 | |
400 This function is not imported in the main namespace. | |
401 To use it use nx.bipartite.preferential_attachment_graph | |
402 """ | |
403 G = nx.empty_graph(0, create_using, default=nx.MultiGraph) | |
404 if G.is_directed(): | |
405 raise nx.NetworkXError("Directed Graph not supported") | |
406 | |
407 if p > 1: | |
408 raise nx.NetworkXError(f"probability {p} > 1") | |
409 | |
410 naseq = len(aseq) | |
411 G = _add_nodes_with_bipartite_label(G, naseq, 0) | |
412 vv = [[v] * aseq[v] for v in range(0, naseq)] | |
413 while vv: | |
414 while vv[0]: | |
415 source = vv[0][0] | |
416 vv[0].remove(source) | |
417 if seed.random() < p or len(G) == naseq: | |
418 target = len(G) | |
419 G.add_node(target, bipartite=1) | |
420 G.add_edge(source, target) | |
421 else: | |
422 bb = [[b] * G.degree(b) for b in range(naseq, len(G))] | |
423 # flatten the list of lists into a list. | |
424 bbstubs = reduce(lambda x, y: x + y, bb) | |
425 # choose preferentially a bottom node. | |
426 target = seed.choice(bbstubs) | |
427 G.add_node(target, bipartite=1) | |
428 G.add_edge(source, target) | |
429 vv.remove(vv[0]) | |
430 G.name = "bipartite_preferential_attachment_model" | |
431 return G | |
432 | |
433 | |
434 @py_random_state(3) | |
435 def random_graph(n, m, p, seed=None, directed=False): | |
436 """Returns a bipartite random graph. | |
437 | |
438 This is a bipartite version of the binomial (Erdős-Rényi) graph. | |
439 The graph is composed of two partitions. Set A has nodes 0 to | |
440 (n - 1) and set B has nodes n to (n + m - 1). | |
441 | |
442 Parameters | |
443 ---------- | |
444 n : int | |
445 The number of nodes in the first bipartite set. | |
446 m : int | |
447 The number of nodes in the second bipartite set. | |
448 p : float | |
449 Probability for edge creation. | |
450 seed : integer, random_state, or None (default) | |
451 Indicator of random number generation state. | |
452 See :ref:`Randomness<randomness>`. | |
453 directed : bool, optional (default=False) | |
454 If True return a directed graph | |
455 | |
456 Notes | |
457 ----- | |
458 The bipartite random graph algorithm chooses each of the n*m (undirected) | |
459 or 2*nm (directed) possible edges with probability p. | |
460 | |
461 This algorithm is $O(n+m)$ where $m$ is the expected number of edges. | |
462 | |
463 The nodes are assigned the attribute 'bipartite' with the value 0 or 1 | |
464 to indicate which bipartite set the node belongs to. | |
465 | |
466 This function is not imported in the main namespace. | |
467 To use it use nx.bipartite.random_graph | |
468 | |
469 See Also | |
470 -------- | |
471 gnp_random_graph, configuration_model | |
472 | |
473 References | |
474 ---------- | |
475 .. [1] Vladimir Batagelj and Ulrik Brandes, | |
476 "Efficient generation of large random networks", | |
477 Phys. Rev. E, 71, 036113, 2005. | |
478 """ | |
479 G = nx.Graph() | |
480 G = _add_nodes_with_bipartite_label(G, n, m) | |
481 if directed: | |
482 G = nx.DiGraph(G) | |
483 G.name = f"fast_gnp_random_graph({n},{m},{p})" | |
484 | |
485 if p <= 0: | |
486 return G | |
487 if p >= 1: | |
488 return nx.complete_bipartite_graph(n, m) | |
489 | |
490 lp = math.log(1.0 - p) | |
491 | |
492 v = 0 | |
493 w = -1 | |
494 while v < n: | |
495 lr = math.log(1.0 - seed.random()) | |
496 w = w + 1 + int(lr / lp) | |
497 while w >= m and v < n: | |
498 w = w - m | |
499 v = v + 1 | |
500 if v < n: | |
501 G.add_edge(v, n + w) | |
502 | |
503 if directed: | |
504 # use the same algorithm to | |
505 # add edges from the "m" to "n" set | |
506 v = 0 | |
507 w = -1 | |
508 while v < n: | |
509 lr = math.log(1.0 - seed.random()) | |
510 w = w + 1 + int(lr / lp) | |
511 while w >= m and v < n: | |
512 w = w - m | |
513 v = v + 1 | |
514 if v < n: | |
515 G.add_edge(n + w, v) | |
516 | |
517 return G | |
518 | |
519 | |
520 @py_random_state(3) | |
521 def gnmk_random_graph(n, m, k, seed=None, directed=False): | |
522 """Returns a random bipartite graph G_{n,m,k}. | |
523 | |
524 Produces a bipartite graph chosen randomly out of the set of all graphs | |
525 with n top nodes, m bottom nodes, and k edges. | |
526 The graph is composed of two sets of nodes. | |
527 Set A has nodes 0 to (n - 1) and set B has nodes n to (n + m - 1). | |
528 | |
529 Parameters | |
530 ---------- | |
531 n : int | |
532 The number of nodes in the first bipartite set. | |
533 m : int | |
534 The number of nodes in the second bipartite set. | |
535 k : int | |
536 The number of edges | |
537 seed : integer, random_state, or None (default) | |
538 Indicator of random number generation state. | |
539 See :ref:`Randomness<randomness>`. | |
540 directed : bool, optional (default=False) | |
541 If True return a directed graph | |
542 | |
543 Examples | |
544 -------- | |
545 from nx.algorithms import bipartite | |
546 G = bipartite.gnmk_random_graph(10,20,50) | |
547 | |
548 See Also | |
549 -------- | |
550 gnm_random_graph | |
551 | |
552 Notes | |
553 ----- | |
554 If k > m * n then a complete bipartite graph is returned. | |
555 | |
556 This graph is a bipartite version of the `G_{nm}` random graph model. | |
557 | |
558 The nodes are assigned the attribute 'bipartite' with the value 0 or 1 | |
559 to indicate which bipartite set the node belongs to. | |
560 | |
561 This function is not imported in the main namespace. | |
562 To use it use nx.bipartite.gnmk_random_graph | |
563 """ | |
564 G = nx.Graph() | |
565 G = _add_nodes_with_bipartite_label(G, n, m) | |
566 if directed: | |
567 G = nx.DiGraph(G) | |
568 G.name = f"bipartite_gnm_random_graph({n},{m},{k})" | |
569 if n == 1 or m == 1: | |
570 return G | |
571 max_edges = n * m # max_edges for bipartite networks | |
572 if k >= max_edges: # Maybe we should raise an exception here | |
573 return nx.complete_bipartite_graph(n, m, create_using=G) | |
574 | |
575 top = [n for n, d in G.nodes(data=True) if d["bipartite"] == 0] | |
576 bottom = list(set(G) - set(top)) | |
577 edge_count = 0 | |
578 while edge_count < k: | |
579 # generate random edge,u,v | |
580 u = seed.choice(top) | |
581 v = seed.choice(bottom) | |
582 if v in G[u]: | |
583 continue | |
584 else: | |
585 G.add_edge(u, v) | |
586 edge_count += 1 | |
587 return G | |
588 | |
589 | |
590 def _add_nodes_with_bipartite_label(G, lena, lenb): | |
591 G.add_nodes_from(range(0, lena + lenb)) | |
592 b = dict(zip(range(0, lena), [0] * lena)) | |
593 b.update(dict(zip(range(lena, lena + lenb), [1] * lenb))) | |
594 nx.set_node_attributes(G, b, "bipartite") | |
595 return G |