Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/classic.py: 28%
221 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Generators for some classic graphs.
3The typical graph builder function is called as follows:
5>>> G = nx.complete_graph(100)
7returning the complete graph on n nodes labeled 0, .., 99
8as a simple graph. Except for `empty_graph`, all the functions
9in this module return a Graph class (i.e. a simple, undirected graph).
11"""
13import itertools
14import numbers
16import networkx as nx
17from networkx.classes import Graph
18from networkx.exception import NetworkXError
19from networkx.utils import nodes_or_number, pairwise
21__all__ = [
22 "balanced_tree",
23 "barbell_graph",
24 "binomial_tree",
25 "complete_graph",
26 "complete_multipartite_graph",
27 "circular_ladder_graph",
28 "circulant_graph",
29 "cycle_graph",
30 "dorogovtsev_goltsev_mendes_graph",
31 "empty_graph",
32 "full_rary_tree",
33 "ladder_graph",
34 "lollipop_graph",
35 "null_graph",
36 "path_graph",
37 "star_graph",
38 "trivial_graph",
39 "turan_graph",
40 "wheel_graph",
41]
44# -------------------------------------------------------------------
45# Some Classic Graphs
46# -------------------------------------------------------------------
49def _tree_edges(n, r):
50 if n == 0:
51 return
52 # helper function for trees
53 # yields edges in rooted tree at 0 with n nodes and branching ratio r
54 nodes = iter(range(n))
55 parents = [next(nodes)] # stack of max length r
56 while parents:
57 source = parents.pop(0)
58 for i in range(r):
59 try:
60 target = next(nodes)
61 parents.append(target)
62 yield source, target
63 except StopIteration:
64 break
67@nx._dispatch(graphs=None)
68def full_rary_tree(r, n, create_using=None):
69 """Creates a full r-ary tree of `n` nodes.
71 Sometimes called a k-ary, n-ary, or m-ary tree.
72 "... all non-leaf nodes have exactly r children and all levels
73 are full except for some rightmost position of the bottom level
74 (if a leaf at the bottom level is missing, then so are all of the
75 leaves to its right." [1]_
77 Parameters
78 ----------
79 r : int
80 branching factor of the tree
81 n : int
82 Number of nodes in the tree
83 create_using : NetworkX graph constructor, optional (default=nx.Graph)
84 Graph type to create. If graph instance, then cleared before populated.
86 Returns
87 -------
88 G : networkx Graph
89 An r-ary tree with n nodes
91 References
92 ----------
93 .. [1] An introduction to data structures and algorithms,
94 James Andrew Storer, Birkhauser Boston 2001, (page 225).
95 """
96 G = empty_graph(n, create_using)
97 G.add_edges_from(_tree_edges(n, r))
98 return G
101@nx._dispatch(graphs=None)
102def balanced_tree(r, h, create_using=None):
103 """Returns the perfectly balanced `r`-ary tree of height `h`.
105 Parameters
106 ----------
107 r : int
108 Branching factor of the tree; each node will have `r`
109 children.
111 h : int
112 Height of the tree.
114 create_using : NetworkX graph constructor, optional (default=nx.Graph)
115 Graph type to create. If graph instance, then cleared before populated.
117 Returns
118 -------
119 G : NetworkX graph
120 A balanced `r`-ary tree of height `h`.
122 Notes
123 -----
124 This is the rooted tree where all leaves are at distance `h` from
125 the root. The root has degree `r` and all other internal nodes
126 have degree `r + 1`.
128 Node labels are integers, starting from zero.
130 A balanced tree is also known as a *complete r-ary tree*.
132 """
133 # The number of nodes in the balanced tree is `1 + r + ... + r^h`,
134 # which is computed by using the closed-form formula for a geometric
135 # sum with ratio `r`. In the special case that `r` is 1, the number
136 # of nodes is simply `h + 1` (since the tree is actually a path
137 # graph).
138 if r == 1:
139 n = h + 1
140 else:
141 # This must be an integer if both `r` and `h` are integers. If
142 # they are not, we force integer division anyway.
143 n = (1 - r ** (h + 1)) // (1 - r)
144 return full_rary_tree(r, n, create_using=create_using)
147@nx._dispatch(graphs=None)
148def barbell_graph(m1, m2, create_using=None):
149 """Returns the Barbell Graph: two complete graphs connected by a path.
151 Parameters
152 ----------
153 m1 : int
154 Size of the left and right barbells, must be greater than 2.
156 m2 : int
157 Length of the path connecting the barbells.
159 create_using : NetworkX graph constructor, optional (default=nx.Graph)
160 Graph type to create. If graph instance, then cleared before populated.
161 Only undirected Graphs are supported.
163 Returns
164 -------
165 G : NetworkX graph
166 A barbell graph.
168 Notes
169 -----
172 Two identical complete graphs $K_{m1}$ form the left and right bells,
173 and are connected by a path $P_{m2}$.
175 The `2*m1+m2` nodes are numbered
176 `0, ..., m1-1` for the left barbell,
177 `m1, ..., m1+m2-1` for the path,
178 and `m1+m2, ..., 2*m1+m2-1` for the right barbell.
180 The 3 subgraphs are joined via the edges `(m1-1, m1)` and
181 `(m1+m2-1, m1+m2)`. If `m2=0`, this is merely two complete
182 graphs joined together.
184 This graph is an extremal example in David Aldous
185 and Jim Fill's e-text on Random Walks on Graphs.
187 """
188 if m1 < 2:
189 raise NetworkXError("Invalid graph description, m1 should be >=2")
190 if m2 < 0:
191 raise NetworkXError("Invalid graph description, m2 should be >=0")
193 # left barbell
194 G = complete_graph(m1, create_using)
195 if G.is_directed():
196 raise NetworkXError("Directed Graph not supported")
198 # connecting path
199 G.add_nodes_from(range(m1, m1 + m2 - 1))
200 if m2 > 1:
201 G.add_edges_from(pairwise(range(m1, m1 + m2)))
203 # right barbell
204 G.add_edges_from(
205 (u, v) for u in range(m1 + m2, 2 * m1 + m2) for v in range(u + 1, 2 * m1 + m2)
206 )
208 # connect it up
209 G.add_edge(m1 - 1, m1)
210 if m2 > 0:
211 G.add_edge(m1 + m2 - 1, m1 + m2)
213 return G
216@nx._dispatch(graphs=None)
217def binomial_tree(n, create_using=None):
218 """Returns the Binomial Tree of order n.
220 The binomial tree of order 0 consists of a single node. A binomial tree of order k
221 is defined recursively by linking two binomial trees of order k-1: the root of one is
222 the leftmost child of the root of the other.
224 Parameters
225 ----------
226 n : int
227 Order of the binomial tree.
229 create_using : NetworkX graph constructor, optional (default=nx.Graph)
230 Graph type to create. If graph instance, then cleared before populated.
232 Returns
233 -------
234 G : NetworkX graph
235 A binomial tree of $2^n$ nodes and $2^n - 1$ edges.
237 """
238 G = nx.empty_graph(1, create_using)
240 N = 1
241 for i in range(n):
242 # Use G.edges() to ensure 2-tuples. G.edges is 3-tuple for MultiGraph
243 edges = [(u + N, v + N) for (u, v) in G.edges()]
244 G.add_edges_from(edges)
245 G.add_edge(0, N)
246 N *= 2
247 return G
250@nodes_or_number(0)
251@nx._dispatch(graphs=None)
252def complete_graph(n, create_using=None):
253 """Return the complete graph `K_n` with n nodes.
255 A complete graph on `n` nodes means that all pairs
256 of distinct nodes have an edge connecting them.
258 Parameters
259 ----------
260 n : int or iterable container of nodes
261 If n is an integer, nodes are from range(n).
262 If n is a container of nodes, those nodes appear in the graph.
263 Warning: n is not checked for duplicates and if present the
264 resulting graph may not be as desired. Make sure you have no duplicates.
265 create_using : NetworkX graph constructor, optional (default=nx.Graph)
266 Graph type to create. If graph instance, then cleared before populated.
268 Examples
269 --------
270 >>> G = nx.complete_graph(9)
271 >>> len(G)
272 9
273 >>> G.size()
274 36
275 >>> G = nx.complete_graph(range(11, 14))
276 >>> list(G.nodes())
277 [11, 12, 13]
278 >>> G = nx.complete_graph(4, nx.DiGraph())
279 >>> G.is_directed()
280 True
282 """
283 _, nodes = n
284 G = empty_graph(nodes, create_using)
285 if len(nodes) > 1:
286 if G.is_directed():
287 edges = itertools.permutations(nodes, 2)
288 else:
289 edges = itertools.combinations(nodes, 2)
290 G.add_edges_from(edges)
291 return G
294@nx._dispatch(graphs=None)
295def circular_ladder_graph(n, create_using=None):
296 """Returns the circular ladder graph $CL_n$ of length n.
298 $CL_n$ consists of two concentric n-cycles in which
299 each of the n pairs of concentric nodes are joined by an edge.
301 Node labels are the integers 0 to n-1
303 """
304 G = ladder_graph(n, create_using)
305 G.add_edge(0, n - 1)
306 G.add_edge(n, 2 * n - 1)
307 return G
310@nx._dispatch(graphs=None)
311def circulant_graph(n, offsets, create_using=None):
312 r"""Returns the circulant graph $Ci_n(x_1, x_2, ..., x_m)$ with $n$ nodes.
314 The circulant graph $Ci_n(x_1, ..., x_m)$ consists of $n$ nodes $0, ..., n-1$
315 such that node $i$ is connected to nodes $(i + x) \mod n$ and $(i - x) \mod n$
316 for all $x$ in $x_1, ..., x_m$. Thus $Ci_n(1)$ is a cycle graph.
318 Parameters
319 ----------
320 n : integer
321 The number of nodes in the graph.
322 offsets : list of integers
323 A list of node offsets, $x_1$ up to $x_m$, as described above.
324 create_using : NetworkX graph constructor, optional (default=nx.Graph)
325 Graph type to create. If graph instance, then cleared before populated.
327 Returns
328 -------
329 NetworkX Graph of type create_using
331 Examples
332 --------
333 Many well-known graph families are subfamilies of the circulant graphs;
334 for example, to create the cycle graph on n points, we connect every
335 node to nodes on either side (with offset plus or minus one). For n = 10,
337 >>> G = nx.circulant_graph(10, [1])
338 >>> edges = [
339 ... (0, 9),
340 ... (0, 1),
341 ... (1, 2),
342 ... (2, 3),
343 ... (3, 4),
344 ... (4, 5),
345 ... (5, 6),
346 ... (6, 7),
347 ... (7, 8),
348 ... (8, 9),
349 ... ]
350 ...
351 >>> sorted(edges) == sorted(G.edges())
352 True
354 Similarly, we can create the complete graph
355 on 5 points with the set of offsets [1, 2]:
357 >>> G = nx.circulant_graph(5, [1, 2])
358 >>> edges = [
359 ... (0, 1),
360 ... (0, 2),
361 ... (0, 3),
362 ... (0, 4),
363 ... (1, 2),
364 ... (1, 3),
365 ... (1, 4),
366 ... (2, 3),
367 ... (2, 4),
368 ... (3, 4),
369 ... ]
370 ...
371 >>> sorted(edges) == sorted(G.edges())
372 True
374 """
375 G = empty_graph(n, create_using)
376 for i in range(n):
377 for j in offsets:
378 G.add_edge(i, (i - j) % n)
379 G.add_edge(i, (i + j) % n)
380 return G
383@nodes_or_number(0)
384@nx._dispatch(graphs=None)
385def cycle_graph(n, create_using=None):
386 """Returns the cycle graph $C_n$ of cyclically connected nodes.
388 $C_n$ is a path with its two end-nodes connected.
390 Parameters
391 ----------
392 n : int or iterable container of nodes
393 If n is an integer, nodes are from `range(n)`.
394 If n is a container of nodes, those nodes appear in the graph.
395 Warning: n is not checked for duplicates and if present the
396 resulting graph may not be as desired. Make sure you have no duplicates.
397 create_using : NetworkX graph constructor, optional (default=nx.Graph)
398 Graph type to create. If graph instance, then cleared before populated.
400 Notes
401 -----
402 If create_using is directed, the direction is in increasing order.
404 """
405 _, nodes = n
406 G = empty_graph(nodes, create_using)
407 G.add_edges_from(pairwise(nodes, cyclic=True))
408 return G
411@nx._dispatch(graphs=None)
412def dorogovtsev_goltsev_mendes_graph(n, create_using=None):
413 """Returns the hierarchically constructed Dorogovtsev-Goltsev-Mendes graph.
415 The Dorogovtsev-Goltsev-Mendes [1]_ procedure produces a scale-free graph
416 deterministically with the following properties for a given `n`:
417 - Total number of nodes = ``3 * (3**n + 1) / 2``
418 - Total number of edges = ``3 ** (n + 1)``
420 Parameters
421 ----------
422 n : integer
423 The generation number.
425 create_using : NetworkX Graph, optional
426 Graph type to be returned. Directed graphs and multi graphs are not
427 supported.
429 Returns
430 -------
431 G : NetworkX Graph
433 Examples
434 --------
435 >>> G = nx.dorogovtsev_goltsev_mendes_graph(3)
436 >>> G.number_of_nodes()
437 15
438 >>> G.number_of_edges()
439 27
440 >>> nx.is_planar(G)
441 True
443 References
444 ----------
445 .. [1] S. N. Dorogovtsev, A. V. Goltsev and J. F. F. Mendes,
446 "Pseudofractal scale-free web", Physical Review E 65, 066122, 2002.
447 https://arxiv.org/pdf/cond-mat/0112143.pdf
448 """
449 G = empty_graph(0, create_using)
450 if G.is_directed():
451 raise NetworkXError("Directed Graph not supported")
452 if G.is_multigraph():
453 raise NetworkXError("Multigraph not supported")
455 G.add_edge(0, 1)
456 if n == 0:
457 return G
458 new_node = 2 # next node to be added
459 for i in range(1, n + 1): # iterate over number of generations.
460 last_generation_edges = list(G.edges())
461 number_of_edges_in_last_generation = len(last_generation_edges)
462 for j in range(number_of_edges_in_last_generation):
463 G.add_edge(new_node, last_generation_edges[j][0])
464 G.add_edge(new_node, last_generation_edges[j][1])
465 new_node += 1
466 return G
469@nodes_or_number(0)
470@nx._dispatch(graphs=None)
471def empty_graph(n=0, create_using=None, default=Graph):
472 """Returns the empty graph with n nodes and zero edges.
474 Parameters
475 ----------
476 n : int or iterable container of nodes (default = 0)
477 If n is an integer, nodes are from `range(n)`.
478 If n is a container of nodes, those nodes appear in the graph.
479 create_using : Graph Instance, Constructor or None
480 Indicator of type of graph to return.
481 If a Graph-type instance, then clear and use it.
482 If None, use the `default` constructor.
483 If a constructor, call it to create an empty graph.
484 default : Graph constructor (optional, default = nx.Graph)
485 The constructor to use if create_using is None.
486 If None, then nx.Graph is used.
487 This is used when passing an unknown `create_using` value
488 through your home-grown function to `empty_graph` and
489 you want a default constructor other than nx.Graph.
491 Examples
492 --------
493 >>> G = nx.empty_graph(10)
494 >>> G.number_of_nodes()
495 10
496 >>> G.number_of_edges()
497 0
498 >>> G = nx.empty_graph("ABC")
499 >>> G.number_of_nodes()
500 3
501 >>> sorted(G)
502 ['A', 'B', 'C']
504 Notes
505 -----
506 The variable create_using should be a Graph Constructor or a
507 "graph"-like object. Constructors, e.g. `nx.Graph` or `nx.MultiGraph`
508 will be used to create the returned graph. "graph"-like objects
509 will be cleared (nodes and edges will be removed) and refitted as
510 an empty "graph" with nodes specified in n. This capability
511 is useful for specifying the class-nature of the resulting empty
512 "graph" (i.e. Graph, DiGraph, MyWeirdGraphClass, etc.).
514 The variable create_using has three main uses:
515 Firstly, the variable create_using can be used to create an
516 empty digraph, multigraph, etc. For example,
518 >>> n = 10
519 >>> G = nx.empty_graph(n, create_using=nx.DiGraph)
521 will create an empty digraph on n nodes.
523 Secondly, one can pass an existing graph (digraph, multigraph,
524 etc.) via create_using. For example, if G is an existing graph
525 (resp. digraph, multigraph, etc.), then empty_graph(n, create_using=G)
526 will empty G (i.e. delete all nodes and edges using G.clear())
527 and then add n nodes and zero edges, and return the modified graph.
529 Thirdly, when constructing your home-grown graph creation function
530 you can use empty_graph to construct the graph by passing a user
531 defined create_using to empty_graph. In this case, if you want the
532 default constructor to be other than nx.Graph, specify `default`.
534 >>> def mygraph(n, create_using=None):
535 ... G = nx.empty_graph(n, create_using, nx.MultiGraph)
536 ... G.add_edges_from([(0, 1), (0, 1)])
537 ... return G
538 >>> G = mygraph(3)
539 >>> G.is_multigraph()
540 True
541 >>> G = mygraph(3, nx.Graph)
542 >>> G.is_multigraph()
543 False
545 See also create_empty_copy(G).
547 """
548 if create_using is None:
549 G = default()
550 elif isinstance(create_using, type):
551 G = create_using()
552 elif not hasattr(create_using, "adj"):
553 raise TypeError("create_using is not a valid NetworkX graph type or instance")
554 else:
555 # create_using is a NetworkX style Graph
556 create_using.clear()
557 G = create_using
559 _, nodes = n
560 G.add_nodes_from(nodes)
561 return G
564@nx._dispatch(graphs=None)
565def ladder_graph(n, create_using=None):
566 """Returns the Ladder graph of length n.
568 This is two paths of n nodes, with
569 each pair connected by a single edge.
571 Node labels are the integers 0 to 2*n - 1.
573 """
574 G = empty_graph(2 * n, create_using)
575 if G.is_directed():
576 raise NetworkXError("Directed Graph not supported")
577 G.add_edges_from(pairwise(range(n)))
578 G.add_edges_from(pairwise(range(n, 2 * n)))
579 G.add_edges_from((v, v + n) for v in range(n))
580 return G
583@nodes_or_number([0, 1])
584@nx._dispatch(graphs=None)
585def lollipop_graph(m, n, create_using=None):
586 """Returns the Lollipop Graph; `K_m` connected to `P_n`.
588 This is the Barbell Graph without the right barbell.
590 Parameters
591 ----------
592 m, n : int or iterable container of nodes (default = 0)
593 If an integer, nodes are from `range(m)` and `range(m,m+n)`.
594 If a container of nodes, those nodes appear in the graph.
595 Warning: m and n are not checked for duplicates and if present the
596 resulting graph may not be as desired. Make sure you have no duplicates.
598 The nodes for m appear in the complete graph $K_m$ and the nodes
599 for n appear in the path $P_n$
600 create_using : NetworkX graph constructor, optional (default=nx.Graph)
601 Graph type to create. If graph instance, then cleared before populated.
603 Notes
604 -----
605 The 2 subgraphs are joined via an edge (m-1, m).
606 If n=0, this is merely a complete graph.
608 (This graph is an extremal example in David Aldous and Jim
609 Fill's etext on Random Walks on Graphs.)
611 """
612 m, m_nodes = m
613 M = len(m_nodes)
614 if M < 2:
615 raise NetworkXError("Invalid description: m should indicate at least 2 nodes")
617 n, n_nodes = n
618 if isinstance(m, numbers.Integral) and isinstance(n, numbers.Integral):
619 n_nodes = list(range(M, M + n))
620 N = len(n_nodes)
622 # the ball
623 G = complete_graph(m_nodes, create_using)
624 if G.is_directed():
625 raise NetworkXError("Directed Graph not supported")
627 # the stick
628 G.add_nodes_from(n_nodes)
629 if N > 1:
630 G.add_edges_from(pairwise(n_nodes))
632 if len(G) != M + N:
633 raise NetworkXError("Nodes must be distinct in containers m and n")
635 # connect ball to stick
636 if M > 0 and N > 0:
637 G.add_edge(m_nodes[-1], n_nodes[0])
638 return G
641@nx._dispatch(graphs=None)
642def null_graph(create_using=None):
643 """Returns the Null graph with no nodes or edges.
645 See empty_graph for the use of create_using.
647 """
648 G = empty_graph(0, create_using)
649 return G
652@nodes_or_number(0)
653@nx._dispatch(graphs=None)
654def path_graph(n, create_using=None):
655 """Returns the Path graph `P_n` of linearly connected nodes.
657 Parameters
658 ----------
659 n : int or iterable
660 If an integer, nodes are 0 to n - 1.
661 If an iterable of nodes, in the order they appear in the path.
662 Warning: n is not checked for duplicates and if present the
663 resulting graph may not be as desired. Make sure you have no duplicates.
664 create_using : NetworkX graph constructor, optional (default=nx.Graph)
665 Graph type to create. If graph instance, then cleared before populated.
667 """
668 _, nodes = n
669 G = empty_graph(nodes, create_using)
670 G.add_edges_from(pairwise(nodes))
671 return G
674@nodes_or_number(0)
675@nx._dispatch(graphs=None)
676def star_graph(n, create_using=None):
677 """Return the star graph
679 The star graph consists of one center node connected to n outer nodes.
681 Parameters
682 ----------
683 n : int or iterable
684 If an integer, node labels are 0 to n with center 0.
685 If an iterable of nodes, the center is the first.
686 Warning: n is not checked for duplicates and if present the
687 resulting graph may not be as desired. Make sure you have no duplicates.
688 create_using : NetworkX graph constructor, optional (default=nx.Graph)
689 Graph type to create. If graph instance, then cleared before populated.
691 Notes
692 -----
693 The graph has n+1 nodes for integer n.
694 So star_graph(3) is the same as star_graph(range(4)).
695 """
696 n, nodes = n
697 if isinstance(n, numbers.Integral):
698 nodes.append(n) # there should be n+1 nodes
699 G = empty_graph(nodes, create_using)
700 if G.is_directed():
701 raise NetworkXError("Directed Graph not supported")
703 if len(nodes) > 1:
704 hub, *spokes = nodes
705 G.add_edges_from((hub, node) for node in spokes)
706 return G
709@nx._dispatch(graphs=None)
710def trivial_graph(create_using=None):
711 """Return the Trivial graph with one node (with label 0) and no edges."""
712 G = empty_graph(1, create_using)
713 return G
716@nx._dispatch(graphs=None)
717def turan_graph(n, r):
718 r"""Return the Turan Graph
720 The Turan Graph is a complete multipartite graph on $n$ nodes
721 with $r$ disjoint subsets. That is, edges connect each node to
722 every node not in its subset.
724 Given $n$ and $r$, we create a complete multipartite graph with
725 $r-(n \mod r)$ partitions of size $n/r$, rounded down, and
726 $n \mod r$ partitions of size $n/r+1$, rounded down.
728 Parameters
729 ----------
730 n : int
731 The number of nodes.
732 r : int
733 The number of partitions.
734 Must be less than or equal to n.
736 Notes
737 -----
738 Must satisfy $1 <= r <= n$.
739 The graph has $(r-1)(n^2)/(2r)$ edges, rounded down.
740 """
742 if not 1 <= r <= n:
743 raise NetworkXError("Must satisfy 1 <= r <= n")
745 partitions = [n // r] * (r - (n % r)) + [n // r + 1] * (n % r)
746 G = complete_multipartite_graph(*partitions)
747 return G
750@nodes_or_number(0)
751@nx._dispatch(graphs=None)
752def wheel_graph(n, create_using=None):
753 """Return the wheel graph
755 The wheel graph consists of a hub node connected to a cycle of (n-1) nodes.
757 Parameters
758 ----------
759 n : int or iterable
760 If an integer, node labels are 0 to n with center 0.
761 If an iterable of nodes, the center is the first.
762 Warning: n is not checked for duplicates and if present the
763 resulting graph may not be as desired. Make sure you have no duplicates.
764 create_using : NetworkX graph constructor, optional (default=nx.Graph)
765 Graph type to create. If graph instance, then cleared before populated.
767 Node labels are the integers 0 to n - 1.
768 """
769 _, nodes = n
770 G = empty_graph(nodes, create_using)
771 if G.is_directed():
772 raise NetworkXError("Directed Graph not supported")
774 if len(nodes) > 1:
775 hub, *rim = nodes
776 G.add_edges_from((hub, node) for node in rim)
777 if len(rim) > 1:
778 G.add_edges_from(pairwise(rim, cyclic=True))
779 return G
782@nx._dispatch(graphs=None)
783def complete_multipartite_graph(*subset_sizes):
784 """Returns the complete multipartite graph with the specified subset sizes.
786 Parameters
787 ----------
788 subset_sizes : tuple of integers or tuple of node iterables
789 The arguments can either all be integer number of nodes or they
790 can all be iterables of nodes. If integers, they represent the
791 number of nodes in each subset of the multipartite graph.
792 If iterables, each is used to create the nodes for that subset.
793 The length of subset_sizes is the number of subsets.
795 Returns
796 -------
797 G : NetworkX Graph
798 Returns the complete multipartite graph with the specified subsets.
800 For each node, the node attribute 'subset' is an integer
801 indicating which subset contains the node.
803 Examples
804 --------
805 Creating a complete tripartite graph, with subsets of one, two, and three
806 nodes, respectively.
808 >>> G = nx.complete_multipartite_graph(1, 2, 3)
809 >>> [G.nodes[u]["subset"] for u in G]
810 [0, 1, 1, 2, 2, 2]
811 >>> list(G.edges(0))
812 [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]
813 >>> list(G.edges(2))
814 [(2, 0), (2, 3), (2, 4), (2, 5)]
815 >>> list(G.edges(4))
816 [(4, 0), (4, 1), (4, 2)]
818 >>> G = nx.complete_multipartite_graph("a", "bc", "def")
819 >>> [G.nodes[u]["subset"] for u in sorted(G)]
820 [0, 1, 1, 2, 2, 2]
822 Notes
823 -----
824 This function generalizes several other graph builder functions.
826 - If no subset sizes are given, this returns the null graph.
827 - If a single subset size `n` is given, this returns the empty graph on
828 `n` nodes.
829 - If two subset sizes `m` and `n` are given, this returns the complete
830 bipartite graph on `m + n` nodes.
831 - If subset sizes `1` and `n` are given, this returns the star graph on
832 `n + 1` nodes.
834 See also
835 --------
836 complete_bipartite_graph
837 """
838 # The complete multipartite graph is an undirected simple graph.
839 G = Graph()
841 if len(subset_sizes) == 0:
842 return G
844 # set up subsets of nodes
845 try:
846 extents = pairwise(itertools.accumulate((0,) + subset_sizes))
847 subsets = [range(start, end) for start, end in extents]
848 except TypeError:
849 subsets = subset_sizes
851 # add nodes with subset attribute
852 # while checking that ints are not mixed with iterables
853 try:
854 for i, subset in enumerate(subsets):
855 G.add_nodes_from(subset, subset=i)
856 except TypeError as err:
857 raise NetworkXError("Arguments must be all ints or all iterables") from err
859 # Across subsets, all nodes should be adjacent.
860 # We can use itertools.combinations() because undirected.
861 for subset1, subset2 in itertools.combinations(subsets, 2):
862 G.add_edges_from(itertools.product(subset1, subset2))
863 return G