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 Parameters
377 ----------
378 n : int
379 The length of the ladder. Must be at least 2.
380 create_using : NetworkX graph constructor, optional (default=nx.Graph)
381 Graph type to create. If graph instance, then cleared before populated.
383 Returns
384 -------
385 G : Graph
386 A circular ladder graph.
388 Raises
389 ------
390 ValueError
391 If `n` is less than 2.
392 NetworkXError
393 If `create_using` is a directed graph.
395 """
396 if n < 2:
397 raise ValueError("n must be at least 2 for circular_ladder_graph")
398 G = ladder_graph(n, create_using)
399 G.add_edge(0, n - 1)
400 G.add_edge(n, 2 * n - 1)
401 return G
404@nx._dispatchable(graphs=None, returns_graph=True)
405def circulant_graph(n, offsets, create_using=None):
406 r"""Returns the circulant graph $Ci_n(x_1, x_2, ..., x_m)$ with $n$ nodes.
408 The circulant graph $Ci_n(x_1, ..., x_m)$ consists of $n$ nodes $0, ..., n-1$
409 such that node $i$ is connected to nodes $(i + x) \mod n$ and $(i - x) \mod n$
410 for all $x$ in $x_1, ..., x_m$. Thus $Ci_n(1)$ is a cycle graph.
412 .. plot::
414 >>> nx.draw(nx.circulant_graph(10, [1]))
416 Parameters
417 ----------
418 n : integer
419 The number of nodes in the graph.
420 offsets : list of integers
421 A list of node offsets, $x_1$ up to $x_m$, as described above.
422 create_using : NetworkX graph constructor, optional (default=nx.Graph)
423 Graph type to create. If graph instance, then cleared before populated.
425 Returns
426 -------
427 NetworkX Graph of type create_using
429 Examples
430 --------
431 Many well-known graph families are subfamilies of the circulant graphs;
432 for example, to create the cycle graph on n points, we connect every
433 node to nodes on either side (with offset plus or minus one). For n = 10,
435 >>> G = nx.circulant_graph(10, [1])
436 >>> edges = [
437 ... (0, 9),
438 ... (0, 1),
439 ... (1, 2),
440 ... (2, 3),
441 ... (3, 4),
442 ... (4, 5),
443 ... (5, 6),
444 ... (6, 7),
445 ... (7, 8),
446 ... (8, 9),
447 ... ]
448 >>> sorted(edges) == sorted(G.edges())
449 True
451 Similarly, we can create the complete graph
452 on 5 points with the set of offsets [1, 2]:
454 >>> G = nx.circulant_graph(5, [1, 2])
455 >>> edges = [
456 ... (0, 1),
457 ... (0, 2),
458 ... (0, 3),
459 ... (0, 4),
460 ... (1, 2),
461 ... (1, 3),
462 ... (1, 4),
463 ... (2, 3),
464 ... (2, 4),
465 ... (3, 4),
466 ... ]
467 >>> sorted(edges) == sorted(G.edges())
468 True
470 """
471 G = empty_graph(n, create_using)
472 G.add_edges_from((i, (i - j) % n) for i in range(n) for j in offsets)
473 G.add_edges_from((i, (i + j) % n) for i in range(n) for j in offsets)
474 return G
477@nx._dispatchable(graphs=None, returns_graph=True)
478@nodes_or_number(0)
479def cycle_graph(n, create_using=None):
480 """Returns the cycle graph $C_n$ of cyclically connected nodes.
482 $C_n$ is a path with its two end-nodes connected.
484 .. plot::
486 >>> nx.draw(nx.cycle_graph(5))
488 Parameters
489 ----------
490 n : int or iterable container of nodes
491 If n is an integer, nodes are from `range(n)`.
492 If n is a container of nodes, those nodes appear in the graph.
493 Warning: n is not checked for duplicates and if present the
494 resulting graph may not be as desired. Make sure you have no duplicates.
495 create_using : NetworkX graph constructor, optional (default=nx.Graph)
496 Graph type to create. If graph instance, then cleared before populated.
498 Notes
499 -----
500 If create_using is directed, the direction is in increasing order.
502 """
503 _, nodes = n
504 G = empty_graph(nodes, create_using)
505 G.add_edges_from(pairwise(nodes, cyclic=True))
506 return G
509@nx._dispatchable(graphs=None, returns_graph=True)
510def dorogovtsev_goltsev_mendes_graph(n, create_using=None):
511 """Returns the hierarchically constructed Dorogovtsev--Goltsev--Mendes graph.
513 The Dorogovtsev--Goltsev--Mendes [1]_ procedure deterministically produces a
514 scale-free graph with ``3/2 * (3**(n-1) + 1)`` nodes
515 and ``3**n`` edges for a given `n`.
517 Note that `n` denotes the number of times the state transition is applied,
518 starting from the base graph with ``n = 0`` (no transitions), as in [2]_.
519 This is different from the parameter ``t = n - 1`` in [1]_.
521 .. plot::
523 >>> nx.draw(nx.dorogovtsev_goltsev_mendes_graph(3))
525 Parameters
526 ----------
527 n : integer
528 The generation number.
530 create_using : NetworkX graph constructor, optional (default=nx.Graph)
531 Graph type to create. Directed graphs and multigraphs are not supported.
533 Returns
534 -------
535 G : NetworkX `Graph`
537 Raises
538 ------
539 NetworkXError
540 If `n` is less than zero.
542 If `create_using` is a directed graph or multigraph.
544 Examples
545 --------
546 >>> G = nx.dorogovtsev_goltsev_mendes_graph(3)
547 >>> G.number_of_nodes()
548 15
549 >>> G.number_of_edges()
550 27
551 >>> nx.is_planar(G)
552 True
554 References
555 ----------
556 .. [1] S. N. Dorogovtsev, A. V. Goltsev and J. F. F. Mendes,
557 "Pseudofractal scale-free web", Physical Review E 65, 066122, 2002.
558 https://arxiv.org/pdf/cond-mat/0112143.pdf
559 .. [2] Weisstein, Eric W. "Dorogovtsev--Goltsev--Mendes Graph".
560 From MathWorld--A Wolfram Web Resource.
561 https://mathworld.wolfram.com/Dorogovtsev-Goltsev-MendesGraph.html
562 """
563 if n < 0:
564 raise NetworkXError("n must be greater than or equal to 0")
566 G = empty_graph(0, create_using)
567 if G.is_directed():
568 raise NetworkXError("directed graph not supported")
569 if G.is_multigraph():
570 raise NetworkXError("multigraph not supported")
572 G.add_edge(0, 1)
573 new_node = 2 # next node to be added
574 for _ in range(n): # iterate over number of generations.
575 new_edges = []
576 for u, v in G.edges():
577 new_edges.append((u, new_node))
578 new_edges.append((v, new_node))
579 new_node += 1
581 G.add_edges_from(new_edges)
582 return G
585@nx._dispatchable(graphs=None, returns_graph=True)
586@nodes_or_number(0)
587def empty_graph(n=0, create_using=None, default=Graph):
588 """Returns the empty graph with n nodes and zero edges.
590 .. plot::
592 >>> nx.draw(nx.empty_graph(5))
594 Parameters
595 ----------
596 n : int or iterable container of nodes (default = 0)
597 If n is an integer, nodes are from `range(n)`.
598 If n is a container of nodes, those nodes appear in the graph.
599 create_using : Graph Instance, Constructor or None
600 Indicator of type of graph to return.
601 If a Graph-type instance, then clear and use it.
602 If None, use the `default` constructor.
603 If a constructor, call it to create an empty graph.
604 default : Graph constructor (optional, default = nx.Graph)
605 The constructor to use if create_using is None.
606 If None, then nx.Graph is used.
607 This is used when passing an unknown `create_using` value
608 through your home-grown function to `empty_graph` and
609 you want a default constructor other than nx.Graph.
611 Examples
612 --------
613 >>> G = nx.empty_graph(10)
614 >>> G.number_of_nodes()
615 10
616 >>> G.number_of_edges()
617 0
618 >>> G = nx.empty_graph("ABC")
619 >>> G.number_of_nodes()
620 3
621 >>> sorted(G)
622 ['A', 'B', 'C']
624 Notes
625 -----
626 The variable create_using should be a Graph Constructor or a
627 "graph"-like object. Constructors, e.g. `nx.Graph` or `nx.MultiGraph`
628 will be used to create the returned graph. "graph"-like objects
629 will be cleared (nodes and edges will be removed) and refitted as
630 an empty "graph" with nodes specified in n. This capability
631 is useful for specifying the class-nature of the resulting empty
632 "graph" (i.e. Graph, DiGraph, MyWeirdGraphClass, etc.).
634 The variable create_using has three main uses:
635 Firstly, the variable create_using can be used to create an
636 empty digraph, multigraph, etc. For example,
638 >>> n = 10
639 >>> G = nx.empty_graph(n, create_using=nx.DiGraph)
641 will create an empty digraph on n nodes.
643 Secondly, one can pass an existing graph (digraph, multigraph,
644 etc.) via create_using. For example, if G is an existing graph
645 (resp. digraph, multigraph, etc.), then empty_graph(n, create_using=G)
646 will empty G (i.e. delete all nodes and edges using G.clear())
647 and then add n nodes and zero edges, and return the modified graph.
649 Thirdly, when constructing your home-grown graph creation function
650 you can use empty_graph to construct the graph by passing a user
651 defined create_using to empty_graph. In this case, if you want the
652 default constructor to be other than nx.Graph, specify `default`.
654 >>> def mygraph(n, create_using=None):
655 ... G = nx.empty_graph(n, create_using, nx.MultiGraph)
656 ... G.add_edges_from([(0, 1), (0, 1)])
657 ... return G
658 >>> G = mygraph(3)
659 >>> G.is_multigraph()
660 True
661 >>> G = mygraph(3, nx.Graph)
662 >>> G.is_multigraph()
663 False
665 See also create_empty_copy(G).
667 """
668 if create_using is None:
669 G = default()
670 elif isinstance(create_using, type):
671 G = create_using()
672 elif not hasattr(create_using, "adj"):
673 raise TypeError("create_using is not a valid NetworkX graph type or instance")
674 else:
675 # create_using is a NetworkX style Graph
676 create_using.clear()
677 G = create_using
679 _, nodes = n
680 G.add_nodes_from(nodes)
681 return G
684@nx._dispatchable(graphs=None, returns_graph=True)
685def ladder_graph(n, create_using=None):
686 """Returns the Ladder graph of length n.
688 This is two paths of n nodes, with
689 each pair connected by a single edge.
691 Node labels are the integers 0 to 2*n - 1.
693 .. plot::
695 >>> nx.draw(nx.ladder_graph(5))
697 """
698 G = empty_graph(2 * n, create_using)
699 if G.is_directed():
700 raise NetworkXError("Directed Graph not supported")
701 G.add_edges_from(pairwise(range(n)))
702 G.add_edges_from(pairwise(range(n, 2 * n)))
703 G.add_edges_from((v, v + n) for v in range(n))
704 return G
707@nx._dispatchable(graphs=None, returns_graph=True)
708@nodes_or_number([0, 1])
709def lollipop_graph(m, n, create_using=None):
710 """Returns the Lollipop Graph; ``K_m`` connected to ``P_n``.
712 This is the Barbell Graph without the right barbell.
714 .. plot::
716 >>> nx.draw(nx.lollipop_graph(3, 4))
718 Parameters
719 ----------
720 m, n : int or iterable container of nodes
721 If an integer, nodes are from ``range(m)`` and ``range(m, m+n)``.
722 If a container of nodes, those nodes appear in the graph.
723 Warning: `m` and `n` are not checked for duplicates and if present the
724 resulting graph may not be as desired. Make sure you have no duplicates.
726 The nodes for `m` appear in the complete graph $K_m$ and the nodes
727 for `n` appear in the path $P_n$
728 create_using : NetworkX graph constructor, optional (default=nx.Graph)
729 Graph type to create. If graph instance, then cleared before populated.
731 Returns
732 -------
733 Networkx graph
734 A complete graph with `m` nodes connected to a path of length `n`.
736 Notes
737 -----
738 The 2 subgraphs are joined via an edge ``(m-1, m)``.
739 If ``n=0``, this is merely a complete graph.
741 (This graph is an extremal example in David Aldous and Jim
742 Fill's etext on Random Walks on Graphs.)
744 """
745 m, m_nodes = m
746 M = len(m_nodes)
747 if M < 2:
748 raise NetworkXError("Invalid description: m should indicate at least 2 nodes")
750 n, n_nodes = n
751 if isinstance(m, numbers.Integral) and isinstance(n, numbers.Integral):
752 n_nodes = list(range(M, M + n))
753 N = len(n_nodes)
755 # the ball
756 G = complete_graph(m_nodes, create_using)
757 if G.is_directed():
758 raise NetworkXError("Directed Graph not supported")
760 # the stick
761 G.add_nodes_from(n_nodes)
762 if N > 1:
763 G.add_edges_from(pairwise(n_nodes))
765 if len(G) != M + N:
766 raise NetworkXError("Nodes must be distinct in containers m and n")
768 # connect ball to stick
769 if M > 0 and N > 0:
770 G.add_edge(m_nodes[-1], n_nodes[0])
771 return G
774@nx._dispatchable(graphs=None, returns_graph=True)
775def null_graph(create_using=None):
776 """Returns the Null graph with no nodes or edges.
778 See empty_graph for the use of create_using.
780 """
781 G = empty_graph(0, create_using)
782 return G
785@nx._dispatchable(graphs=None, returns_graph=True)
786@nodes_or_number(0)
787def path_graph(n, create_using=None):
788 """Returns the Path graph `P_n` of linearly connected nodes.
790 .. plot::
792 >>> nx.draw(nx.path_graph(5))
794 Parameters
795 ----------
796 n : int or iterable
797 If an integer, nodes are 0 to n - 1.
798 If an iterable of nodes, in the order they appear in the path.
799 Warning: n is not checked for duplicates and if present the
800 resulting graph may not be as desired. Make sure you have no duplicates.
801 create_using : NetworkX graph constructor, optional (default=nx.Graph)
802 Graph type to create. If graph instance, then cleared before populated.
804 """
805 _, nodes = n
806 G = empty_graph(nodes, create_using)
807 G.add_edges_from(pairwise(nodes))
808 return G
811@nx._dispatchable(graphs=None, returns_graph=True)
812@nodes_or_number(0)
813def star_graph(n, create_using=None):
814 """Return a star graph.
816 The star graph consists of one center node connected to `n` outer nodes.
818 .. plot::
820 >>> nx.draw(nx.star_graph(6))
822 Parameters
823 ----------
824 n : int or iterable
825 If an integer, node labels are ``0`` to `n`, with center ``0``.
826 If an iterable of nodes, the center is the first.
827 Warning: `n` is not checked for duplicates and if present, the
828 resulting graph may not be as desired. Make sure you have no duplicates.
829 create_using : NetworkX graph constructor, optional (default=nx.Graph)
830 Graph type to create. If graph instance, then cleared before populated.
832 Examples
833 --------
834 A star graph with 3 spokes can be generated with
836 >>> G = nx.star_graph(3)
837 >>> sorted(G.edges)
838 [(0, 1), (0, 2), (0, 3)]
840 For directed graphs, the convention is to have edges pointing from the hub
841 to the spokes:
843 >>> DG1 = nx.star_graph(3, create_using=nx.DiGraph)
844 >>> sorted(DG1.edges)
845 [(0, 1), (0, 2), (0, 3)]
847 Other possible definitions have edges pointing from the spokes to the hub:
849 >>> DG2 = nx.star_graph(3, create_using=nx.DiGraph).reverse()
850 >>> sorted(DG2.edges)
851 [(1, 0), (2, 0), (3, 0)]
853 or have bidirectional edges:
855 >>> DG3 = nx.star_graph(3).to_directed()
856 >>> sorted(DG3.edges)
857 [(0, 1), (0, 2), (0, 3), (1, 0), (2, 0), (3, 0)]
859 Notes
860 -----
861 The graph has ``n + 1`` nodes for integer `n`.
862 So ``star_graph(3)`` is the same as ``star_graph(range(4))``.
863 """
864 n, nodes = n
865 if isinstance(n, numbers.Integral):
866 nodes.append(int(n)) # There should be n + 1 nodes.
867 G = empty_graph(nodes, create_using)
869 if len(nodes) > 1:
870 hub, *spokes = nodes
871 G.add_edges_from((hub, node) for node in spokes)
872 return G
875@nx._dispatchable(graphs=None, returns_graph=True)
876@nodes_or_number([0, 1])
877def tadpole_graph(m, n, create_using=None):
878 """Returns the (m,n)-tadpole graph; ``C_m`` connected to ``P_n``.
880 This graph on m+n nodes connects a cycle of size `m` to a path of length `n`.
881 It looks like a tadpole. It is also called a kite graph or a dragon graph.
883 .. plot::
885 >>> nx.draw(nx.tadpole_graph(3, 5))
887 Parameters
888 ----------
889 m, n : int or iterable container of nodes
890 If an integer, nodes are from ``range(m)`` and ``range(m,m+n)``.
891 If a container of nodes, those nodes appear in the graph.
892 Warning: `m` and `n` are not checked for duplicates and if present the
893 resulting graph may not be as desired.
895 The nodes for `m` appear in the cycle graph $C_m$ and the nodes
896 for `n` appear in the path $P_n$.
897 create_using : NetworkX graph constructor, optional (default=nx.Graph)
898 Graph type to create. If graph instance, then cleared before populated.
900 Returns
901 -------
902 Networkx graph
903 A cycle of size `m` connected to a path of length `n`.
905 Raises
906 ------
907 NetworkXError
908 If ``m < 2``. The tadpole graph is undefined for ``m<2``.
910 Notes
911 -----
912 The 2 subgraphs are joined via an edge ``(m-1, m)``.
913 If ``n=0``, this is a cycle graph.
914 `m` and/or `n` can be a container of nodes instead of an integer.
916 """
917 m, m_nodes = m
918 M = len(m_nodes)
919 if M < 2:
920 raise NetworkXError("Invalid description: m should indicate at least 2 nodes")
922 n, n_nodes = n
923 if isinstance(m, numbers.Integral) and isinstance(n, numbers.Integral):
924 n_nodes = list(range(M, M + n))
926 # the circle
927 G = cycle_graph(m_nodes, create_using)
928 if G.is_directed():
929 raise NetworkXError("Directed Graph not supported")
931 # the stick
932 nx.add_path(G, [m_nodes[-1]] + list(n_nodes))
934 return G
937@nx._dispatchable(graphs=None, returns_graph=True)
938def trivial_graph(create_using=None):
939 """Return the Trivial graph with one node (with label 0) and no edges.
941 .. plot::
943 >>> nx.draw(nx.trivial_graph(), with_labels=True)
945 """
946 G = empty_graph(1, create_using)
947 return G
950@nx._dispatchable(graphs=None, returns_graph=True)
951def turan_graph(n, r):
952 r"""Return the Turan Graph
954 The Turan Graph is a complete multipartite graph on $n$ nodes
955 with $r$ disjoint subsets. That is, edges connect each node to
956 every node not in its subset.
958 Given $n$ and $r$, we create a complete multipartite graph with
959 $r-(n \mod r)$ partitions of size $n/r$, rounded down, and
960 $n \mod r$ partitions of size $n/r+1$, rounded down.
962 .. plot::
964 >>> nx.draw(nx.turan_graph(6, 2))
966 Parameters
967 ----------
968 n : int
969 The number of nodes.
970 r : int
971 The number of partitions.
972 Must be less than or equal to n.
974 Notes
975 -----
976 Must satisfy $1 <= r <= n$.
977 The graph has $(r-1)(n^2)/(2r)$ edges, rounded down.
978 """
980 if not 1 <= r <= n:
981 raise NetworkXError("Must satisfy 1 <= r <= n")
983 partitions = [n // r] * (r - (n % r)) + [n // r + 1] * (n % r)
984 G = complete_multipartite_graph(*partitions)
985 return G
988@nx._dispatchable(graphs=None, returns_graph=True)
989@nodes_or_number(0)
990def wheel_graph(n, create_using=None):
991 """Return the wheel graph
993 The wheel graph consists of a hub node connected to a cycle of (n-1) nodes.
995 .. plot::
997 >>> nx.draw(nx.wheel_graph(5))
999 Parameters
1000 ----------
1001 n : int or iterable
1002 If an integer, node labels are 0 to n with center 0.
1003 If an iterable of nodes, the center is the first.
1004 Warning: n is not checked for duplicates and if present the
1005 resulting graph may not be as desired. Make sure you have no duplicates.
1006 create_using : NetworkX graph constructor, optional (default=nx.Graph)
1007 Graph type to create. If graph instance, then cleared before populated.
1009 Node labels are the integers 0 to n - 1.
1010 """
1011 _, nodes = n
1012 G = empty_graph(nodes, create_using)
1013 if G.is_directed():
1014 raise NetworkXError("Directed Graph not supported")
1016 if len(nodes) > 1:
1017 hub, *rim = nodes
1018 G.add_edges_from((hub, node) for node in rim)
1019 if len(rim) > 1:
1020 G.add_edges_from(pairwise(rim, cyclic=True))
1021 return G
1024@nx._dispatchable(graphs=None, returns_graph=True)
1025def complete_multipartite_graph(*subset_sizes):
1026 """Returns the complete multipartite graph with the specified subset sizes.
1028 .. plot::
1030 >>> nx.draw(nx.complete_multipartite_graph(1, 2, 3))
1032 Parameters
1033 ----------
1034 subset_sizes : tuple of integers or tuple of node iterables
1035 The arguments can either all be integer number of nodes or they
1036 can all be iterables of nodes. If integers, they represent the
1037 number of nodes in each subset of the multipartite graph.
1038 If iterables, each is used to create the nodes for that subset.
1039 The length of subset_sizes is the number of subsets.
1041 Returns
1042 -------
1043 G : NetworkX Graph
1044 Returns the complete multipartite graph with the specified subsets.
1046 For each node, the node attribute 'subset' is an integer
1047 indicating which subset contains the node.
1049 Examples
1050 --------
1051 Creating a complete tripartite graph, with subsets of one, two, and three
1052 nodes, respectively.
1054 >>> G = nx.complete_multipartite_graph(1, 2, 3)
1055 >>> [G.nodes[u]["subset"] for u in G]
1056 [0, 1, 1, 2, 2, 2]
1057 >>> list(G.edges(0))
1058 [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]
1059 >>> list(G.edges(2))
1060 [(2, 0), (2, 3), (2, 4), (2, 5)]
1061 >>> list(G.edges(4))
1062 [(4, 0), (4, 1), (4, 2)]
1064 >>> G = nx.complete_multipartite_graph("a", "bc", "def")
1065 >>> [G.nodes[u]["subset"] for u in sorted(G)]
1066 [0, 1, 1, 2, 2, 2]
1068 Notes
1069 -----
1070 This function generalizes several other graph builder functions.
1072 - If no subset sizes are given, this returns the null graph.
1073 - If a single subset size `n` is given, this returns the empty graph on
1074 `n` nodes.
1075 - If two subset sizes `m` and `n` are given, this returns the complete
1076 bipartite graph on `m + n` nodes.
1077 - If subset sizes `1` and `n` are given, this returns the star graph on
1078 `n + 1` nodes.
1080 See also
1081 --------
1082 complete_bipartite_graph
1083 """
1084 # The complete multipartite graph is an undirected simple graph.
1085 G = Graph()
1087 if len(subset_sizes) == 0:
1088 return G
1090 # set up subsets of nodes
1091 try:
1092 extents = pairwise(itertools.accumulate((0,) + subset_sizes))
1093 subsets = [range(start, end) for start, end in extents]
1094 except TypeError:
1095 subsets = subset_sizes
1096 else:
1097 if any(size < 0 for size in subset_sizes):
1098 raise NetworkXError(f"Negative number of nodes not valid: {subset_sizes}")
1100 # add nodes with subset attribute
1101 # while checking that ints are not mixed with iterables
1102 try:
1103 for i, subset in enumerate(subsets):
1104 G.add_nodes_from(subset, subset=i)
1105 except TypeError as err:
1106 raise NetworkXError("Arguments must be all ints or all iterables") from err
1108 # Across subsets, all nodes should be adjacent.
1109 # We can use itertools.combinations() because undirected.
1110 for subset1, subset2 in itertools.combinations(subsets, 2):
1111 G.add_edges_from(itertools.product(subset1, subset2))
1112 return G