Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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 "kneser_graph",
34 "ladder_graph",
35 "lollipop_graph",
36 "null_graph",
37 "path_graph",
38 "star_graph",
39 "tadpole_graph",
40 "trivial_graph",
41 "turan_graph",
42 "wheel_graph",
43]
46# -------------------------------------------------------------------
47# Some Classic Graphs
48# -------------------------------------------------------------------
51def _tree_edges(n, r):
52 if n == 0:
53 return
54 # helper function for trees
55 # yields edges in rooted tree at 0 with n nodes and branching ratio r
56 nodes = iter(range(n))
57 parents = [next(nodes)] # stack of max length r
58 while parents:
59 source = parents.pop(0)
60 for i in range(r):
61 try:
62 target = next(nodes)
63 parents.append(target)
64 yield source, target
65 except StopIteration:
66 break
69@nx._dispatchable(graphs=None, returns_graph=True)
70def full_rary_tree(r, n, create_using=None):
71 """Creates a full r-ary tree of `n` nodes.
73 Sometimes called a k-ary, n-ary, or m-ary tree.
74 "... all non-leaf nodes have exactly r children and all levels
75 are full except for some rightmost position of the bottom level
76 (if a leaf at the bottom level is missing, then so are all of the
77 leaves to its right." [1]_
79 .. plot::
81 >>> nx.draw(nx.full_rary_tree(2, 10))
83 Parameters
84 ----------
85 r : int
86 branching factor of the tree
87 n : int
88 Number of nodes in the tree
89 create_using : NetworkX graph constructor, optional (default=nx.Graph)
90 Graph type to create. If graph instance, then cleared before populated.
92 Returns
93 -------
94 G : networkx Graph
95 An r-ary tree with n nodes
97 References
98 ----------
99 .. [1] An introduction to data structures and algorithms,
100 James Andrew Storer, Birkhauser Boston 2001, (page 225).
101 """
102 G = empty_graph(n, create_using)
103 G.add_edges_from(_tree_edges(n, r))
104 return G
107@nx._dispatchable(graphs=None, returns_graph=True)
108def kneser_graph(n, k):
109 """Returns the Kneser Graph with parameters `n` and `k`.
111 The Kneser Graph has nodes that are k-tuples (subsets) of the integers
112 between 0 and ``n-1``. Nodes are adjacent if their corresponding sets are disjoint.
114 Parameters
115 ----------
116 n: int
117 Number of integers from which to make node subsets.
118 Subsets are drawn from ``set(range(n))``.
119 k: int
120 Size of the subsets.
122 Returns
123 -------
124 G : NetworkX Graph
126 Examples
127 --------
128 >>> G = nx.kneser_graph(5, 2)
129 >>> G.number_of_nodes()
130 10
131 >>> G.number_of_edges()
132 15
133 >>> nx.is_isomorphic(G, nx.petersen_graph())
134 True
135 """
136 if n <= 0:
137 raise NetworkXError("n should be greater than zero")
138 if k <= 0 or k > n:
139 raise NetworkXError("k should be greater than zero and smaller than n")
141 G = nx.Graph()
142 # Create all k-subsets of [0, 1, ..., n-1]
143 subsets = list(itertools.combinations(range(n), k))
145 if 2 * k > n:
146 G.add_nodes_from(subsets)
148 universe = set(range(n))
149 comb = itertools.combinations # only to make it all fit on one line
150 G.add_edges_from((s, t) for s in subsets for t in comb(universe - set(s), k))
151 return G
154@nx._dispatchable(graphs=None, returns_graph=True)
155def balanced_tree(r, h, create_using=None):
156 """Returns the perfectly balanced `r`-ary tree of height `h`.
158 .. plot::
160 >>> nx.draw(nx.balanced_tree(2, 3))
162 Parameters
163 ----------
164 r : int
165 Branching factor of the tree; each node will have `r`
166 children.
168 h : int
169 Height of the tree.
171 create_using : NetworkX graph constructor, optional (default=nx.Graph)
172 Graph type to create. If graph instance, then cleared before populated.
174 Returns
175 -------
176 G : NetworkX graph
177 A balanced `r`-ary tree of height `h`.
179 Notes
180 -----
181 This is the rooted tree where all leaves are at distance `h` from
182 the root. The root has degree `r` and all other internal nodes
183 have degree `r + 1`.
185 Node labels are integers, starting from zero.
187 A balanced tree is also known as a *complete r-ary tree*.
189 """
190 # The number of nodes in the balanced tree is `1 + r + ... + r^h`,
191 # which is computed by using the closed-form formula for a geometric
192 # sum with ratio `r`. In the special case that `r` is 1, the number
193 # of nodes is simply `h + 1` (since the tree is actually a path
194 # graph).
195 if r == 1:
196 n = h + 1
197 else:
198 # This must be an integer if both `r` and `h` are integers. If
199 # they are not, we force integer division anyway.
200 n = (1 - r ** (h + 1)) // (1 - r)
201 return full_rary_tree(r, n, create_using=create_using)
204@nx._dispatchable(graphs=None, returns_graph=True)
205def barbell_graph(m1, m2, create_using=None):
206 """Returns the Barbell Graph: two complete graphs connected by a path.
208 .. plot::
210 >>> nx.draw(nx.barbell_graph(4, 2))
212 Parameters
213 ----------
214 m1 : int
215 Size of the left and right barbells, must be greater than 2.
217 m2 : int
218 Length of the path connecting the barbells.
220 create_using : NetworkX graph constructor, optional (default=nx.Graph)
221 Graph type to create. If graph instance, then cleared before populated.
222 Only undirected Graphs are supported.
224 Returns
225 -------
226 G : NetworkX graph
227 A barbell graph.
229 Notes
230 -----
233 Two identical complete graphs $K_{m1}$ form the left and right bells,
234 and are connected by a path $P_{m2}$.
236 The `2*m1+m2` nodes are numbered
237 `0, ..., m1-1` for the left barbell,
238 `m1, ..., m1+m2-1` for the path,
239 and `m1+m2, ..., 2*m1+m2-1` for the right barbell.
241 The 3 subgraphs are joined via the edges `(m1-1, m1)` and
242 `(m1+m2-1, m1+m2)`. If `m2=0`, this is merely two complete
243 graphs joined together.
245 This graph is an extremal example in David Aldous
246 and Jim Fill's e-text on Random Walks on Graphs.
248 """
249 if m1 < 2:
250 raise NetworkXError("Invalid graph description, m1 should be >=2")
251 if m2 < 0:
252 raise NetworkXError("Invalid graph description, m2 should be >=0")
254 # left barbell
255 G = complete_graph(m1, create_using)
256 if G.is_directed():
257 raise NetworkXError("Directed Graph not supported")
259 # connecting path
260 G.add_nodes_from(range(m1, m1 + m2 - 1))
261 if m2 > 1:
262 G.add_edges_from(pairwise(range(m1, m1 + m2)))
264 # right barbell
265 G.add_edges_from(
266 (u, v) for u in range(m1 + m2, 2 * m1 + m2) for v in range(u + 1, 2 * m1 + m2)
267 )
269 # connect it up
270 G.add_edge(m1 - 1, m1)
271 if m2 > 0:
272 G.add_edge(m1 + m2 - 1, m1 + m2)
274 return G
277@nx._dispatchable(graphs=None, returns_graph=True)
278def binomial_tree(n, create_using=None):
279 """Returns the Binomial Tree of order n.
281 The binomial tree of order 0 consists of a single node. A binomial tree of order k
282 is defined recursively by linking two binomial trees of order k-1: the root of one is
283 the leftmost child of the root of the other.
285 .. plot::
287 >>> nx.draw(nx.binomial_tree(3))
289 Parameters
290 ----------
291 n : int
292 Order of the binomial tree.
294 create_using : NetworkX graph constructor, optional (default=nx.Graph)
295 Graph type to create. If graph instance, then cleared before populated.
297 Returns
298 -------
299 G : NetworkX graph
300 A binomial tree of $2^n$ nodes and $2^n - 1$ edges.
302 """
303 G = nx.empty_graph(1, create_using)
305 N = 1
306 for i in range(n):
307 # Use G.edges() to ensure 2-tuples. G.edges is 3-tuple for MultiGraph
308 edges = [(u + N, v + N) for (u, v) in G.edges()]
309 G.add_edges_from(edges)
310 G.add_edge(0, N)
311 N *= 2
312 return G
315@nx._dispatchable(graphs=None, returns_graph=True)
316@nodes_or_number(0)
317def complete_graph(n, create_using=None):
318 """Return the complete graph `K_n` with n nodes.
320 A complete graph on `n` nodes means that all pairs
321 of distinct nodes have an edge connecting them.
323 .. plot::
325 >>> nx.draw(nx.complete_graph(5))
327 Parameters
328 ----------
329 n : int or iterable container of nodes
330 If n is an integer, nodes are from range(n).
331 If n is a container of nodes, those nodes appear in the graph.
332 Warning: n is not checked for duplicates and if present the
333 resulting graph may not be as desired. Make sure you have no duplicates.
334 create_using : NetworkX graph constructor, optional (default=nx.Graph)
335 Graph type to create. If graph instance, then cleared before populated.
337 Examples
338 --------
339 >>> G = nx.complete_graph(9)
340 >>> len(G)
341 9
342 >>> G.size()
343 36
344 >>> G = nx.complete_graph(range(11, 14))
345 >>> list(G.nodes())
346 [11, 12, 13]
347 >>> G = nx.complete_graph(4, nx.DiGraph())
348 >>> G.is_directed()
349 True
351 """
352 _, nodes = n
353 G = empty_graph(nodes, create_using)
354 if len(nodes) > 1:
355 if G.is_directed():
356 edges = itertools.permutations(nodes, 2)
357 else:
358 edges = itertools.combinations(nodes, 2)
359 G.add_edges_from(edges)
360 return G
363@nx._dispatchable(graphs=None, returns_graph=True)
364def circular_ladder_graph(n, create_using=None):
365 """Returns the circular ladder graph $CL_n$ of length n.
367 $CL_n$ consists of two concentric n-cycles in which
368 each of the n pairs of concentric nodes are joined by an edge.
370 Node labels are the integers 0 to n-1
372 .. plot::
374 >>> nx.draw(nx.circular_ladder_graph(5))
376 """
377 G = ladder_graph(n, create_using)
378 G.add_edge(0, n - 1)
379 G.add_edge(n, 2 * n - 1)
380 return G
383@nx._dispatchable(graphs=None, returns_graph=True)
384def circulant_graph(n, offsets, create_using=None):
385 r"""Returns the circulant graph $Ci_n(x_1, x_2, ..., x_m)$ with $n$ nodes.
387 The circulant graph $Ci_n(x_1, ..., x_m)$ consists of $n$ nodes $0, ..., n-1$
388 such that node $i$ is connected to nodes $(i + x) \mod n$ and $(i - x) \mod n$
389 for all $x$ in $x_1, ..., x_m$. Thus $Ci_n(1)$ is a cycle graph.
391 .. plot::
393 >>> nx.draw(nx.circulant_graph(10, [1]))
395 Parameters
396 ----------
397 n : integer
398 The number of nodes in the graph.
399 offsets : list of integers
400 A list of node offsets, $x_1$ up to $x_m$, as described above.
401 create_using : NetworkX graph constructor, optional (default=nx.Graph)
402 Graph type to create. If graph instance, then cleared before populated.
404 Returns
405 -------
406 NetworkX Graph of type create_using
408 Examples
409 --------
410 Many well-known graph families are subfamilies of the circulant graphs;
411 for example, to create the cycle graph on n points, we connect every
412 node to nodes on either side (with offset plus or minus one). For n = 10,
414 >>> G = nx.circulant_graph(10, [1])
415 >>> edges = [
416 ... (0, 9),
417 ... (0, 1),
418 ... (1, 2),
419 ... (2, 3),
420 ... (3, 4),
421 ... (4, 5),
422 ... (5, 6),
423 ... (6, 7),
424 ... (7, 8),
425 ... (8, 9),
426 ... ]
427 >>> sorted(edges) == sorted(G.edges())
428 True
430 Similarly, we can create the complete graph
431 on 5 points with the set of offsets [1, 2]:
433 >>> G = nx.circulant_graph(5, [1, 2])
434 >>> edges = [
435 ... (0, 1),
436 ... (0, 2),
437 ... (0, 3),
438 ... (0, 4),
439 ... (1, 2),
440 ... (1, 3),
441 ... (1, 4),
442 ... (2, 3),
443 ... (2, 4),
444 ... (3, 4),
445 ... ]
446 >>> sorted(edges) == sorted(G.edges())
447 True
449 """
450 G = empty_graph(n, create_using)
451 G.add_edges_from((i, (i - j) % n) for i in range(n) for j in offsets)
452 G.add_edges_from((i, (i + j) % n) for i in range(n) for j in offsets)
453 return G
456@nx._dispatchable(graphs=None, returns_graph=True)
457@nodes_or_number(0)
458def cycle_graph(n, create_using=None):
459 """Returns the cycle graph $C_n$ of cyclically connected nodes.
461 $C_n$ is a path with its two end-nodes connected.
463 .. plot::
465 >>> nx.draw(nx.cycle_graph(5))
467 Parameters
468 ----------
469 n : int or iterable container of nodes
470 If n is an integer, nodes are from `range(n)`.
471 If n is a container of nodes, those nodes appear in the graph.
472 Warning: n is not checked for duplicates and if present the
473 resulting graph may not be as desired. Make sure you have no duplicates.
474 create_using : NetworkX graph constructor, optional (default=nx.Graph)
475 Graph type to create. If graph instance, then cleared before populated.
477 Notes
478 -----
479 If create_using is directed, the direction is in increasing order.
481 """
482 _, nodes = n
483 G = empty_graph(nodes, create_using)
484 G.add_edges_from(pairwise(nodes, cyclic=True))
485 return G
488@nx._dispatchable(graphs=None, returns_graph=True)
489def dorogovtsev_goltsev_mendes_graph(n, create_using=None):
490 """Returns the hierarchically constructed Dorogovtsev--Goltsev--Mendes graph.
492 The Dorogovtsev--Goltsev--Mendes [1]_ procedure deterministically produces a
493 scale-free graph with ``3/2 * (3**(n-1) + 1)`` nodes
494 and ``3**n`` edges for a given `n`.
496 Note that `n` denotes the number of times the state transition is applied,
497 starting from the base graph with ``n = 0`` (no transitions), as in [2]_.
498 This is different from the parameter ``t = n - 1`` in [1]_.
500 .. plot::
502 >>> nx.draw(nx.dorogovtsev_goltsev_mendes_graph(3))
504 Parameters
505 ----------
506 n : integer
507 The generation number.
509 create_using : NetworkX graph constructor, optional (default=nx.Graph)
510 Graph type to create. Directed graphs and multigraphs are not supported.
512 Returns
513 -------
514 G : NetworkX `Graph`
516 Raises
517 ------
518 NetworkXError
519 If `n` is less than zero.
521 If `create_using` is a directed graph or multigraph.
523 Examples
524 --------
525 >>> G = nx.dorogovtsev_goltsev_mendes_graph(3)
526 >>> G.number_of_nodes()
527 15
528 >>> G.number_of_edges()
529 27
530 >>> nx.is_planar(G)
531 True
533 References
534 ----------
535 .. [1] S. N. Dorogovtsev, A. V. Goltsev and J. F. F. Mendes,
536 "Pseudofractal scale-free web", Physical Review E 65, 066122, 2002.
537 https://arxiv.org/pdf/cond-mat/0112143.pdf
538 .. [2] Weisstein, Eric W. "Dorogovtsev--Goltsev--Mendes Graph".
539 From MathWorld--A Wolfram Web Resource.
540 https://mathworld.wolfram.com/Dorogovtsev-Goltsev-MendesGraph.html
541 """
542 if n < 0:
543 raise NetworkXError("n must be greater than or equal to 0")
545 G = empty_graph(0, create_using)
546 if G.is_directed():
547 raise NetworkXError("directed graph not supported")
548 if G.is_multigraph():
549 raise NetworkXError("multigraph not supported")
551 G.add_edge(0, 1)
552 new_node = 2 # next node to be added
553 for _ in range(n): # iterate over number of generations.
554 new_edges = []
555 for u, v in G.edges():
556 new_edges.append((u, new_node))
557 new_edges.append((v, new_node))
558 new_node += 1
560 G.add_edges_from(new_edges)
561 return G
564@nx._dispatchable(graphs=None, returns_graph=True)
565@nodes_or_number(0)
566def empty_graph(n=0, create_using=None, default=Graph):
567 """Returns the empty graph with n nodes and zero edges.
569 .. plot::
571 >>> nx.draw(nx.empty_graph(5))
573 Parameters
574 ----------
575 n : int or iterable container of nodes (default = 0)
576 If n is an integer, nodes are from `range(n)`.
577 If n is a container of nodes, those nodes appear in the graph.
578 create_using : Graph Instance, Constructor or None
579 Indicator of type of graph to return.
580 If a Graph-type instance, then clear and use it.
581 If None, use the `default` constructor.
582 If a constructor, call it to create an empty graph.
583 default : Graph constructor (optional, default = nx.Graph)
584 The constructor to use if create_using is None.
585 If None, then nx.Graph is used.
586 This is used when passing an unknown `create_using` value
587 through your home-grown function to `empty_graph` and
588 you want a default constructor other than nx.Graph.
590 Examples
591 --------
592 >>> G = nx.empty_graph(10)
593 >>> G.number_of_nodes()
594 10
595 >>> G.number_of_edges()
596 0
597 >>> G = nx.empty_graph("ABC")
598 >>> G.number_of_nodes()
599 3
600 >>> sorted(G)
601 ['A', 'B', 'C']
603 Notes
604 -----
605 The variable create_using should be a Graph Constructor or a
606 "graph"-like object. Constructors, e.g. `nx.Graph` or `nx.MultiGraph`
607 will be used to create the returned graph. "graph"-like objects
608 will be cleared (nodes and edges will be removed) and refitted as
609 an empty "graph" with nodes specified in n. This capability
610 is useful for specifying the class-nature of the resulting empty
611 "graph" (i.e. Graph, DiGraph, MyWeirdGraphClass, etc.).
613 The variable create_using has three main uses:
614 Firstly, the variable create_using can be used to create an
615 empty digraph, multigraph, etc. For example,
617 >>> n = 10
618 >>> G = nx.empty_graph(n, create_using=nx.DiGraph)
620 will create an empty digraph on n nodes.
622 Secondly, one can pass an existing graph (digraph, multigraph,
623 etc.) via create_using. For example, if G is an existing graph
624 (resp. digraph, multigraph, etc.), then empty_graph(n, create_using=G)
625 will empty G (i.e. delete all nodes and edges using G.clear())
626 and then add n nodes and zero edges, and return the modified graph.
628 Thirdly, when constructing your home-grown graph creation function
629 you can use empty_graph to construct the graph by passing a user
630 defined create_using to empty_graph. In this case, if you want the
631 default constructor to be other than nx.Graph, specify `default`.
633 >>> def mygraph(n, create_using=None):
634 ... G = nx.empty_graph(n, create_using, nx.MultiGraph)
635 ... G.add_edges_from([(0, 1), (0, 1)])
636 ... return G
637 >>> G = mygraph(3)
638 >>> G.is_multigraph()
639 True
640 >>> G = mygraph(3, nx.Graph)
641 >>> G.is_multigraph()
642 False
644 See also create_empty_copy(G).
646 """
647 if create_using is None:
648 G = default()
649 elif isinstance(create_using, type):
650 G = create_using()
651 elif not hasattr(create_using, "adj"):
652 raise TypeError("create_using is not a valid NetworkX graph type or instance")
653 else:
654 # create_using is a NetworkX style Graph
655 create_using.clear()
656 G = create_using
658 _, nodes = n
659 G.add_nodes_from(nodes)
660 return G
663@nx._dispatchable(graphs=None, returns_graph=True)
664def ladder_graph(n, create_using=None):
665 """Returns the Ladder graph of length n.
667 This is two paths of n nodes, with
668 each pair connected by a single edge.
670 Node labels are the integers 0 to 2*n - 1.
672 .. plot::
674 >>> nx.draw(nx.ladder_graph(5))
676 """
677 G = empty_graph(2 * n, create_using)
678 if G.is_directed():
679 raise NetworkXError("Directed Graph not supported")
680 G.add_edges_from(pairwise(range(n)))
681 G.add_edges_from(pairwise(range(n, 2 * n)))
682 G.add_edges_from((v, v + n) for v in range(n))
683 return G
686@nx._dispatchable(graphs=None, returns_graph=True)
687@nodes_or_number([0, 1])
688def lollipop_graph(m, n, create_using=None):
689 """Returns the Lollipop Graph; ``K_m`` connected to ``P_n``.
691 This is the Barbell Graph without the right barbell.
693 .. plot::
695 >>> nx.draw(nx.lollipop_graph(3, 4))
697 Parameters
698 ----------
699 m, n : int or iterable container of nodes
700 If an integer, nodes are from ``range(m)`` and ``range(m, m+n)``.
701 If a container of nodes, those nodes appear in the graph.
702 Warning: `m` and `n` are not checked for duplicates and if present the
703 resulting graph may not be as desired. Make sure you have no duplicates.
705 The nodes for `m` appear in the complete graph $K_m$ and the nodes
706 for `n` appear in the path $P_n$
707 create_using : NetworkX graph constructor, optional (default=nx.Graph)
708 Graph type to create. If graph instance, then cleared before populated.
710 Returns
711 -------
712 Networkx graph
713 A complete graph with `m` nodes connected to a path of length `n`.
715 Notes
716 -----
717 The 2 subgraphs are joined via an edge ``(m-1, m)``.
718 If ``n=0``, this is merely a complete graph.
720 (This graph is an extremal example in David Aldous and Jim
721 Fill's etext on Random Walks on Graphs.)
723 """
724 m, m_nodes = m
725 M = len(m_nodes)
726 if M < 2:
727 raise NetworkXError("Invalid description: m should indicate at least 2 nodes")
729 n, n_nodes = n
730 if isinstance(m, numbers.Integral) and isinstance(n, numbers.Integral):
731 n_nodes = list(range(M, M + n))
732 N = len(n_nodes)
734 # the ball
735 G = complete_graph(m_nodes, create_using)
736 if G.is_directed():
737 raise NetworkXError("Directed Graph not supported")
739 # the stick
740 G.add_nodes_from(n_nodes)
741 if N > 1:
742 G.add_edges_from(pairwise(n_nodes))
744 if len(G) != M + N:
745 raise NetworkXError("Nodes must be distinct in containers m and n")
747 # connect ball to stick
748 if M > 0 and N > 0:
749 G.add_edge(m_nodes[-1], n_nodes[0])
750 return G
753@nx._dispatchable(graphs=None, returns_graph=True)
754def null_graph(create_using=None):
755 """Returns the Null graph with no nodes or edges.
757 See empty_graph for the use of create_using.
759 """
760 G = empty_graph(0, create_using)
761 return G
764@nx._dispatchable(graphs=None, returns_graph=True)
765@nodes_or_number(0)
766def path_graph(n, create_using=None):
767 """Returns the Path graph `P_n` of linearly connected nodes.
769 .. plot::
771 >>> nx.draw(nx.path_graph(5))
773 Parameters
774 ----------
775 n : int or iterable
776 If an integer, nodes are 0 to n - 1.
777 If an iterable of nodes, in the order they appear in the path.
778 Warning: n is not checked for duplicates and if present the
779 resulting graph may not be as desired. Make sure you have no duplicates.
780 create_using : NetworkX graph constructor, optional (default=nx.Graph)
781 Graph type to create. If graph instance, then cleared before populated.
783 """
784 _, nodes = n
785 G = empty_graph(nodes, create_using)
786 G.add_edges_from(pairwise(nodes))
787 return G
790@nx._dispatchable(graphs=None, returns_graph=True)
791@nodes_or_number(0)
792def star_graph(n, create_using=None):
793 """Return a star graph.
795 The star graph consists of one center node connected to `n` outer nodes.
797 .. plot::
799 >>> nx.draw(nx.star_graph(6))
801 Parameters
802 ----------
803 n : int or iterable
804 If an integer, node labels are ``0`` to `n`, with center ``0``.
805 If an iterable of nodes, the center is the first.
806 Warning: `n` is not checked for duplicates and if present, the
807 resulting graph may not be as desired. Make sure you have no duplicates.
808 create_using : NetworkX graph constructor, optional (default=nx.Graph)
809 Graph type to create. If graph instance, then cleared before populated.
811 Examples
812 --------
813 A star graph with 3 spokes can be generated with
815 >>> G = nx.star_graph(3)
816 >>> sorted(G.edges)
817 [(0, 1), (0, 2), (0, 3)]
819 For directed graphs, the convention is to have edges pointing from the hub
820 to the spokes:
822 >>> DG1 = nx.star_graph(3, create_using=nx.DiGraph)
823 >>> sorted(DG1.edges)
824 [(0, 1), (0, 2), (0, 3)]
826 Other possible definitions have edges pointing from the spokes to the hub:
828 >>> DG2 = nx.star_graph(3, create_using=nx.DiGraph).reverse()
829 >>> sorted(DG2.edges)
830 [(1, 0), (2, 0), (3, 0)]
832 or have bidirectional edges:
834 >>> DG3 = nx.star_graph(3).to_directed()
835 >>> sorted(DG3.edges)
836 [(0, 1), (0, 2), (0, 3), (1, 0), (2, 0), (3, 0)]
838 Notes
839 -----
840 The graph has ``n + 1`` nodes for integer `n`.
841 So ``star_graph(3)`` is the same as ``star_graph(range(4))``.
842 """
843 n, nodes = n
844 if isinstance(n, numbers.Integral):
845 nodes.append(int(n)) # There should be n + 1 nodes.
846 G = empty_graph(nodes, create_using)
848 if len(nodes) > 1:
849 hub, *spokes = nodes
850 G.add_edges_from((hub, node) for node in spokes)
851 return G
854@nx._dispatchable(graphs=None, returns_graph=True)
855@nodes_or_number([0, 1])
856def tadpole_graph(m, n, create_using=None):
857 """Returns the (m,n)-tadpole graph; ``C_m`` connected to ``P_n``.
859 This graph on m+n nodes connects a cycle of size `m` to a path of length `n`.
860 It looks like a tadpole. It is also called a kite graph or a dragon graph.
862 .. plot::
864 >>> nx.draw(nx.tadpole_graph(3, 5))
866 Parameters
867 ----------
868 m, n : int or iterable container of nodes
869 If an integer, nodes are from ``range(m)`` and ``range(m,m+n)``.
870 If a container of nodes, those nodes appear in the graph.
871 Warning: `m` and `n` are not checked for duplicates and if present the
872 resulting graph may not be as desired.
874 The nodes for `m` appear in the cycle graph $C_m$ and the nodes
875 for `n` appear in the path $P_n$.
876 create_using : NetworkX graph constructor, optional (default=nx.Graph)
877 Graph type to create. If graph instance, then cleared before populated.
879 Returns
880 -------
881 Networkx graph
882 A cycle of size `m` connected to a path of length `n`.
884 Raises
885 ------
886 NetworkXError
887 If ``m < 2``. The tadpole graph is undefined for ``m<2``.
889 Notes
890 -----
891 The 2 subgraphs are joined via an edge ``(m-1, m)``.
892 If ``n=0``, this is a cycle graph.
893 `m` and/or `n` can be a container of nodes instead of an integer.
895 """
896 m, m_nodes = m
897 M = len(m_nodes)
898 if M < 2:
899 raise NetworkXError("Invalid description: m should indicate at least 2 nodes")
901 n, n_nodes = n
902 if isinstance(m, numbers.Integral) and isinstance(n, numbers.Integral):
903 n_nodes = list(range(M, M + n))
905 # the circle
906 G = cycle_graph(m_nodes, create_using)
907 if G.is_directed():
908 raise NetworkXError("Directed Graph not supported")
910 # the stick
911 nx.add_path(G, [m_nodes[-1]] + list(n_nodes))
913 return G
916@nx._dispatchable(graphs=None, returns_graph=True)
917def trivial_graph(create_using=None):
918 """Return the Trivial graph with one node (with label 0) and no edges.
920 .. plot::
922 >>> nx.draw(nx.trivial_graph(), with_labels=True)
924 """
925 G = empty_graph(1, create_using)
926 return G
929@nx._dispatchable(graphs=None, returns_graph=True)
930def turan_graph(n, r):
931 r"""Return the Turan Graph
933 The Turan Graph is a complete multipartite graph on $n$ nodes
934 with $r$ disjoint subsets. That is, edges connect each node to
935 every node not in its subset.
937 Given $n$ and $r$, we create a complete multipartite graph with
938 $r-(n \mod r)$ partitions of size $n/r$, rounded down, and
939 $n \mod r$ partitions of size $n/r+1$, rounded down.
941 .. plot::
943 >>> nx.draw(nx.turan_graph(6, 2))
945 Parameters
946 ----------
947 n : int
948 The number of nodes.
949 r : int
950 The number of partitions.
951 Must be less than or equal to n.
953 Notes
954 -----
955 Must satisfy $1 <= r <= n$.
956 The graph has $(r-1)(n^2)/(2r)$ edges, rounded down.
957 """
959 if not 1 <= r <= n:
960 raise NetworkXError("Must satisfy 1 <= r <= n")
962 partitions = [n // r] * (r - (n % r)) + [n // r + 1] * (n % r)
963 G = complete_multipartite_graph(*partitions)
964 return G
967@nx._dispatchable(graphs=None, returns_graph=True)
968@nodes_or_number(0)
969def wheel_graph(n, create_using=None):
970 """Return the wheel graph
972 The wheel graph consists of a hub node connected to a cycle of (n-1) nodes.
974 .. plot::
976 >>> nx.draw(nx.wheel_graph(5))
978 Parameters
979 ----------
980 n : int or iterable
981 If an integer, node labels are 0 to n with center 0.
982 If an iterable of nodes, the center is the first.
983 Warning: n is not checked for duplicates and if present the
984 resulting graph may not be as desired. Make sure you have no duplicates.
985 create_using : NetworkX graph constructor, optional (default=nx.Graph)
986 Graph type to create. If graph instance, then cleared before populated.
988 Node labels are the integers 0 to n - 1.
989 """
990 _, nodes = n
991 G = empty_graph(nodes, create_using)
992 if G.is_directed():
993 raise NetworkXError("Directed Graph not supported")
995 if len(nodes) > 1:
996 hub, *rim = nodes
997 G.add_edges_from((hub, node) for node in rim)
998 if len(rim) > 1:
999 G.add_edges_from(pairwise(rim, cyclic=True))
1000 return G
1003@nx._dispatchable(graphs=None, returns_graph=True)
1004def complete_multipartite_graph(*subset_sizes):
1005 """Returns the complete multipartite graph with the specified subset sizes.
1007 .. plot::
1009 >>> nx.draw(nx.complete_multipartite_graph(1, 2, 3))
1011 Parameters
1012 ----------
1013 subset_sizes : tuple of integers or tuple of node iterables
1014 The arguments can either all be integer number of nodes or they
1015 can all be iterables of nodes. If integers, they represent the
1016 number of nodes in each subset of the multipartite graph.
1017 If iterables, each is used to create the nodes for that subset.
1018 The length of subset_sizes is the number of subsets.
1020 Returns
1021 -------
1022 G : NetworkX Graph
1023 Returns the complete multipartite graph with the specified subsets.
1025 For each node, the node attribute 'subset' is an integer
1026 indicating which subset contains the node.
1028 Examples
1029 --------
1030 Creating a complete tripartite graph, with subsets of one, two, and three
1031 nodes, respectively.
1033 >>> G = nx.complete_multipartite_graph(1, 2, 3)
1034 >>> [G.nodes[u]["subset"] for u in G]
1035 [0, 1, 1, 2, 2, 2]
1036 >>> list(G.edges(0))
1037 [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]
1038 >>> list(G.edges(2))
1039 [(2, 0), (2, 3), (2, 4), (2, 5)]
1040 >>> list(G.edges(4))
1041 [(4, 0), (4, 1), (4, 2)]
1043 >>> G = nx.complete_multipartite_graph("a", "bc", "def")
1044 >>> [G.nodes[u]["subset"] for u in sorted(G)]
1045 [0, 1, 1, 2, 2, 2]
1047 Notes
1048 -----
1049 This function generalizes several other graph builder functions.
1051 - If no subset sizes are given, this returns the null graph.
1052 - If a single subset size `n` is given, this returns the empty graph on
1053 `n` nodes.
1054 - If two subset sizes `m` and `n` are given, this returns the complete
1055 bipartite graph on `m + n` nodes.
1056 - If subset sizes `1` and `n` are given, this returns the star graph on
1057 `n + 1` nodes.
1059 See also
1060 --------
1061 complete_bipartite_graph
1062 """
1063 # The complete multipartite graph is an undirected simple graph.
1064 G = Graph()
1066 if len(subset_sizes) == 0:
1067 return G
1069 # set up subsets of nodes
1070 try:
1071 extents = pairwise(itertools.accumulate((0,) + subset_sizes))
1072 subsets = [range(start, end) for start, end in extents]
1073 except TypeError:
1074 subsets = subset_sizes
1075 else:
1076 if any(size < 0 for size in subset_sizes):
1077 raise NetworkXError(f"Negative number of nodes not valid: {subset_sizes}")
1079 # add nodes with subset attribute
1080 # while checking that ints are not mixed with iterables
1081 try:
1082 for i, subset in enumerate(subsets):
1083 G.add_nodes_from(subset, subset=i)
1084 except TypeError as err:
1085 raise NetworkXError("Arguments must be all ints or all iterables") from err
1087 # Across subsets, all nodes should be adjacent.
1088 # We can use itertools.combinations() because undirected.
1089 for subset1, subset2 in itertools.combinations(subsets, 2):
1090 G.add_edges_from(itertools.product(subset1, subset2))
1091 return G