Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/small.py: 39%
171 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
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.
49 """
51 @wraps(func)
52 def wrapper(*args, **kwargs):
53 if kwargs.get("create_using") is not None:
54 G = nx.empty_graph(create_using=kwargs["create_using"])
55 if G.is_directed():
56 raise NetworkXError("Directed Graph not supported")
57 return func(*args, **kwargs)
59 return wrapper
62@nx._dispatch(graphs=None)
63def LCF_graph(n, shift_list, repeats, create_using=None):
64 """
65 Return the cubic graph specified in LCF notation.
67 LCF notation (LCF=Lederberg-Coxeter-Fruchte) is a compressed
68 notation used in the generation of various cubic Hamiltonian
69 graphs of high symmetry. See, for example, dodecahedral_graph,
70 desargues_graph, heawood_graph and pappus_graph below.
72 n (number of nodes)
73 The starting graph is the n-cycle with nodes 0,...,n-1.
74 (The null graph is returned if n < 0.)
76 shift_list = [s1,s2,..,sk], a list of integer shifts mod n,
78 repeats
79 integer specifying the number of times that shifts in shift_list
80 are successively applied to each v_current in the n-cycle
81 to generate an edge between v_current and v_current+shift mod n.
83 For v1 cycling through the n-cycle a total of k*repeats
84 with shift cycling through shiftlist repeats times connect
85 v1 with v1+shift mod n
87 The utility graph $K_{3,3}$
89 >>> G = nx.LCF_graph(6, [3, -3], 3)
91 The Heawood graph
93 >>> G = nx.LCF_graph(14, [5, -5], 7)
95 See http://mathworld.wolfram.com/LCFNotation.html for a description
96 and references.
98 """
99 if n <= 0:
100 return empty_graph(0, create_using)
102 # start with the n-cycle
103 G = cycle_graph(n, create_using)
104 if G.is_directed():
105 raise NetworkXError("Directed Graph not supported")
106 G.name = "LCF_graph"
107 nodes = sorted(G)
109 n_extra_edges = repeats * len(shift_list)
110 # edges are added n_extra_edges times
111 # (not all of these need be new)
112 if n_extra_edges < 1:
113 return G
115 for i in range(n_extra_edges):
116 shift = shift_list[i % len(shift_list)] # cycle through shift_list
117 v1 = nodes[i % n] # cycle repeatedly through nodes
118 v2 = nodes[(i + shift) % n]
119 G.add_edge(v1, v2)
120 return G
123# -------------------------------------------------------------------------------
124# Various small and named graphs
125# -------------------------------------------------------------------------------
128@_raise_on_directed
129@nx._dispatch(graphs=None)
130def bull_graph(create_using=None):
131 """
132 Returns the Bull Graph
134 The Bull Graph has 5 nodes and 5 edges. It is a planar undirected
135 graph in the form of a triangle with two disjoint pendant edges [1]_
136 The name comes from the triangle and pendant edges representing
137 respectively the body and legs of a bull.
139 Parameters
140 ----------
141 create_using : NetworkX graph constructor, optional (default=nx.Graph)
142 Graph type to create. If graph instance, then cleared before populated.
144 Returns
145 -------
146 G : networkx Graph
147 A bull graph with 5 nodes
149 References
150 ----------
151 .. [1] https://en.wikipedia.org/wiki/Bull_graph.
153 """
154 G = nx.from_dict_of_lists(
155 {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 4], 3: [1], 4: [2]},
156 create_using=create_using,
157 )
158 G.name = "Bull Graph"
159 return G
162@_raise_on_directed
163@nx._dispatch(graphs=None)
164def chvatal_graph(create_using=None):
165 """
166 Returns the Chvátal Graph
168 The Chvátal Graph is an undirected graph with 12 nodes and 24 edges [1]_.
169 It has 370 distinct (directed) Hamiltonian cycles, giving a unique generalized
170 LCF notation of order 4, two of order 6 , and 43 of order 1 [2]_.
172 Parameters
173 ----------
174 create_using : NetworkX graph constructor, optional (default=nx.Graph)
175 Graph type to create. If graph instance, then cleared before populated.
177 Returns
178 -------
179 G : networkx Graph
180 The Chvátal graph with 12 nodes and 24 edges
182 References
183 ----------
184 .. [1] https://en.wikipedia.org/wiki/Chv%C3%A1tal_graph
185 .. [2] https://mathworld.wolfram.com/ChvatalGraph.html
187 """
188 G = nx.from_dict_of_lists(
189 {
190 0: [1, 4, 6, 9],
191 1: [2, 5, 7],
192 2: [3, 6, 8],
193 3: [4, 7, 9],
194 4: [5, 8],
195 5: [10, 11],
196 6: [10, 11],
197 7: [8, 11],
198 8: [10],
199 9: [10, 11],
200 },
201 create_using=create_using,
202 )
203 G.name = "Chvatal Graph"
204 return G
207@_raise_on_directed
208@nx._dispatch(graphs=None)
209def cubical_graph(create_using=None):
210 """
211 Returns the 3-regular Platonic Cubical Graph
213 The skeleton of the cube (the nodes and edges) form a graph, with 8
214 nodes, and 12 edges. It is a special case of the hypercube graph.
215 It is one of 5 Platonic graphs, each a skeleton of its
216 Platonic solid [1]_.
217 Such graphs arise in parallel processing in computers.
219 Parameters
220 ----------
221 create_using : NetworkX graph constructor, optional (default=nx.Graph)
222 Graph type to create. If graph instance, then cleared before populated.
224 Returns
225 -------
226 G : networkx Graph
227 A cubical graph with 8 nodes and 12 edges
229 References
230 ----------
231 .. [1] https://en.wikipedia.org/wiki/Cube#Cubical_graph
233 """
234 G = nx.from_dict_of_lists(
235 {
236 0: [1, 3, 4],
237 1: [0, 2, 7],
238 2: [1, 3, 6],
239 3: [0, 2, 5],
240 4: [0, 5, 7],
241 5: [3, 4, 6],
242 6: [2, 5, 7],
243 7: [1, 4, 6],
244 },
245 create_using=create_using,
246 )
247 G.name = ("Platonic Cubical Graph",)
248 return G
251@nx._dispatch(graphs=None)
252def desargues_graph(create_using=None):
253 """
254 Returns the Desargues Graph
256 The Desargues Graph is a non-planar, distance-transitive cubic graph
257 with 20 nodes and 30 edges [1]_.
258 It is a symmetric graph. It can be represented in LCF notation
259 as [5,-5,9,-9]^5 [2]_.
261 Parameters
262 ----------
263 create_using : NetworkX graph constructor, optional (default=nx.Graph)
264 Graph type to create. If graph instance, then cleared before populated.
266 Returns
267 -------
268 G : networkx Graph
269 Desargues Graph with 20 nodes and 30 edges
271 References
272 ----------
273 .. [1] https://en.wikipedia.org/wiki/Desargues_graph
274 .. [2] https://mathworld.wolfram.com/DesarguesGraph.html
275 """
276 G = LCF_graph(20, [5, -5, 9, -9], 5, create_using)
277 G.name = "Desargues Graph"
278 return G
281@_raise_on_directed
282@nx._dispatch(graphs=None)
283def diamond_graph(create_using=None):
284 """
285 Returns the Diamond graph
287 The Diamond Graph is planar undirected graph with 4 nodes and 5 edges.
288 It is also sometimes known as the double triangle graph or kite graph [1]_.
290 Parameters
291 ----------
292 create_using : NetworkX graph constructor, optional (default=nx.Graph)
293 Graph type to create. If graph instance, then cleared before populated.
295 Returns
296 -------
297 G : networkx Graph
298 Diamond Graph with 4 nodes and 5 edges
300 References
301 ----------
302 .. [1] https://mathworld.wolfram.com/DiamondGraph.html
303 """
304 G = nx.from_dict_of_lists(
305 {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 3], 3: [1, 2]}, create_using=create_using
306 )
307 G.name = "Diamond Graph"
308 return G
311@nx._dispatch(graphs=None)
312def dodecahedral_graph(create_using=None):
313 """
314 Returns the Platonic Dodecahedral graph.
316 The dodecahedral graph has 20 nodes and 30 edges. The skeleton of the
317 dodecahedron forms a graph. It is one of 5 Platonic graphs [1]_.
318 It can be described in LCF notation as:
319 ``[10, 7, 4, -4, -7, 10, -4, 7, -7, 4]^2`` [2]_.
321 Parameters
322 ----------
323 create_using : NetworkX graph constructor, optional (default=nx.Graph)
324 Graph type to create. If graph instance, then cleared before populated.
326 Returns
327 -------
328 G : networkx Graph
329 Dodecahedral Graph with 20 nodes and 30 edges
331 References
332 ----------
333 .. [1] https://en.wikipedia.org/wiki/Regular_dodecahedron#Dodecahedral_graph
334 .. [2] https://mathworld.wolfram.com/DodecahedralGraph.html
336 """
337 G = LCF_graph(20, [10, 7, 4, -4, -7, 10, -4, 7, -7, 4], 2, create_using)
338 G.name = "Dodecahedral Graph"
339 return G
342@nx._dispatch(graphs=None)
343def frucht_graph(create_using=None):
344 """
345 Returns the Frucht Graph.
347 The Frucht Graph is the smallest cubical graph whose
348 automorphism group consists only of the identity element [1]_.
349 It has 12 nodes and 18 edges and no nontrivial symmetries.
350 It is planar and Hamiltonian [2]_.
352 Parameters
353 ----------
354 create_using : NetworkX graph constructor, optional (default=nx.Graph)
355 Graph type to create. If graph instance, then cleared before populated.
357 Returns
358 -------
359 G : networkx Graph
360 Frucht Graph with 12 nodes and 18 edges
362 References
363 ----------
364 .. [1] https://en.wikipedia.org/wiki/Frucht_graph
365 .. [2] https://mathworld.wolfram.com/FruchtGraph.html
367 """
368 G = cycle_graph(7, create_using)
369 G.add_edges_from(
370 [
371 [0, 7],
372 [1, 7],
373 [2, 8],
374 [3, 9],
375 [4, 9],
376 [5, 10],
377 [6, 10],
378 [7, 11],
379 [8, 11],
380 [8, 9],
381 [10, 11],
382 ]
383 )
385 G.name = "Frucht Graph"
386 return G
389@nx._dispatch(graphs=None)
390def heawood_graph(create_using=None):
391 """
392 Returns the Heawood Graph, a (3,6) cage.
394 The Heawood Graph is an undirected graph with 14 nodes and 21 edges,
395 named after Percy John Heawood [1]_.
396 It is cubic symmetric, nonplanar, Hamiltonian, and can be represented
397 in LCF notation as ``[5,-5]^7`` [2]_.
398 It is the unique (3,6)-cage: the regular cubic graph of girth 6 with
399 minimal number of vertices [3]_.
401 Parameters
402 ----------
403 create_using : NetworkX graph constructor, optional (default=nx.Graph)
404 Graph type to create. If graph instance, then cleared before populated.
406 Returns
407 -------
408 G : networkx Graph
409 Heawood Graph with 14 nodes and 21 edges
411 References
412 ----------
413 .. [1] https://en.wikipedia.org/wiki/Heawood_graph
414 .. [2] https://mathworld.wolfram.com/HeawoodGraph.html
415 .. [3] https://www.win.tue.nl/~aeb/graphs/Heawood.html
417 """
418 G = LCF_graph(14, [5, -5], 7, create_using)
419 G.name = "Heawood Graph"
420 return G
423@nx._dispatch(graphs=None)
424def hoffman_singleton_graph():
425 """
426 Returns the Hoffman-Singleton Graph.
428 The Hoffman–Singleton graph is a symmetrical undirected graph
429 with 50 nodes and 175 edges.
430 All indices lie in ``Z % 5``: that is, the integers mod 5 [1]_.
431 It is the only regular graph of vertex degree 7, diameter 2, and girth 5.
432 It is the unique (7,5)-cage graph and Moore graph, and contains many
433 copies of the Petersen graph [2]_.
435 Returns
436 -------
437 G : networkx Graph
438 Hoffman–Singleton Graph with 50 nodes and 175 edges
440 Notes
441 -----
442 Constructed from pentagon and pentagram as follows: Take five pentagons $P_h$
443 and five pentagrams $Q_i$ . Join vertex $j$ of $P_h$ to vertex $h·i+j$ of $Q_i$ [3]_.
445 References
446 ----------
447 .. [1] https://blogs.ams.org/visualinsight/2016/02/01/hoffman-singleton-graph/
448 .. [2] https://mathworld.wolfram.com/Hoffman-SingletonGraph.html
449 .. [3] https://en.wikipedia.org/wiki/Hoffman%E2%80%93Singleton_graph
451 """
452 G = nx.Graph()
453 for i in range(5):
454 for j in range(5):
455 G.add_edge(("pentagon", i, j), ("pentagon", i, (j - 1) % 5))
456 G.add_edge(("pentagon", i, j), ("pentagon", i, (j + 1) % 5))
457 G.add_edge(("pentagram", i, j), ("pentagram", i, (j - 2) % 5))
458 G.add_edge(("pentagram", i, j), ("pentagram", i, (j + 2) % 5))
459 for k in range(5):
460 G.add_edge(("pentagon", i, j), ("pentagram", k, (i * k + j) % 5))
461 G = nx.convert_node_labels_to_integers(G)
462 G.name = "Hoffman-Singleton Graph"
463 return G
466@_raise_on_directed
467@nx._dispatch(graphs=None)
468def house_graph(create_using=None):
469 """
470 Returns the House graph (square with triangle on top)
472 The house graph is a simple undirected graph with
473 5 nodes and 6 edges [1]_.
475 Parameters
476 ----------
477 create_using : NetworkX graph constructor, optional (default=nx.Graph)
478 Graph type to create. If graph instance, then cleared before populated.
480 Returns
481 -------
482 G : networkx Graph
483 House graph in the form of a square with a triangle on top
485 References
486 ----------
487 .. [1] https://mathworld.wolfram.com/HouseGraph.html
488 """
489 G = nx.from_dict_of_lists(
490 {0: [1, 2], 1: [0, 3], 2: [0, 3, 4], 3: [1, 2, 4], 4: [2, 3]},
491 create_using=create_using,
492 )
493 G.name = "House Graph"
494 return G
497@_raise_on_directed
498@nx._dispatch(graphs=None)
499def house_x_graph(create_using=None):
500 """
501 Returns the House graph with a cross inside the house square.
503 The House X-graph is the House graph plus the two edges connecting diagonally
504 opposite vertices of the square base. It is also one of the two graphs
505 obtained by removing two edges from the pentatope graph [1]_.
507 Parameters
508 ----------
509 create_using : NetworkX graph constructor, optional (default=nx.Graph)
510 Graph type to create. If graph instance, then cleared before populated.
512 Returns
513 -------
514 G : networkx Graph
515 House graph with diagonal vertices connected
517 References
518 ----------
519 .. [1] https://mathworld.wolfram.com/HouseGraph.html
520 """
521 G = house_graph(create_using)
522 G.add_edges_from([(0, 3), (1, 2)])
523 G.name = "House-with-X-inside Graph"
524 return G
527@_raise_on_directed
528@nx._dispatch(graphs=None)
529def icosahedral_graph(create_using=None):
530 """
531 Returns the Platonic Icosahedral graph.
533 The icosahedral graph has 12 nodes and 30 edges. It is a Platonic graph
534 whose nodes have the connectivity of the icosahedron. It is undirected,
535 regular and Hamiltonian [1]_.
537 Parameters
538 ----------
539 create_using : NetworkX graph constructor, optional (default=nx.Graph)
540 Graph type to create. If graph instance, then cleared before populated.
542 Returns
543 -------
544 G : networkx Graph
545 Icosahedral graph with 12 nodes and 30 edges.
547 References
548 ----------
549 .. [1] https://mathworld.wolfram.com/IcosahedralGraph.html
550 """
551 G = nx.from_dict_of_lists(
552 {
553 0: [1, 5, 7, 8, 11],
554 1: [2, 5, 6, 8],
555 2: [3, 6, 8, 9],
556 3: [4, 6, 9, 10],
557 4: [5, 6, 10, 11],
558 5: [6, 11],
559 7: [8, 9, 10, 11],
560 8: [9],
561 9: [10],
562 10: [11],
563 },
564 create_using=create_using,
565 )
566 G.name = "Platonic Icosahedral Graph"
567 return G
570@_raise_on_directed
571@nx._dispatch(graphs=None)
572def krackhardt_kite_graph(create_using=None):
573 """
574 Returns the Krackhardt Kite Social Network.
576 A 10 actor social network introduced by David Krackhardt
577 to illustrate different centrality measures [1]_.
579 Parameters
580 ----------
581 create_using : NetworkX graph constructor, optional (default=nx.Graph)
582 Graph type to create. If graph instance, then cleared before populated.
584 Returns
585 -------
586 G : networkx Graph
587 Krackhardt Kite graph with 10 nodes and 18 edges
589 Notes
590 -----
591 The traditional labeling is:
592 Andre=1, Beverley=2, Carol=3, Diane=4,
593 Ed=5, Fernando=6, Garth=7, Heather=8, Ike=9, Jane=10.
595 References
596 ----------
597 .. [1] Krackhardt, David. "Assessing the Political Landscape: Structure,
598 Cognition, and Power in Organizations". Administrative Science Quarterly.
599 35 (2): 342–369. doi:10.2307/2393394. JSTOR 2393394. June 1990.
601 """
602 G = nx.from_dict_of_lists(
603 {
604 0: [1, 2, 3, 5],
605 1: [0, 3, 4, 6],
606 2: [0, 3, 5],
607 3: [0, 1, 2, 4, 5, 6],
608 4: [1, 3, 6],
609 5: [0, 2, 3, 6, 7],
610 6: [1, 3, 4, 5, 7],
611 7: [5, 6, 8],
612 8: [7, 9],
613 9: [8],
614 },
615 create_using=create_using,
616 )
617 G.name = "Krackhardt Kite Social Network"
618 return G
621@nx._dispatch(graphs=None)
622def moebius_kantor_graph(create_using=None):
623 """
624 Returns the Moebius-Kantor graph.
626 The Möbius-Kantor graph is the cubic symmetric graph on 16 nodes.
627 Its LCF notation is [5,-5]^8, and it is isomorphic to the generalized
628 Petersen graph [1]_.
630 Parameters
631 ----------
632 create_using : NetworkX graph constructor, optional (default=nx.Graph)
633 Graph type to create. If graph instance, then cleared before populated.
635 Returns
636 -------
637 G : networkx Graph
638 Moebius-Kantor graph
640 References
641 ----------
642 .. [1] https://en.wikipedia.org/wiki/M%C3%B6bius%E2%80%93Kantor_graph
644 """
645 G = LCF_graph(16, [5, -5], 8, create_using)
646 G.name = "Moebius-Kantor Graph"
647 return G
650@_raise_on_directed
651@nx._dispatch(graphs=None)
652def octahedral_graph(create_using=None):
653 """
654 Returns the Platonic Octahedral graph.
656 The octahedral graph is the 6-node 12-edge Platonic graph having the
657 connectivity of the octahedron [1]_. If 6 couples go to a party,
658 and each person shakes hands with every person except his or her partner,
659 then this graph describes the set of handshakes that take place;
660 for this reason it is also called the cocktail party graph [2]_.
662 Parameters
663 ----------
664 create_using : NetworkX graph constructor, optional (default=nx.Graph)
665 Graph type to create. If graph instance, then cleared before populated.
667 Returns
668 -------
669 G : networkx Graph
670 Octahedral graph
672 References
673 ----------
674 .. [1] https://mathworld.wolfram.com/OctahedralGraph.html
675 .. [2] https://en.wikipedia.org/wiki/Tur%C3%A1n_graph#Special_cases
677 """
678 G = nx.from_dict_of_lists(
679 {0: [1, 2, 3, 4], 1: [2, 3, 5], 2: [4, 5], 3: [4, 5], 4: [5]},
680 create_using=create_using,
681 )
682 G.name = "Platonic Octahedral Graph"
683 return G
686@nx._dispatch(graphs=None)
687def pappus_graph():
688 """
689 Returns the Pappus graph.
691 The Pappus graph is a cubic symmetric distance-regular graph with 18 nodes
692 and 27 edges. It is Hamiltonian and can be represented in LCF notation as
693 [5,7,-7,7,-7,-5]^3 [1]_.
695 Returns
696 -------
697 G : networkx Graph
698 Pappus graph
700 References
701 ----------
702 .. [1] https://en.wikipedia.org/wiki/Pappus_graph
703 """
704 G = LCF_graph(18, [5, 7, -7, 7, -7, -5], 3)
705 G.name = "Pappus Graph"
706 return G
709@_raise_on_directed
710@nx._dispatch(graphs=None)
711def petersen_graph(create_using=None):
712 """
713 Returns the Petersen graph.
715 The Peterson graph is a cubic, undirected graph with 10 nodes and 15 edges [1]_.
716 Julius Petersen constructed the graph as the smallest counterexample
717 against the claim that a connected bridgeless cubic graph
718 has an edge colouring with three colours [2]_.
720 Parameters
721 ----------
722 create_using : NetworkX graph constructor, optional (default=nx.Graph)
723 Graph type to create. If graph instance, then cleared before populated.
725 Returns
726 -------
727 G : networkx Graph
728 Petersen graph
730 References
731 ----------
732 .. [1] https://en.wikipedia.org/wiki/Petersen_graph
733 .. [2] https://www.win.tue.nl/~aeb/drg/graphs/Petersen.html
734 """
735 G = nx.from_dict_of_lists(
736 {
737 0: [1, 4, 5],
738 1: [0, 2, 6],
739 2: [1, 3, 7],
740 3: [2, 4, 8],
741 4: [3, 0, 9],
742 5: [0, 7, 8],
743 6: [1, 8, 9],
744 7: [2, 5, 9],
745 8: [3, 5, 6],
746 9: [4, 6, 7],
747 },
748 create_using=create_using,
749 )
750 G.name = "Petersen Graph"
751 return G
754@nx._dispatch(graphs=None)
755def sedgewick_maze_graph(create_using=None):
756 """
757 Return a small maze with a cycle.
759 This is the maze used in Sedgewick, 3rd Edition, Part 5, Graph
760 Algorithms, Chapter 18, e.g. Figure 18.2 and following [1]_.
761 Nodes are numbered 0,..,7
763 Parameters
764 ----------
765 create_using : NetworkX graph constructor, optional (default=nx.Graph)
766 Graph type to create. If graph instance, then cleared before populated.
768 Returns
769 -------
770 G : networkx Graph
771 Small maze with a cycle
773 References
774 ----------
775 .. [1] Figure 18.2, Chapter 18, Graph Algorithms (3rd Ed), Sedgewick
776 """
777 G = empty_graph(0, create_using)
778 G.add_nodes_from(range(8))
779 G.add_edges_from([[0, 2], [0, 7], [0, 5]])
780 G.add_edges_from([[1, 7], [2, 6]])
781 G.add_edges_from([[3, 4], [3, 5]])
782 G.add_edges_from([[4, 5], [4, 7], [4, 6]])
783 G.name = "Sedgewick Maze"
784 return G
787@nx._dispatch(graphs=None)
788def tetrahedral_graph(create_using=None):
789 """
790 Returns the 3-regular Platonic Tetrahedral graph.
792 Tetrahedral graph has 4 nodes and 6 edges. It is a
793 special case of the complete graph, K4, and wheel graph, W4.
794 It is one of the 5 platonic graphs [1]_.
796 Parameters
797 ----------
798 create_using : NetworkX graph constructor, optional (default=nx.Graph)
799 Graph type to create. If graph instance, then cleared before populated.
801 Returns
802 -------
803 G : networkx Graph
804 Tetrahedral Graph
806 References
807 ----------
808 .. [1] https://en.wikipedia.org/wiki/Tetrahedron#Tetrahedral_graph
810 """
811 G = complete_graph(4, create_using)
812 G.name = "Platonic Tetrahedral graph"
813 return G
816@_raise_on_directed
817@nx._dispatch(graphs=None)
818def truncated_cube_graph(create_using=None):
819 """
820 Returns the skeleton of the truncated cube.
822 The truncated cube is an Archimedean solid with 14 regular
823 faces (6 octagonal and 8 triangular), 36 edges and 24 nodes [1]_.
824 The truncated cube is created by truncating (cutting off) the tips
825 of the cube one third of the way into each edge [2]_.
827 Parameters
828 ----------
829 create_using : NetworkX graph constructor, optional (default=nx.Graph)
830 Graph type to create. If graph instance, then cleared before populated.
832 Returns
833 -------
834 G : networkx Graph
835 Skeleton of the truncated cube
837 References
838 ----------
839 .. [1] https://en.wikipedia.org/wiki/Truncated_cube
840 .. [2] https://www.coolmath.com/reference/polyhedra-truncated-cube
842 """
843 G = nx.from_dict_of_lists(
844 {
845 0: [1, 2, 4],
846 1: [11, 14],
847 2: [3, 4],
848 3: [6, 8],
849 4: [5],
850 5: [16, 18],
851 6: [7, 8],
852 7: [10, 12],
853 8: [9],
854 9: [17, 20],
855 10: [11, 12],
856 11: [14],
857 12: [13],
858 13: [21, 22],
859 14: [15],
860 15: [19, 23],
861 16: [17, 18],
862 17: [20],
863 18: [19],
864 19: [23],
865 20: [21],
866 21: [22],
867 22: [23],
868 },
869 create_using=create_using,
870 )
871 G.name = "Truncated Cube Graph"
872 return G
875@nx._dispatch(graphs=None)
876def truncated_tetrahedron_graph(create_using=None):
877 """
878 Returns the skeleton of the truncated Platonic tetrahedron.
880 The truncated tetrahedron is an Archimedean solid with 4 regular hexagonal faces,
881 4 equilateral triangle faces, 12 nodes and 18 edges. It can be constructed by truncating
882 all 4 vertices of a regular tetrahedron at one third of the original edge length [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 Skeleton of the truncated tetrahedron
894 References
895 ----------
896 .. [1] https://en.wikipedia.org/wiki/Truncated_tetrahedron
898 """
899 G = path_graph(12, create_using)
900 G.add_edges_from([(0, 2), (0, 9), (1, 6), (3, 11), (4, 11), (5, 7), (8, 10)])
901 G.name = "Truncated Tetrahedron Graph"
902 return G
905@_raise_on_directed
906@nx._dispatch(graphs=None)
907def tutte_graph(create_using=None):
908 """
909 Returns the Tutte graph.
911 The Tutte graph is a cubic polyhedral, non-Hamiltonian graph. It has
912 46 nodes and 69 edges.
913 It is a counterexample to Tait's conjecture that every 3-regular polyhedron
914 has a Hamiltonian cycle.
915 It can be realized geometrically from a tetrahedron by multiply truncating
916 three of its vertices [1]_.
918 Parameters
919 ----------
920 create_using : NetworkX graph constructor, optional (default=nx.Graph)
921 Graph type to create. If graph instance, then cleared before populated.
923 Returns
924 -------
925 G : networkx Graph
926 Tutte graph
928 References
929 ----------
930 .. [1] https://en.wikipedia.org/wiki/Tutte_graph
931 """
932 G = nx.from_dict_of_lists(
933 {
934 0: [1, 2, 3],
935 1: [4, 26],
936 2: [10, 11],
937 3: [18, 19],
938 4: [5, 33],
939 5: [6, 29],
940 6: [7, 27],
941 7: [8, 14],
942 8: [9, 38],
943 9: [10, 37],
944 10: [39],
945 11: [12, 39],
946 12: [13, 35],
947 13: [14, 15],
948 14: [34],
949 15: [16, 22],
950 16: [17, 44],
951 17: [18, 43],
952 18: [45],
953 19: [20, 45],
954 20: [21, 41],
955 21: [22, 23],
956 22: [40],
957 23: [24, 27],
958 24: [25, 32],
959 25: [26, 31],
960 26: [33],
961 27: [28],
962 28: [29, 32],
963 29: [30],
964 30: [31, 33],
965 31: [32],
966 34: [35, 38],
967 35: [36],
968 36: [37, 39],
969 37: [38],
970 40: [41, 44],
971 41: [42],
972 42: [43, 45],
973 43: [44],
974 },
975 create_using=create_using,
976 )
977 G.name = "Tutte's Graph"
978 return G