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