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"""
2Various small and named graphs, together with some compact generators.
4"""
6__all__ = [
7 "LCF_graph",
8 "bull_graph",
9 "chvatal_graph",
10 "cubical_graph",
11 "desargues_graph",
12 "diamond_graph",
13 "dodecahedral_graph",
14 "frucht_graph",
15 "generalized_petersen_graph",
16 "heawood_graph",
17 "hoffman_singleton_graph",
18 "house_graph",
19 "house_x_graph",
20 "icosahedral_graph",
21 "krackhardt_kite_graph",
22 "moebius_kantor_graph",
23 "octahedral_graph",
24 "pappus_graph",
25 "petersen_graph",
26 "sedgewick_maze_graph",
27 "tetrahedral_graph",
28 "truncated_cube_graph",
29 "truncated_tetrahedron_graph",
30 "tutte_graph",
31]
33from functools import wraps
35import networkx as nx
36from networkx.exception import NetworkXError
37from networkx.generators.classic import (
38 complete_graph,
39 cycle_graph,
40 empty_graph,
41 path_graph,
42)
45def _raise_on_directed(func):
46 """
47 A decorator which inspects the `create_using` argument and raises a
48 NetworkX exception when `create_using` is a DiGraph (class or instance) for
49 graph generators that do not support directed outputs.
51 `create_using` may be a keyword argument or the first positional argument.
52 """
54 @wraps(func)
55 def wrapper(*args, **kwargs):
56 create_using = args[0] if args else kwargs.get("create_using")
57 if create_using is not None:
58 G = nx.empty_graph(create_using=create_using)
59 if G.is_directed():
60 raise NetworkXError("Directed Graph not supported in create_using")
61 return func(*args, **kwargs)
63 return wrapper
66@nx._dispatchable(graphs=None, returns_graph=True)
67def LCF_graph(n, shift_list, repeats, create_using=None):
68 """
69 Return the cubic graph specified in LCF notation.
71 LCF (Lederberg-Coxeter-Fruchte) notation[1]_ is a compressed
72 notation used in the generation of various cubic Hamiltonian
73 graphs of high symmetry. See, for example, `dodecahedral_graph`,
74 `desargues_graph`, `heawood_graph` and `pappus_graph`.
76 Nodes are drawn from ``range(n)``. Each node ``n_i`` is connected with
77 node ``n_i + shift % n`` where ``shift`` is given by cycling through
78 the input `shift_list` `repeat` s times.
80 Parameters
81 ----------
82 n : int
83 The starting graph is the `n`-cycle with nodes ``0, ..., n-1``.
84 The null graph is returned if `n` < 1.
86 shift_list : list
87 A list of integer shifts mod `n`, ``[s1, s2, .., sk]``
89 repeats : int
90 Integer specifying the number of times that shifts in `shift_list`
91 are successively applied to each current node in the n-cycle
92 to generate an edge between ``n_current`` and ``n_current + shift mod n``.
94 Returns
95 -------
96 G : Graph
97 A graph instance created from the specified LCF notation.
99 Examples
100 --------
101 The utility graph $K_{3,3}$
103 >>> G = nx.LCF_graph(6, [3, -3], 3)
104 >>> G.edges()
105 EdgeView([(0, 1), (0, 5), (0, 3), (1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5)])
107 The Heawood graph:
109 >>> G = nx.LCF_graph(14, [5, -5], 7)
110 >>> nx.is_isomorphic(G, nx.heawood_graph())
111 True
113 References
114 ----------
115 .. [1] https://en.wikipedia.org/wiki/LCF_notation
117 """
118 if n <= 0:
119 return empty_graph(0, create_using)
121 # start with the n-cycle
122 G = cycle_graph(n, create_using)
123 if G.is_directed():
124 raise NetworkXError("Directed Graph not supported")
125 G.name = "LCF_graph"
126 nodes = sorted(G)
128 n_extra_edges = repeats * len(shift_list)
129 # edges are added n_extra_edges times
130 # (not all of these need be new)
131 if n_extra_edges < 1:
132 return G
134 for i in range(n_extra_edges):
135 shift = shift_list[i % len(shift_list)] # cycle through shift_list
136 v1 = nodes[i % n] # cycle repeatedly through nodes
137 v2 = nodes[(i + shift) % n]
138 G.add_edge(v1, v2)
139 return G
142# -------------------------------------------------------------------------------
143# Various small and named graphs
144# -------------------------------------------------------------------------------
147@_raise_on_directed
148@nx._dispatchable(graphs=None, returns_graph=True)
149def bull_graph(create_using=None):
150 """
151 Returns the Bull Graph
153 The Bull Graph has 5 nodes and 5 edges. It is a planar undirected
154 graph in the form of a triangle with two disjoint pendant edges [1]_
155 The name comes from the triangle and pendant edges representing
156 respectively the body and legs of a bull.
158 Parameters
159 ----------
160 create_using : NetworkX graph constructor, optional (default=nx.Graph)
161 Graph type to create. If graph instance, then cleared before populated.
163 Returns
164 -------
165 G : networkx Graph
166 A bull graph with 5 nodes
168 References
169 ----------
170 .. [1] https://en.wikipedia.org/wiki/Bull_graph.
172 """
173 G = nx.from_dict_of_lists(
174 {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 4], 3: [1], 4: [2]},
175 create_using=create_using,
176 )
177 G.name = "Bull Graph"
178 return G
181@_raise_on_directed
182@nx._dispatchable(graphs=None, returns_graph=True)
183def chvatal_graph(create_using=None):
184 """
185 Returns the Chvátal Graph
187 The Chvátal Graph is an undirected graph with 12 nodes and 24 edges [1]_.
188 It has 370 distinct (directed) Hamiltonian cycles, giving a unique generalized
189 LCF notation of order 4, two of order 6 , and 43 of order 1 [2]_.
191 Parameters
192 ----------
193 create_using : NetworkX graph constructor, optional (default=nx.Graph)
194 Graph type to create. If graph instance, then cleared before populated.
196 Returns
197 -------
198 G : networkx Graph
199 The Chvátal graph with 12 nodes and 24 edges
201 References
202 ----------
203 .. [1] https://en.wikipedia.org/wiki/Chv%C3%A1tal_graph
204 .. [2] https://mathworld.wolfram.com/ChvatalGraph.html
206 """
207 G = nx.from_dict_of_lists(
208 {
209 0: [1, 4, 6, 9],
210 1: [2, 5, 7],
211 2: [3, 6, 8],
212 3: [4, 7, 9],
213 4: [5, 8],
214 5: [10, 11],
215 6: [10, 11],
216 7: [8, 11],
217 8: [10],
218 9: [10, 11],
219 },
220 create_using=create_using,
221 )
222 G.name = "Chvatal Graph"
223 return G
226@_raise_on_directed
227@nx._dispatchable(graphs=None, returns_graph=True)
228def cubical_graph(create_using=None):
229 """
230 Returns the 3-regular Platonic Cubical Graph
232 The skeleton of the cube (the nodes and edges) form a graph, with 8
233 nodes, and 12 edges. It is a special case of the hypercube graph.
234 It is one of 5 Platonic graphs, each a skeleton of its
235 Platonic solid [1]_.
236 Such graphs arise in parallel processing in computers.
238 Parameters
239 ----------
240 create_using : NetworkX graph constructor, optional (default=nx.Graph)
241 Graph type to create. If graph instance, then cleared before populated.
243 Returns
244 -------
245 G : networkx Graph
246 A cubical graph with 8 nodes and 12 edges
248 See Also
249 --------
250 tetrahedral_graph, octahedral_graph, dodecahedral_graph, icosahedral_graph
252 References
253 ----------
254 .. [1] https://en.wikipedia.org/wiki/Cube#Cubical_graph
256 """
257 G = nx.from_dict_of_lists(
258 {
259 0: [1, 3, 4],
260 1: [0, 2, 7],
261 2: [1, 3, 6],
262 3: [0, 2, 5],
263 4: [0, 5, 7],
264 5: [3, 4, 6],
265 6: [2, 5, 7],
266 7: [1, 4, 6],
267 },
268 create_using=create_using,
269 )
270 G.name = "Platonic Cubical Graph"
271 return G
274@nx._dispatchable(graphs=None, returns_graph=True)
275def desargues_graph(create_using=None):
276 """
277 Returns the Desargues Graph
279 The Desargues Graph is a non-planar, distance-transitive cubic graph
280 with 20 nodes and 30 edges [1]_. It is isomorphic to the Generalized
281 Petersen Graph GP(10, 3). It is a symmetric graph. It can be represented
282 in LCF notation as [5,-5,9,-9]^5 [2]_.
284 Parameters
285 ----------
286 create_using : NetworkX graph constructor, optional (default=nx.Graph)
287 Graph type to create. If graph instance, then cleared before populated.
289 Returns
290 -------
291 G : networkx Graph
292 Desargues Graph with 20 nodes and 30 edges
294 References
295 ----------
296 .. [1] https://en.wikipedia.org/wiki/Desargues_graph
297 .. [2] https://mathworld.wolfram.com/DesarguesGraph.html
298 """
299 G = LCF_graph(20, [5, -5, 9, -9], 5, create_using)
300 G.name = "Desargues Graph"
301 return G
304@_raise_on_directed
305@nx._dispatchable(graphs=None, returns_graph=True)
306def diamond_graph(create_using=None):
307 """
308 Returns the Diamond graph
310 The Diamond Graph is planar undirected graph with 4 nodes and 5 edges.
311 It is also sometimes known as the double triangle graph or kite graph [1]_.
313 Parameters
314 ----------
315 create_using : NetworkX graph constructor, optional (default=nx.Graph)
316 Graph type to create. If graph instance, then cleared before populated.
318 Returns
319 -------
320 G : networkx Graph
321 Diamond Graph with 4 nodes and 5 edges
323 References
324 ----------
325 .. [1] https://mathworld.wolfram.com/DiamondGraph.html
326 """
327 G = nx.from_dict_of_lists(
328 {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 3], 3: [1, 2]}, create_using=create_using
329 )
330 G.name = "Diamond Graph"
331 return G
334@nx._dispatchable(graphs=None, returns_graph=True)
335def dodecahedral_graph(create_using=None):
336 """
337 Returns the Platonic Dodecahedral graph.
339 The dodecahedral graph has 20 nodes and 30 edges. The skeleton of the
340 dodecahedron forms a graph. It is one of 5 Platonic graphs [1]_.
341 It can be described in LCF notation as:
342 ``[10, 7, 4, -4, -7, 10, -4, 7, -7, 4]^2`` [2]_.
344 Parameters
345 ----------
346 create_using : NetworkX graph constructor, optional (default=nx.Graph)
347 Graph type to create. If graph instance, then cleared before populated.
349 Returns
350 -------
351 G : networkx Graph
352 Dodecahedral Graph with 20 nodes and 30 edges
354 See Also
355 --------
356 tetrahedral_graph, cubical_graph, octahedral_graph, icosahedral_graph
358 References
359 ----------
360 .. [1] https://en.wikipedia.org/wiki/Regular_dodecahedron#Dodecahedral_graph
361 .. [2] https://mathworld.wolfram.com/DodecahedralGraph.html
363 """
364 G = LCF_graph(20, [10, 7, 4, -4, -7, 10, -4, 7, -7, 4], 2, create_using)
365 G.name = "Dodecahedral Graph"
366 return G
369@nx._dispatchable(graphs=None, returns_graph=True)
370def frucht_graph(create_using=None):
371 """
372 Returns the Frucht Graph.
374 The Frucht Graph is the smallest cubical graph whose
375 automorphism group consists only of the identity element [1]_.
376 It has 12 nodes and 18 edges and no nontrivial symmetries.
377 It is planar and Hamiltonian [2]_.
379 Parameters
380 ----------
381 create_using : NetworkX graph constructor, optional (default=nx.Graph)
382 Graph type to create. If graph instance, then cleared before populated.
384 Returns
385 -------
386 G : networkx Graph
387 Frucht Graph with 12 nodes and 18 edges
389 References
390 ----------
391 .. [1] https://en.wikipedia.org/wiki/Frucht_graph
392 .. [2] https://mathworld.wolfram.com/FruchtGraph.html
394 """
395 G = cycle_graph(7, create_using)
396 G.add_edges_from(
397 [
398 [0, 7],
399 [1, 7],
400 [2, 8],
401 [3, 9],
402 [4, 9],
403 [5, 10],
404 [6, 10],
405 [7, 11],
406 [8, 11],
407 [8, 9],
408 [10, 11],
409 ]
410 )
412 G.name = "Frucht Graph"
413 return G
416@nx._dispatchable(graphs=None, returns_graph=True)
417def heawood_graph(create_using=None):
418 """
419 Returns the Heawood Graph, a (3,6) cage.
421 The Heawood Graph is an undirected graph with 14 nodes and 21 edges,
422 named after Percy John Heawood [1]_.
423 It is cubic symmetric, nonplanar, Hamiltonian, and can be represented
424 in LCF notation as ``[5,-5]^7`` [2]_.
425 It is the unique (3,6)-cage: the regular cubic graph of girth 6 with
426 minimal number of vertices [3]_.
428 Parameters
429 ----------
430 create_using : NetworkX graph constructor, optional (default=nx.Graph)
431 Graph type to create. If graph instance, then cleared before populated.
433 Returns
434 -------
435 G : networkx Graph
436 Heawood Graph with 14 nodes and 21 edges
438 References
439 ----------
440 .. [1] https://en.wikipedia.org/wiki/Heawood_graph
441 .. [2] https://mathworld.wolfram.com/HeawoodGraph.html
442 .. [3] https://www.win.tue.nl/~aeb/graphs/Heawood.html
444 """
445 G = LCF_graph(14, [5, -5], 7, create_using)
446 G.name = "Heawood Graph"
447 return G
450@nx._dispatchable(graphs=None, returns_graph=True)
451def hoffman_singleton_graph():
452 """
453 Returns the Hoffman-Singleton Graph.
455 The Hoffman–Singleton graph is a symmetrical undirected graph
456 with 50 nodes and 175 edges.
457 All indices lie in ``Z % 5``: that is, the integers mod 5 [1]_.
458 It is the only regular graph of vertex degree 7, diameter 2, and girth 5.
459 It is the unique (7,5)-cage graph and Moore graph, and contains many
460 copies of the Petersen Graph [2]_.
462 Returns
463 -------
464 G : networkx Graph
465 Hoffman–Singleton Graph with 50 nodes and 175 edges
467 Notes
468 -----
469 Constructed from pentagon and pentagram as follows: Take five pentagons $P_h$
470 and five pentagrams $Q_i$ . Join vertex $j$ of $P_h$ to vertex $h·i+j$ of $Q_i$ [3]_.
472 References
473 ----------
474 .. [1] https://blogs.ams.org/visualinsight/2016/02/01/hoffman-singleton-graph/
475 .. [2] https://mathworld.wolfram.com/Hoffman-SingletonGraph.html
476 .. [3] https://en.wikipedia.org/wiki/Hoffman%E2%80%93Singleton_graph
478 """
479 G = nx.Graph()
480 for i in range(5):
481 for j in range(5):
482 G.add_edge(("pentagon", i, j), ("pentagon", i, (j - 1) % 5))
483 G.add_edge(("pentagon", i, j), ("pentagon", i, (j + 1) % 5))
484 G.add_edge(("pentagram", i, j), ("pentagram", i, (j - 2) % 5))
485 G.add_edge(("pentagram", i, j), ("pentagram", i, (j + 2) % 5))
486 for k in range(5):
487 G.add_edge(("pentagon", i, j), ("pentagram", k, (i * k + j) % 5))
488 G = nx.convert_node_labels_to_integers(G)
489 G.name = "Hoffman-Singleton Graph"
490 return G
493@_raise_on_directed
494@nx._dispatchable(graphs=None, returns_graph=True)
495def house_graph(create_using=None):
496 """
497 Returns the House graph (square with triangle on top)
499 The house graph is a simple undirected graph with
500 5 nodes and 6 edges [1]_.
502 Parameters
503 ----------
504 create_using : NetworkX graph constructor, optional (default=nx.Graph)
505 Graph type to create. If graph instance, then cleared before populated.
507 Returns
508 -------
509 G : networkx Graph
510 House graph in the form of a square with a triangle on top
512 References
513 ----------
514 .. [1] https://mathworld.wolfram.com/HouseGraph.html
515 """
516 G = nx.from_dict_of_lists(
517 {0: [1, 2], 1: [0, 3], 2: [0, 3, 4], 3: [1, 2, 4], 4: [2, 3]},
518 create_using=create_using,
519 )
520 G.name = "House Graph"
521 return G
524@_raise_on_directed
525@nx._dispatchable(graphs=None, returns_graph=True)
526def house_x_graph(create_using=None):
527 """
528 Returns the House graph with a cross inside the house square.
530 The House X-graph is the House graph plus the two edges connecting diagonally
531 opposite vertices of the square base. It is also one of the two graphs
532 obtained by removing two edges from the pentatope graph [1]_.
534 Parameters
535 ----------
536 create_using : NetworkX graph constructor, optional (default=nx.Graph)
537 Graph type to create. If graph instance, then cleared before populated.
539 Returns
540 -------
541 G : networkx Graph
542 House graph with diagonal vertices connected
544 References
545 ----------
546 .. [1] https://mathworld.wolfram.com/HouseGraph.html
547 """
548 G = house_graph(create_using)
549 G.add_edges_from([(0, 3), (1, 2)])
550 G.name = "House-with-X-inside Graph"
551 return G
554@_raise_on_directed
555@nx._dispatchable(graphs=None, returns_graph=True)
556def icosahedral_graph(create_using=None):
557 """
558 Returns the Platonic Icosahedral graph.
560 The icosahedral graph has 12 nodes and 30 edges. It is a Platonic graph
561 whose nodes have the connectivity of the icosahedron. It is undirected,
562 regular and Hamiltonian [1]_.
564 Parameters
565 ----------
566 create_using : NetworkX graph constructor, optional (default=nx.Graph)
567 Graph type to create. If graph instance, then cleared before populated.
569 Returns
570 -------
571 G : networkx Graph
572 Icosahedral graph with 12 nodes and 30 edges.
574 See Also
575 --------
576 tetrahedral_graph, cubical_graph, octahedral_graph, dodecahedral_graph
578 References
579 ----------
580 .. [1] https://mathworld.wolfram.com/IcosahedralGraph.html
581 """
582 G = nx.from_dict_of_lists(
583 {
584 0: [1, 5, 7, 8, 11],
585 1: [2, 5, 6, 8],
586 2: [3, 6, 8, 9],
587 3: [4, 6, 9, 10],
588 4: [5, 6, 10, 11],
589 5: [6, 11],
590 7: [8, 9, 10, 11],
591 8: [9],
592 9: [10],
593 10: [11],
594 },
595 create_using=create_using,
596 )
597 G.name = "Platonic Icosahedral Graph"
598 return G
601@_raise_on_directed
602@nx._dispatchable(graphs=None, returns_graph=True)
603def krackhardt_kite_graph(create_using=None):
604 """
605 Returns the Krackhardt Kite Social Network.
607 A 10 actor social network introduced by David Krackhardt
608 to illustrate different centrality measures [1]_.
610 Parameters
611 ----------
612 create_using : NetworkX graph constructor, optional (default=nx.Graph)
613 Graph type to create. If graph instance, then cleared before populated.
615 Returns
616 -------
617 G : networkx Graph
618 Krackhardt Kite graph with 10 nodes and 18 edges
620 Notes
621 -----
622 The traditional labeling is:
623 Andre=1, Beverley=2, Carol=3, Diane=4,
624 Ed=5, Fernando=6, Garth=7, Heather=8, Ike=9, Jane=10.
626 References
627 ----------
628 .. [1] Krackhardt, David. "Assessing the Political Landscape: Structure,
629 Cognition, and Power in Organizations". Administrative Science Quarterly.
630 35 (2): 342–369. doi:10.2307/2393394. JSTOR 2393394. June 1990.
632 """
633 G = nx.from_dict_of_lists(
634 {
635 0: [1, 2, 3, 5],
636 1: [0, 3, 4, 6],
637 2: [0, 3, 5],
638 3: [0, 1, 2, 4, 5, 6],
639 4: [1, 3, 6],
640 5: [0, 2, 3, 6, 7],
641 6: [1, 3, 4, 5, 7],
642 7: [5, 6, 8],
643 8: [7, 9],
644 9: [8],
645 },
646 create_using=create_using,
647 )
648 G.name = "Krackhardt Kite Social Network"
649 return G
652@nx._dispatchable(graphs=None, returns_graph=True)
653def moebius_kantor_graph(create_using=None):
654 """
655 Returns the Moebius-Kantor graph.
657 The Möbius-Kantor graph is the cubic symmetric graph on 16 nodes.
658 Its LCF notation is [5,-5]^8, and it is isomorphic to the generalized
659 Petersen Graph GP(8, 3) [1]_.
661 Parameters
662 ----------
663 create_using : NetworkX graph constructor, optional (default=nx.Graph)
664 Graph type to create. If graph instance, then cleared before populated.
666 Returns
667 -------
668 G : networkx Graph
669 Moebius-Kantor graph
671 References
672 ----------
673 .. [1] https://en.wikipedia.org/wiki/M%C3%B6bius%E2%80%93Kantor_graph
675 """
676 G = LCF_graph(16, [5, -5], 8, create_using)
677 G.name = "Moebius-Kantor Graph"
678 return G
681@_raise_on_directed
682@nx._dispatchable(graphs=None, returns_graph=True)
683def octahedral_graph(create_using=None):
684 """
685 Returns the Platonic Octahedral graph.
687 The octahedral graph is the 6-node 12-edge Platonic graph having the
688 connectivity of the octahedron [1]_. If 6 couples go to a party,
689 and each person shakes hands with every person except his or her partner,
690 then this graph describes the set of handshakes that take place;
691 for this reason it is also called the cocktail party graph [2]_.
693 Parameters
694 ----------
695 create_using : NetworkX graph constructor, optional (default=nx.Graph)
696 Graph type to create. If graph instance, then cleared before populated.
698 Returns
699 -------
700 G : networkx Graph
701 Octahedral graph
703 See Also
704 --------
705 tetrahedral_graph, cubical_graph, dodecahedral_graph, icosahedral_graph
707 References
708 ----------
709 .. [1] https://mathworld.wolfram.com/OctahedralGraph.html
710 .. [2] https://en.wikipedia.org/wiki/Tur%C3%A1n_graph#Special_cases
712 """
713 G = nx.from_dict_of_lists(
714 {0: [1, 2, 3, 4], 1: [2, 3, 5], 2: [4, 5], 3: [4, 5], 4: [5]},
715 create_using=create_using,
716 )
717 G.name = "Platonic Octahedral Graph"
718 return G
721@nx._dispatchable(graphs=None, returns_graph=True)
722def pappus_graph():
723 """
724 Returns the Pappus graph.
726 The Pappus graph is a cubic symmetric distance-regular graph with 18 nodes
727 and 27 edges. It is Hamiltonian and can be represented in LCF notation as
728 [5,7,-7,7,-7,-5]^3 [1]_.
730 Returns
731 -------
732 G : networkx Graph
733 Pappus graph
735 References
736 ----------
737 .. [1] https://en.wikipedia.org/wiki/Pappus_graph
738 """
739 G = LCF_graph(18, [5, 7, -7, 7, -7, -5], 3)
740 G.name = "Pappus Graph"
741 return G
744@_raise_on_directed
745@nx._dispatchable(graphs=None, returns_graph=True)
746def petersen_graph(create_using=None):
747 """
748 Returns the Petersen Graph.
750 The Peterson Graph is a cubic, undirected graph with 10 nodes and 15 edges [1]_.
751 Julius Petersen constructed the graph as the smallest counterexample
752 against the claim that a connected bridgeless cubic graph
753 has an edge colouring with three colours [2]_.
755 Parameters
756 ----------
757 create_using : NetworkX graph constructor, optional (default=nx.Graph)
758 Graph type to create. If graph instance, then cleared before populated.
760 Returns
761 -------
762 G : networkx Graph
763 Petersen Graph
765 References
766 ----------
767 .. [1] https://en.wikipedia.org/wiki/Petersen_graph
768 .. [2] https://www.win.tue.nl/~aeb/drg/graphs/Petersen.html
769 """
770 G = nx.from_dict_of_lists(
771 {
772 0: [1, 4, 5],
773 1: [0, 2, 6],
774 2: [1, 3, 7],
775 3: [2, 4, 8],
776 4: [3, 0, 9],
777 5: [0, 7, 8],
778 6: [1, 8, 9],
779 7: [2, 5, 9],
780 8: [3, 5, 6],
781 9: [4, 6, 7],
782 },
783 create_using=create_using,
784 )
785 G.name = "Petersen Graph"
786 return G
789@nx._dispatchable(graphs=None, returns_graph=True)
790def generalized_petersen_graph(n, k, *, create_using=None):
791 """
792 Returns the Generalized Petersen Graph GP(n,k).
794 The Generalized Peterson Graph consists of an outer cycle of n nodes
795 connected to an inner circulant graph of n nodes, where nodes in the
796 inner circulant are connected to their kth nearest neighbor [1]_ [2]_.
797 A Generalized Petersen Graph is cubic with 2n nodes and 3n edges.
799 Some well known graphs are examples of Generalized Petersen Graphs such
800 as the Petersen Graph GP(5, 2), the Desargues graph GP(10, 3), the
801 Moebius-Kantor graph GP(8, 3), and the dodecahedron graph GP(10, 2).
803 Parameters
804 ----------
805 n : int
806 Number of nodes in the outer cycle and inner circulant. ``n >= 3`` is required.
808 k : int
809 Neighbor to connect in the inner circulant. ``1 <= k <= n/2``.
810 Note that some people require ``k < n/2`` but we and others allow equality.
811 Also, ``k < n/2`` is equivalent to ``k <= floor((n-1)/2)``
813 create_using : NetworkX graph constructor, optional (default=nx.Graph)
814 Graph type to create. If graph instance, then cleared before populated.
816 Returns
817 -------
818 G : networkx Graph
819 Generalized Petersen Graph n k
821 References
822 ----------
823 .. [1] https://mathworld.wolfram.com/GeneralizedPetersenGraph.html
824 .. [2] https://en.wikipedia.org/wiki/Generalized_Petersen_graph
825 """
826 if n <= 2:
827 raise NetworkXError(f"n >= 3 required. Got {n=}")
828 if k < 1 or k > n / 2:
829 raise NetworkXError(f" Got {n=} {k=}. Need 1 <= k <= n/2")
831 G = nx.cycle_graph(range(n), create_using=create_using) # u-nodes
832 if G.is_directed():
833 raise NetworkXError("Directed Graph not supported in create_using")
834 for i in range(n):
835 G.add_edge(i, n + i) # add v-nodes and u to v edges
836 G.add_edge(n + i, n + (i + k) % n) # edge from v_i to v_(i+k)%n
838 G.name = f"Generalized Petersen Graph GP({n}, {k})"
839 return G
842@nx._dispatchable(graphs=None, returns_graph=True)
843def sedgewick_maze_graph(create_using=None):
844 """
845 Return a small maze with a cycle.
847 This is the maze used in Sedgewick, 3rd Edition, Part 5, Graph
848 Algorithms, Chapter 18, e.g. Figure 18.2 and following [1]_.
849 Nodes are numbered 0,..,7
851 Parameters
852 ----------
853 create_using : NetworkX graph constructor, optional (default=nx.Graph)
854 Graph type to create. If graph instance, then cleared before populated.
856 Returns
857 -------
858 G : networkx Graph
859 Small maze with a cycle
861 References
862 ----------
863 .. [1] Figure 18.2, Chapter 18, Graph Algorithms (3rd Ed), Sedgewick
864 """
865 G = empty_graph(0, create_using)
866 G.add_nodes_from(range(8))
867 G.add_edges_from([[0, 2], [0, 7], [0, 5]])
868 G.add_edges_from([[1, 7], [2, 6]])
869 G.add_edges_from([[3, 4], [3, 5]])
870 G.add_edges_from([[4, 5], [4, 7], [4, 6]])
871 G.name = "Sedgewick Maze"
872 return G
875@nx._dispatchable(graphs=None, returns_graph=True)
876def tetrahedral_graph(create_using=None):
877 """
878 Returns the 3-regular Platonic Tetrahedral graph.
880 Tetrahedral graph has 4 nodes and 6 edges. It is a
881 special case of the complete graph, K4, and wheel graph, W4.
882 It is one of the 5 platonic graphs [1]_.
884 Parameters
885 ----------
886 create_using : NetworkX graph constructor, optional (default=nx.Graph)
887 Graph type to create. If graph instance, then cleared before populated.
889 Returns
890 -------
891 G : networkx Graph
892 Tetrahedral Graph
894 See Also
895 --------
896 cubical_graph, octahedral_graph, dodecahedral_graph, icosahedral_graph
898 References
899 ----------
900 .. [1] https://en.wikipedia.org/wiki/Tetrahedron#Tetrahedral_graph
902 """
903 G = complete_graph(4, create_using)
904 G.name = "Platonic Tetrahedral Graph"
905 return G
908@_raise_on_directed
909@nx._dispatchable(graphs=None, returns_graph=True)
910def truncated_cube_graph(create_using=None):
911 """
912 Returns the skeleton of the truncated cube.
914 The truncated cube is an Archimedean solid with 14 regular
915 faces (6 octagonal and 8 triangular), 36 edges and 24 nodes [1]_.
916 The truncated cube is created by truncating (cutting off) the tips
917 of the cube one third of the way into each edge [2]_.
919 Parameters
920 ----------
921 create_using : NetworkX graph constructor, optional (default=nx.Graph)
922 Graph type to create. If graph instance, then cleared before populated.
924 Returns
925 -------
926 G : networkx Graph
927 Skeleton of the truncated cube
929 References
930 ----------
931 .. [1] https://en.wikipedia.org/wiki/Truncated_cube
932 .. [2] https://www.coolmath.com/reference/polyhedra-truncated-cube
934 """
935 G = nx.from_dict_of_lists(
936 {
937 0: [1, 2, 4],
938 1: [11, 14],
939 2: [3, 4],
940 3: [6, 8],
941 4: [5],
942 5: [16, 18],
943 6: [7, 8],
944 7: [10, 12],
945 8: [9],
946 9: [17, 20],
947 10: [11, 12],
948 11: [14],
949 12: [13],
950 13: [21, 22],
951 14: [15],
952 15: [19, 23],
953 16: [17, 18],
954 17: [20],
955 18: [19],
956 19: [23],
957 20: [21],
958 21: [22],
959 22: [23],
960 },
961 create_using=create_using,
962 )
963 G.name = "Truncated Cube Graph"
964 return G
967@nx._dispatchable(graphs=None, returns_graph=True)
968def truncated_tetrahedron_graph(create_using=None):
969 """
970 Returns the skeleton of the truncated Platonic tetrahedron.
972 The truncated tetrahedron is an Archimedean solid with 4 regular hexagonal faces,
973 4 equilateral triangle faces, 12 nodes and 18 edges. It can be constructed by truncating
974 all 4 vertices of a regular tetrahedron at one third of the original edge length [1]_.
976 Parameters
977 ----------
978 create_using : NetworkX graph constructor, optional (default=nx.Graph)
979 Graph type to create. If graph instance, then cleared before populated.
981 Returns
982 -------
983 G : networkx Graph
984 Skeleton of the truncated tetrahedron
986 References
987 ----------
988 .. [1] https://en.wikipedia.org/wiki/Truncated_tetrahedron
990 """
991 G = path_graph(12, create_using)
992 G.add_edges_from([(0, 2), (0, 9), (1, 6), (3, 11), (4, 11), (5, 7), (8, 10)])
993 G.name = "Truncated Tetrahedron Graph"
994 return G
997@_raise_on_directed
998@nx._dispatchable(graphs=None, returns_graph=True)
999def tutte_graph(create_using=None):
1000 """
1001 Returns the Tutte graph.
1003 The Tutte graph is a cubic polyhedral, non-Hamiltonian graph. It has
1004 46 nodes and 69 edges.
1005 It is a counterexample to Tait's conjecture that every 3-regular polyhedron
1006 has a Hamiltonian cycle.
1007 It can be realized geometrically from a tetrahedron by multiply truncating
1008 three of its vertices [1]_.
1010 Parameters
1011 ----------
1012 create_using : NetworkX graph constructor, optional (default=nx.Graph)
1013 Graph type to create. If graph instance, then cleared before populated.
1015 Returns
1016 -------
1017 G : networkx Graph
1018 Tutte graph
1020 References
1021 ----------
1022 .. [1] https://en.wikipedia.org/wiki/Tutte_graph
1023 """
1024 G = nx.from_dict_of_lists(
1025 {
1026 0: [1, 2, 3],
1027 1: [4, 26],
1028 2: [10, 11],
1029 3: [18, 19],
1030 4: [5, 33],
1031 5: [6, 29],
1032 6: [7, 27],
1033 7: [8, 14],
1034 8: [9, 38],
1035 9: [10, 37],
1036 10: [39],
1037 11: [12, 39],
1038 12: [13, 35],
1039 13: [14, 15],
1040 14: [34],
1041 15: [16, 22],
1042 16: [17, 44],
1043 17: [18, 43],
1044 18: [45],
1045 19: [20, 45],
1046 20: [21, 41],
1047 21: [22, 23],
1048 22: [40],
1049 23: [24, 27],
1050 24: [25, 32],
1051 25: [26, 31],
1052 26: [33],
1053 27: [28],
1054 28: [29, 32],
1055 29: [30],
1056 30: [31, 33],
1057 31: [32],
1058 34: [35, 38],
1059 35: [36],
1060 36: [37, 39],
1061 37: [38],
1062 40: [41, 44],
1063 41: [42],
1064 42: [43, 45],
1065 43: [44],
1066 },
1067 create_using=create_using,
1068 )
1069 G.name = "Tutte's Graph"
1070 return G