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 "heawood_graph",
16 "hoffman_singleton_graph",
17 "house_graph",
18 "house_x_graph",
19 "icosahedral_graph",
20 "krackhardt_kite_graph",
21 "moebius_kantor_graph",
22 "octahedral_graph",
23 "pappus_graph",
24 "petersen_graph",
25 "sedgewick_maze_graph",
26 "tetrahedral_graph",
27 "truncated_cube_graph",
28 "truncated_tetrahedron_graph",
29 "tutte_graph",
30]
32from functools import wraps
34import networkx as nx
35from networkx.exception import NetworkXError
36from networkx.generators.classic import (
37 complete_graph,
38 cycle_graph,
39 empty_graph,
40 path_graph,
41)
44def _raise_on_directed(func):
45 """
46 A decorator which inspects the `create_using` argument and raises a
47 NetworkX exception when `create_using` is a DiGraph (class or instance) for
48 graph generators that do not support directed outputs.
50 `create_using` may be a keyword argument or the first positional argument.
51 """
53 @wraps(func)
54 def wrapper(*args, **kwargs):
55 create_using = args[0] if args else kwargs.get("create_using")
56 if create_using is not None:
57 G = nx.empty_graph(create_using=create_using)
58 if G.is_directed():
59 raise NetworkXError("Directed Graph not supported")
60 return func(*args, **kwargs)
62 return wrapper
65@nx._dispatchable(graphs=None, returns_graph=True)
66def LCF_graph(n, shift_list, repeats, create_using=None):
67 """
68 Return the cubic graph specified in LCF notation.
70 LCF (Lederberg-Coxeter-Fruchte) notation[1]_ is a compressed
71 notation used in the generation of various cubic Hamiltonian
72 graphs of high symmetry. See, for example, `dodecahedral_graph`,
73 `desargues_graph`, `heawood_graph` and `pappus_graph`.
75 Nodes are drawn from ``range(n)``. Each node ``n_i`` is connected with
76 node ``n_i + shift % n`` where ``shift`` is given by cycling through
77 the input `shift_list` `repeat` s times.
79 Parameters
80 ----------
81 n : int
82 The starting graph is the `n`-cycle with nodes ``0, ..., n-1``.
83 The null graph is returned if `n` < 1.
85 shift_list : list
86 A list of integer shifts mod `n`, ``[s1, s2, .., sk]``
88 repeats : int
89 Integer specifying the number of times that shifts in `shift_list`
90 are successively applied to each current node in the n-cycle
91 to generate an edge between ``n_current`` and ``n_current + shift mod n``.
93 Returns
94 -------
95 G : Graph
96 A graph instance created from the specified LCF notation.
98 Examples
99 --------
100 The utility graph $K_{3,3}$
102 >>> G = nx.LCF_graph(6, [3, -3], 3)
103 >>> G.edges()
104 EdgeView([(0, 1), (0, 5), (0, 3), (1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5)])
106 The Heawood graph:
108 >>> G = nx.LCF_graph(14, [5, -5], 7)
109 >>> nx.is_isomorphic(G, nx.heawood_graph())
110 True
112 References
113 ----------
114 .. [1] https://en.wikipedia.org/wiki/LCF_notation
116 """
117 if n <= 0:
118 return empty_graph(0, create_using)
120 # start with the n-cycle
121 G = cycle_graph(n, create_using)
122 if G.is_directed():
123 raise NetworkXError("Directed Graph not supported")
124 G.name = "LCF_graph"
125 nodes = sorted(G)
127 n_extra_edges = repeats * len(shift_list)
128 # edges are added n_extra_edges times
129 # (not all of these need be new)
130 if n_extra_edges < 1:
131 return G
133 for i in range(n_extra_edges):
134 shift = shift_list[i % len(shift_list)] # cycle through shift_list
135 v1 = nodes[i % n] # cycle repeatedly through nodes
136 v2 = nodes[(i + shift) % n]
137 G.add_edge(v1, v2)
138 return G
141# -------------------------------------------------------------------------------
142# Various small and named graphs
143# -------------------------------------------------------------------------------
146@_raise_on_directed
147@nx._dispatchable(graphs=None, returns_graph=True)
148def bull_graph(create_using=None):
149 """
150 Returns the Bull Graph
152 The Bull Graph has 5 nodes and 5 edges. It is a planar undirected
153 graph in the form of a triangle with two disjoint pendant edges [1]_
154 The name comes from the triangle and pendant edges representing
155 respectively the body and legs of a bull.
157 Parameters
158 ----------
159 create_using : NetworkX graph constructor, optional (default=nx.Graph)
160 Graph type to create. If graph instance, then cleared before populated.
162 Returns
163 -------
164 G : networkx Graph
165 A bull graph with 5 nodes
167 References
168 ----------
169 .. [1] https://en.wikipedia.org/wiki/Bull_graph.
171 """
172 G = nx.from_dict_of_lists(
173 {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 4], 3: [1], 4: [2]},
174 create_using=create_using,
175 )
176 G.name = "Bull Graph"
177 return G
180@_raise_on_directed
181@nx._dispatchable(graphs=None, returns_graph=True)
182def chvatal_graph(create_using=None):
183 """
184 Returns the Chvátal Graph
186 The Chvátal Graph is an undirected graph with 12 nodes and 24 edges [1]_.
187 It has 370 distinct (directed) Hamiltonian cycles, giving a unique generalized
188 LCF notation of order 4, two of order 6 , and 43 of order 1 [2]_.
190 Parameters
191 ----------
192 create_using : NetworkX graph constructor, optional (default=nx.Graph)
193 Graph type to create. If graph instance, then cleared before populated.
195 Returns
196 -------
197 G : networkx Graph
198 The Chvátal graph with 12 nodes and 24 edges
200 References
201 ----------
202 .. [1] https://en.wikipedia.org/wiki/Chv%C3%A1tal_graph
203 .. [2] https://mathworld.wolfram.com/ChvatalGraph.html
205 """
206 G = nx.from_dict_of_lists(
207 {
208 0: [1, 4, 6, 9],
209 1: [2, 5, 7],
210 2: [3, 6, 8],
211 3: [4, 7, 9],
212 4: [5, 8],
213 5: [10, 11],
214 6: [10, 11],
215 7: [8, 11],
216 8: [10],
217 9: [10, 11],
218 },
219 create_using=create_using,
220 )
221 G.name = "Chvatal Graph"
222 return G
225@_raise_on_directed
226@nx._dispatchable(graphs=None, returns_graph=True)
227def cubical_graph(create_using=None):
228 """
229 Returns the 3-regular Platonic Cubical Graph
231 The skeleton of the cube (the nodes and edges) form a graph, with 8
232 nodes, and 12 edges. It is a special case of the hypercube graph.
233 It is one of 5 Platonic graphs, each a skeleton of its
234 Platonic solid [1]_.
235 Such graphs arise in parallel processing in computers.
237 Parameters
238 ----------
239 create_using : NetworkX graph constructor, optional (default=nx.Graph)
240 Graph type to create. If graph instance, then cleared before populated.
242 Returns
243 -------
244 G : networkx Graph
245 A cubical graph with 8 nodes and 12 edges
247 References
248 ----------
249 .. [1] https://en.wikipedia.org/wiki/Cube#Cubical_graph
251 """
252 G = nx.from_dict_of_lists(
253 {
254 0: [1, 3, 4],
255 1: [0, 2, 7],
256 2: [1, 3, 6],
257 3: [0, 2, 5],
258 4: [0, 5, 7],
259 5: [3, 4, 6],
260 6: [2, 5, 7],
261 7: [1, 4, 6],
262 },
263 create_using=create_using,
264 )
265 G.name = "Platonic Cubical Graph"
266 return G
269@nx._dispatchable(graphs=None, returns_graph=True)
270def desargues_graph(create_using=None):
271 """
272 Returns the Desargues Graph
274 The Desargues Graph is a non-planar, distance-transitive cubic graph
275 with 20 nodes and 30 edges [1]_.
276 It is a symmetric graph. It can be represented in LCF notation
277 as [5,-5,9,-9]^5 [2]_.
279 Parameters
280 ----------
281 create_using : NetworkX graph constructor, optional (default=nx.Graph)
282 Graph type to create. If graph instance, then cleared before populated.
284 Returns
285 -------
286 G : networkx Graph
287 Desargues Graph with 20 nodes and 30 edges
289 References
290 ----------
291 .. [1] https://en.wikipedia.org/wiki/Desargues_graph
292 .. [2] https://mathworld.wolfram.com/DesarguesGraph.html
293 """
294 G = LCF_graph(20, [5, -5, 9, -9], 5, create_using)
295 G.name = "Desargues Graph"
296 return G
299@_raise_on_directed
300@nx._dispatchable(graphs=None, returns_graph=True)
301def diamond_graph(create_using=None):
302 """
303 Returns the Diamond graph
305 The Diamond Graph is planar undirected graph with 4 nodes and 5 edges.
306 It is also sometimes known as the double triangle graph or kite graph [1]_.
308 Parameters
309 ----------
310 create_using : NetworkX graph constructor, optional (default=nx.Graph)
311 Graph type to create. If graph instance, then cleared before populated.
313 Returns
314 -------
315 G : networkx Graph
316 Diamond Graph with 4 nodes and 5 edges
318 References
319 ----------
320 .. [1] https://mathworld.wolfram.com/DiamondGraph.html
321 """
322 G = nx.from_dict_of_lists(
323 {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 3], 3: [1, 2]}, create_using=create_using
324 )
325 G.name = "Diamond Graph"
326 return G
329@nx._dispatchable(graphs=None, returns_graph=True)
330def dodecahedral_graph(create_using=None):
331 """
332 Returns the Platonic Dodecahedral graph.
334 The dodecahedral graph has 20 nodes and 30 edges. The skeleton of the
335 dodecahedron forms a graph. It is one of 5 Platonic graphs [1]_.
336 It can be described in LCF notation as:
337 ``[10, 7, 4, -4, -7, 10, -4, 7, -7, 4]^2`` [2]_.
339 Parameters
340 ----------
341 create_using : NetworkX graph constructor, optional (default=nx.Graph)
342 Graph type to create. If graph instance, then cleared before populated.
344 Returns
345 -------
346 G : networkx Graph
347 Dodecahedral Graph with 20 nodes and 30 edges
349 References
350 ----------
351 .. [1] https://en.wikipedia.org/wiki/Regular_dodecahedron#Dodecahedral_graph
352 .. [2] https://mathworld.wolfram.com/DodecahedralGraph.html
354 """
355 G = LCF_graph(20, [10, 7, 4, -4, -7, 10, -4, 7, -7, 4], 2, create_using)
356 G.name = "Dodecahedral Graph"
357 return G
360@nx._dispatchable(graphs=None, returns_graph=True)
361def frucht_graph(create_using=None):
362 """
363 Returns the Frucht Graph.
365 The Frucht Graph is the smallest cubical graph whose
366 automorphism group consists only of the identity element [1]_.
367 It has 12 nodes and 18 edges and no nontrivial symmetries.
368 It is planar and Hamiltonian [2]_.
370 Parameters
371 ----------
372 create_using : NetworkX graph constructor, optional (default=nx.Graph)
373 Graph type to create. If graph instance, then cleared before populated.
375 Returns
376 -------
377 G : networkx Graph
378 Frucht Graph with 12 nodes and 18 edges
380 References
381 ----------
382 .. [1] https://en.wikipedia.org/wiki/Frucht_graph
383 .. [2] https://mathworld.wolfram.com/FruchtGraph.html
385 """
386 G = cycle_graph(7, create_using)
387 G.add_edges_from(
388 [
389 [0, 7],
390 [1, 7],
391 [2, 8],
392 [3, 9],
393 [4, 9],
394 [5, 10],
395 [6, 10],
396 [7, 11],
397 [8, 11],
398 [8, 9],
399 [10, 11],
400 ]
401 )
403 G.name = "Frucht Graph"
404 return G
407@nx._dispatchable(graphs=None, returns_graph=True)
408def heawood_graph(create_using=None):
409 """
410 Returns the Heawood Graph, a (3,6) cage.
412 The Heawood Graph is an undirected graph with 14 nodes and 21 edges,
413 named after Percy John Heawood [1]_.
414 It is cubic symmetric, nonplanar, Hamiltonian, and can be represented
415 in LCF notation as ``[5,-5]^7`` [2]_.
416 It is the unique (3,6)-cage: the regular cubic graph of girth 6 with
417 minimal number of vertices [3]_.
419 Parameters
420 ----------
421 create_using : NetworkX graph constructor, optional (default=nx.Graph)
422 Graph type to create. If graph instance, then cleared before populated.
424 Returns
425 -------
426 G : networkx Graph
427 Heawood Graph with 14 nodes and 21 edges
429 References
430 ----------
431 .. [1] https://en.wikipedia.org/wiki/Heawood_graph
432 .. [2] https://mathworld.wolfram.com/HeawoodGraph.html
433 .. [3] https://www.win.tue.nl/~aeb/graphs/Heawood.html
435 """
436 G = LCF_graph(14, [5, -5], 7, create_using)
437 G.name = "Heawood Graph"
438 return G
441@nx._dispatchable(graphs=None, returns_graph=True)
442def hoffman_singleton_graph():
443 """
444 Returns the Hoffman-Singleton Graph.
446 The Hoffman–Singleton graph is a symmetrical undirected graph
447 with 50 nodes and 175 edges.
448 All indices lie in ``Z % 5``: that is, the integers mod 5 [1]_.
449 It is the only regular graph of vertex degree 7, diameter 2, and girth 5.
450 It is the unique (7,5)-cage graph and Moore graph, and contains many
451 copies of the Petersen graph [2]_.
453 Returns
454 -------
455 G : networkx Graph
456 Hoffman–Singleton Graph with 50 nodes and 175 edges
458 Notes
459 -----
460 Constructed from pentagon and pentagram as follows: Take five pentagons $P_h$
461 and five pentagrams $Q_i$ . Join vertex $j$ of $P_h$ to vertex $h·i+j$ of $Q_i$ [3]_.
463 References
464 ----------
465 .. [1] https://blogs.ams.org/visualinsight/2016/02/01/hoffman-singleton-graph/
466 .. [2] https://mathworld.wolfram.com/Hoffman-SingletonGraph.html
467 .. [3] https://en.wikipedia.org/wiki/Hoffman%E2%80%93Singleton_graph
469 """
470 G = nx.Graph()
471 for i in range(5):
472 for j in range(5):
473 G.add_edge(("pentagon", i, j), ("pentagon", i, (j - 1) % 5))
474 G.add_edge(("pentagon", i, j), ("pentagon", i, (j + 1) % 5))
475 G.add_edge(("pentagram", i, j), ("pentagram", i, (j - 2) % 5))
476 G.add_edge(("pentagram", i, j), ("pentagram", i, (j + 2) % 5))
477 for k in range(5):
478 G.add_edge(("pentagon", i, j), ("pentagram", k, (i * k + j) % 5))
479 G = nx.convert_node_labels_to_integers(G)
480 G.name = "Hoffman-Singleton Graph"
481 return G
484@_raise_on_directed
485@nx._dispatchable(graphs=None, returns_graph=True)
486def house_graph(create_using=None):
487 """
488 Returns the House graph (square with triangle on top)
490 The house graph is a simple undirected graph with
491 5 nodes and 6 edges [1]_.
493 Parameters
494 ----------
495 create_using : NetworkX graph constructor, optional (default=nx.Graph)
496 Graph type to create. If graph instance, then cleared before populated.
498 Returns
499 -------
500 G : networkx Graph
501 House graph in the form of a square with a triangle on top
503 References
504 ----------
505 .. [1] https://mathworld.wolfram.com/HouseGraph.html
506 """
507 G = nx.from_dict_of_lists(
508 {0: [1, 2], 1: [0, 3], 2: [0, 3, 4], 3: [1, 2, 4], 4: [2, 3]},
509 create_using=create_using,
510 )
511 G.name = "House Graph"
512 return G
515@_raise_on_directed
516@nx._dispatchable(graphs=None, returns_graph=True)
517def house_x_graph(create_using=None):
518 """
519 Returns the House graph with a cross inside the house square.
521 The House X-graph is the House graph plus the two edges connecting diagonally
522 opposite vertices of the square base. It is also one of the two graphs
523 obtained by removing two edges from the pentatope graph [1]_.
525 Parameters
526 ----------
527 create_using : NetworkX graph constructor, optional (default=nx.Graph)
528 Graph type to create. If graph instance, then cleared before populated.
530 Returns
531 -------
532 G : networkx Graph
533 House graph with diagonal vertices connected
535 References
536 ----------
537 .. [1] https://mathworld.wolfram.com/HouseGraph.html
538 """
539 G = house_graph(create_using)
540 G.add_edges_from([(0, 3), (1, 2)])
541 G.name = "House-with-X-inside Graph"
542 return G
545@_raise_on_directed
546@nx._dispatchable(graphs=None, returns_graph=True)
547def icosahedral_graph(create_using=None):
548 """
549 Returns the Platonic Icosahedral graph.
551 The icosahedral graph has 12 nodes and 30 edges. It is a Platonic graph
552 whose nodes have the connectivity of the icosahedron. It is undirected,
553 regular and Hamiltonian [1]_.
555 Parameters
556 ----------
557 create_using : NetworkX graph constructor, optional (default=nx.Graph)
558 Graph type to create. If graph instance, then cleared before populated.
560 Returns
561 -------
562 G : networkx Graph
563 Icosahedral graph with 12 nodes and 30 edges.
565 References
566 ----------
567 .. [1] https://mathworld.wolfram.com/IcosahedralGraph.html
568 """
569 G = nx.from_dict_of_lists(
570 {
571 0: [1, 5, 7, 8, 11],
572 1: [2, 5, 6, 8],
573 2: [3, 6, 8, 9],
574 3: [4, 6, 9, 10],
575 4: [5, 6, 10, 11],
576 5: [6, 11],
577 7: [8, 9, 10, 11],
578 8: [9],
579 9: [10],
580 10: [11],
581 },
582 create_using=create_using,
583 )
584 G.name = "Platonic Icosahedral Graph"
585 return G
588@_raise_on_directed
589@nx._dispatchable(graphs=None, returns_graph=True)
590def krackhardt_kite_graph(create_using=None):
591 """
592 Returns the Krackhardt Kite Social Network.
594 A 10 actor social network introduced by David Krackhardt
595 to illustrate different centrality measures [1]_.
597 Parameters
598 ----------
599 create_using : NetworkX graph constructor, optional (default=nx.Graph)
600 Graph type to create. If graph instance, then cleared before populated.
602 Returns
603 -------
604 G : networkx Graph
605 Krackhardt Kite graph with 10 nodes and 18 edges
607 Notes
608 -----
609 The traditional labeling is:
610 Andre=1, Beverley=2, Carol=3, Diane=4,
611 Ed=5, Fernando=6, Garth=7, Heather=8, Ike=9, Jane=10.
613 References
614 ----------
615 .. [1] Krackhardt, David. "Assessing the Political Landscape: Structure,
616 Cognition, and Power in Organizations". Administrative Science Quarterly.
617 35 (2): 342–369. doi:10.2307/2393394. JSTOR 2393394. June 1990.
619 """
620 G = nx.from_dict_of_lists(
621 {
622 0: [1, 2, 3, 5],
623 1: [0, 3, 4, 6],
624 2: [0, 3, 5],
625 3: [0, 1, 2, 4, 5, 6],
626 4: [1, 3, 6],
627 5: [0, 2, 3, 6, 7],
628 6: [1, 3, 4, 5, 7],
629 7: [5, 6, 8],
630 8: [7, 9],
631 9: [8],
632 },
633 create_using=create_using,
634 )
635 G.name = "Krackhardt Kite Social Network"
636 return G
639@nx._dispatchable(graphs=None, returns_graph=True)
640def moebius_kantor_graph(create_using=None):
641 """
642 Returns the Moebius-Kantor graph.
644 The Möbius-Kantor graph is the cubic symmetric graph on 16 nodes.
645 Its LCF notation is [5,-5]^8, and it is isomorphic to the generalized
646 Petersen graph [1]_.
648 Parameters
649 ----------
650 create_using : NetworkX graph constructor, optional (default=nx.Graph)
651 Graph type to create. If graph instance, then cleared before populated.
653 Returns
654 -------
655 G : networkx Graph
656 Moebius-Kantor graph
658 References
659 ----------
660 .. [1] https://en.wikipedia.org/wiki/M%C3%B6bius%E2%80%93Kantor_graph
662 """
663 G = LCF_graph(16, [5, -5], 8, create_using)
664 G.name = "Moebius-Kantor Graph"
665 return G
668@_raise_on_directed
669@nx._dispatchable(graphs=None, returns_graph=True)
670def octahedral_graph(create_using=None):
671 """
672 Returns the Platonic Octahedral graph.
674 The octahedral graph is the 6-node 12-edge Platonic graph having the
675 connectivity of the octahedron [1]_. If 6 couples go to a party,
676 and each person shakes hands with every person except his or her partner,
677 then this graph describes the set of handshakes that take place;
678 for this reason it is also called the cocktail party graph [2]_.
680 Parameters
681 ----------
682 create_using : NetworkX graph constructor, optional (default=nx.Graph)
683 Graph type to create. If graph instance, then cleared before populated.
685 Returns
686 -------
687 G : networkx Graph
688 Octahedral graph
690 References
691 ----------
692 .. [1] https://mathworld.wolfram.com/OctahedralGraph.html
693 .. [2] https://en.wikipedia.org/wiki/Tur%C3%A1n_graph#Special_cases
695 """
696 G = nx.from_dict_of_lists(
697 {0: [1, 2, 3, 4], 1: [2, 3, 5], 2: [4, 5], 3: [4, 5], 4: [5]},
698 create_using=create_using,
699 )
700 G.name = "Platonic Octahedral Graph"
701 return G
704@nx._dispatchable(graphs=None, returns_graph=True)
705def pappus_graph():
706 """
707 Returns the Pappus graph.
709 The Pappus graph is a cubic symmetric distance-regular graph with 18 nodes
710 and 27 edges. It is Hamiltonian and can be represented in LCF notation as
711 [5,7,-7,7,-7,-5]^3 [1]_.
713 Returns
714 -------
715 G : networkx Graph
716 Pappus graph
718 References
719 ----------
720 .. [1] https://en.wikipedia.org/wiki/Pappus_graph
721 """
722 G = LCF_graph(18, [5, 7, -7, 7, -7, -5], 3)
723 G.name = "Pappus Graph"
724 return G
727@_raise_on_directed
728@nx._dispatchable(graphs=None, returns_graph=True)
729def petersen_graph(create_using=None):
730 """
731 Returns the Petersen graph.
733 The Peterson graph is a cubic, undirected graph with 10 nodes and 15 edges [1]_.
734 Julius Petersen constructed the graph as the smallest counterexample
735 against the claim that a connected bridgeless cubic graph
736 has an edge colouring with three colours [2]_.
738 Parameters
739 ----------
740 create_using : NetworkX graph constructor, optional (default=nx.Graph)
741 Graph type to create. If graph instance, then cleared before populated.
743 Returns
744 -------
745 G : networkx Graph
746 Petersen graph
748 References
749 ----------
750 .. [1] https://en.wikipedia.org/wiki/Petersen_graph
751 .. [2] https://www.win.tue.nl/~aeb/drg/graphs/Petersen.html
752 """
753 G = nx.from_dict_of_lists(
754 {
755 0: [1, 4, 5],
756 1: [0, 2, 6],
757 2: [1, 3, 7],
758 3: [2, 4, 8],
759 4: [3, 0, 9],
760 5: [0, 7, 8],
761 6: [1, 8, 9],
762 7: [2, 5, 9],
763 8: [3, 5, 6],
764 9: [4, 6, 7],
765 },
766 create_using=create_using,
767 )
768 G.name = "Petersen Graph"
769 return G
772@nx._dispatchable(graphs=None, returns_graph=True)
773def sedgewick_maze_graph(create_using=None):
774 """
775 Return a small maze with a cycle.
777 This is the maze used in Sedgewick, 3rd Edition, Part 5, Graph
778 Algorithms, Chapter 18, e.g. Figure 18.2 and following [1]_.
779 Nodes are numbered 0,..,7
781 Parameters
782 ----------
783 create_using : NetworkX graph constructor, optional (default=nx.Graph)
784 Graph type to create. If graph instance, then cleared before populated.
786 Returns
787 -------
788 G : networkx Graph
789 Small maze with a cycle
791 References
792 ----------
793 .. [1] Figure 18.2, Chapter 18, Graph Algorithms (3rd Ed), Sedgewick
794 """
795 G = empty_graph(0, create_using)
796 G.add_nodes_from(range(8))
797 G.add_edges_from([[0, 2], [0, 7], [0, 5]])
798 G.add_edges_from([[1, 7], [2, 6]])
799 G.add_edges_from([[3, 4], [3, 5]])
800 G.add_edges_from([[4, 5], [4, 7], [4, 6]])
801 G.name = "Sedgewick Maze"
802 return G
805@nx._dispatchable(graphs=None, returns_graph=True)
806def tetrahedral_graph(create_using=None):
807 """
808 Returns the 3-regular Platonic Tetrahedral graph.
810 Tetrahedral graph has 4 nodes and 6 edges. It is a
811 special case of the complete graph, K4, and wheel graph, W4.
812 It is one of the 5 platonic graphs [1]_.
814 Parameters
815 ----------
816 create_using : NetworkX graph constructor, optional (default=nx.Graph)
817 Graph type to create. If graph instance, then cleared before populated.
819 Returns
820 -------
821 G : networkx Graph
822 Tetrahedral Graph
824 References
825 ----------
826 .. [1] https://en.wikipedia.org/wiki/Tetrahedron#Tetrahedral_graph
828 """
829 G = complete_graph(4, create_using)
830 G.name = "Platonic Tetrahedral Graph"
831 return G
834@_raise_on_directed
835@nx._dispatchable(graphs=None, returns_graph=True)
836def truncated_cube_graph(create_using=None):
837 """
838 Returns the skeleton of the truncated cube.
840 The truncated cube is an Archimedean solid with 14 regular
841 faces (6 octagonal and 8 triangular), 36 edges and 24 nodes [1]_.
842 The truncated cube is created by truncating (cutting off) the tips
843 of the cube one third of the way into each edge [2]_.
845 Parameters
846 ----------
847 create_using : NetworkX graph constructor, optional (default=nx.Graph)
848 Graph type to create. If graph instance, then cleared before populated.
850 Returns
851 -------
852 G : networkx Graph
853 Skeleton of the truncated cube
855 References
856 ----------
857 .. [1] https://en.wikipedia.org/wiki/Truncated_cube
858 .. [2] https://www.coolmath.com/reference/polyhedra-truncated-cube
860 """
861 G = nx.from_dict_of_lists(
862 {
863 0: [1, 2, 4],
864 1: [11, 14],
865 2: [3, 4],
866 3: [6, 8],
867 4: [5],
868 5: [16, 18],
869 6: [7, 8],
870 7: [10, 12],
871 8: [9],
872 9: [17, 20],
873 10: [11, 12],
874 11: [14],
875 12: [13],
876 13: [21, 22],
877 14: [15],
878 15: [19, 23],
879 16: [17, 18],
880 17: [20],
881 18: [19],
882 19: [23],
883 20: [21],
884 21: [22],
885 22: [23],
886 },
887 create_using=create_using,
888 )
889 G.name = "Truncated Cube Graph"
890 return G
893@nx._dispatchable(graphs=None, returns_graph=True)
894def truncated_tetrahedron_graph(create_using=None):
895 """
896 Returns the skeleton of the truncated Platonic tetrahedron.
898 The truncated tetrahedron is an Archimedean solid with 4 regular hexagonal faces,
899 4 equilateral triangle faces, 12 nodes and 18 edges. It can be constructed by truncating
900 all 4 vertices of a regular tetrahedron at one third of the original edge length [1]_.
902 Parameters
903 ----------
904 create_using : NetworkX graph constructor, optional (default=nx.Graph)
905 Graph type to create. If graph instance, then cleared before populated.
907 Returns
908 -------
909 G : networkx Graph
910 Skeleton of the truncated tetrahedron
912 References
913 ----------
914 .. [1] https://en.wikipedia.org/wiki/Truncated_tetrahedron
916 """
917 G = path_graph(12, create_using)
918 G.add_edges_from([(0, 2), (0, 9), (1, 6), (3, 11), (4, 11), (5, 7), (8, 10)])
919 G.name = "Truncated Tetrahedron Graph"
920 return G
923@_raise_on_directed
924@nx._dispatchable(graphs=None, returns_graph=True)
925def tutte_graph(create_using=None):
926 """
927 Returns the Tutte graph.
929 The Tutte graph is a cubic polyhedral, non-Hamiltonian graph. It has
930 46 nodes and 69 edges.
931 It is a counterexample to Tait's conjecture that every 3-regular polyhedron
932 has a Hamiltonian cycle.
933 It can be realized geometrically from a tetrahedron by multiply truncating
934 three of its vertices [1]_.
936 Parameters
937 ----------
938 create_using : NetworkX graph constructor, optional (default=nx.Graph)
939 Graph type to create. If graph instance, then cleared before populated.
941 Returns
942 -------
943 G : networkx Graph
944 Tutte graph
946 References
947 ----------
948 .. [1] https://en.wikipedia.org/wiki/Tutte_graph
949 """
950 G = nx.from_dict_of_lists(
951 {
952 0: [1, 2, 3],
953 1: [4, 26],
954 2: [10, 11],
955 3: [18, 19],
956 4: [5, 33],
957 5: [6, 29],
958 6: [7, 27],
959 7: [8, 14],
960 8: [9, 38],
961 9: [10, 37],
962 10: [39],
963 11: [12, 39],
964 12: [13, 35],
965 13: [14, 15],
966 14: [34],
967 15: [16, 22],
968 16: [17, 44],
969 17: [18, 43],
970 18: [45],
971 19: [20, 45],
972 20: [21, 41],
973 21: [22, 23],
974 22: [40],
975 23: [24, 27],
976 24: [25, 32],
977 25: [26, 31],
978 26: [33],
979 27: [28],
980 28: [29, 32],
981 29: [30],
982 30: [31, 33],
983 31: [32],
984 34: [35, 38],
985 35: [36],
986 36: [37, 39],
987 37: [38],
988 40: [41, 44],
989 41: [42],
990 42: [43, 45],
991 43: [44],
992 },
993 create_using=create_using,
994 )
995 G.name = "Tutte's Graph"
996 return G