### comparison env/lib/python3.9/site-packages/networkx/algorithms/bipartite/generators.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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]
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
205 target -= 1 # note this updates bstubs too.
206 if target == 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
278 target -= 1 # note this updates bstubs too.
279 if target == 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
355 target -= 1 # note this updates bstubs too.
356 if target == 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 ..  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 ..  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:
415 source = vv
416 vv.remove(source)
417 if seed.random() < p or len(G) == naseq:
418 target = len(G)
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)
429 vv.remove(vv)
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
470 --------
471 gnp_random_graph, configuration_model
472
473 References
474 ----------
475 ..  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
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: