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 See Also
248 --------
249 tetrahedral_graph, octahedral_graph, dodecahedral_graph, icosahedral_graph
251 References
252 ----------
253 .. [1] https://en.wikipedia.org/wiki/Cube#Cubical_graph
255 """
256 G = nx.from_dict_of_lists(
257 {
258 0: [1, 3, 4],
259 1: [0, 2, 7],
260 2: [1, 3, 6],
261 3: [0, 2, 5],
262 4: [0, 5, 7],
263 5: [3, 4, 6],
264 6: [2, 5, 7],
265 7: [1, 4, 6],
266 },
267 create_using=create_using,
268 )
269 G.name = "Platonic Cubical Graph"
270 return G
273@nx._dispatchable(graphs=None, returns_graph=True)
274def desargues_graph(create_using=None):
275 """
276 Returns the Desargues Graph
278 The Desargues Graph is a non-planar, distance-transitive cubic graph
279 with 20 nodes and 30 edges [1]_.
280 It is a symmetric graph. It can be represented in LCF notation
281 as [5,-5,9,-9]^5 [2]_.
283 Parameters
284 ----------
285 create_using : NetworkX graph constructor, optional (default=nx.Graph)
286 Graph type to create. If graph instance, then cleared before populated.
288 Returns
289 -------
290 G : networkx Graph
291 Desargues Graph with 20 nodes and 30 edges
293 References
294 ----------
295 .. [1] https://en.wikipedia.org/wiki/Desargues_graph
296 .. [2] https://mathworld.wolfram.com/DesarguesGraph.html
297 """
298 G = LCF_graph(20, [5, -5, 9, -9], 5, create_using)
299 G.name = "Desargues Graph"
300 return G
303@_raise_on_directed
304@nx._dispatchable(graphs=None, returns_graph=True)
305def diamond_graph(create_using=None):
306 """
307 Returns the Diamond graph
309 The Diamond Graph is planar undirected graph with 4 nodes and 5 edges.
310 It is also sometimes known as the double triangle graph or kite graph [1]_.
312 Parameters
313 ----------
314 create_using : NetworkX graph constructor, optional (default=nx.Graph)
315 Graph type to create. If graph instance, then cleared before populated.
317 Returns
318 -------
319 G : networkx Graph
320 Diamond Graph with 4 nodes and 5 edges
322 References
323 ----------
324 .. [1] https://mathworld.wolfram.com/DiamondGraph.html
325 """
326 G = nx.from_dict_of_lists(
327 {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 3], 3: [1, 2]}, create_using=create_using
328 )
329 G.name = "Diamond Graph"
330 return G
333@nx._dispatchable(graphs=None, returns_graph=True)
334def dodecahedral_graph(create_using=None):
335 """
336 Returns the Platonic Dodecahedral graph.
338 The dodecahedral graph has 20 nodes and 30 edges. The skeleton of the
339 dodecahedron forms a graph. It is one of 5 Platonic graphs [1]_.
340 It can be described in LCF notation as:
341 ``[10, 7, 4, -4, -7, 10, -4, 7, -7, 4]^2`` [2]_.
343 Parameters
344 ----------
345 create_using : NetworkX graph constructor, optional (default=nx.Graph)
346 Graph type to create. If graph instance, then cleared before populated.
348 Returns
349 -------
350 G : networkx Graph
351 Dodecahedral Graph with 20 nodes and 30 edges
353 See Also
354 --------
355 tetrahedral_graph, cubical_graph, octahedral_graph, icosahedral_graph
357 References
358 ----------
359 .. [1] https://en.wikipedia.org/wiki/Regular_dodecahedron#Dodecahedral_graph
360 .. [2] https://mathworld.wolfram.com/DodecahedralGraph.html
362 """
363 G = LCF_graph(20, [10, 7, 4, -4, -7, 10, -4, 7, -7, 4], 2, create_using)
364 G.name = "Dodecahedral Graph"
365 return G
368@nx._dispatchable(graphs=None, returns_graph=True)
369def frucht_graph(create_using=None):
370 """
371 Returns the Frucht Graph.
373 The Frucht Graph is the smallest cubical graph whose
374 automorphism group consists only of the identity element [1]_.
375 It has 12 nodes and 18 edges and no nontrivial symmetries.
376 It is planar and Hamiltonian [2]_.
378 Parameters
379 ----------
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 : networkx Graph
386 Frucht Graph with 12 nodes and 18 edges
388 References
389 ----------
390 .. [1] https://en.wikipedia.org/wiki/Frucht_graph
391 .. [2] https://mathworld.wolfram.com/FruchtGraph.html
393 """
394 G = cycle_graph(7, create_using)
395 G.add_edges_from(
396 [
397 [0, 7],
398 [1, 7],
399 [2, 8],
400 [3, 9],
401 [4, 9],
402 [5, 10],
403 [6, 10],
404 [7, 11],
405 [8, 11],
406 [8, 9],
407 [10, 11],
408 ]
409 )
411 G.name = "Frucht Graph"
412 return G
415@nx._dispatchable(graphs=None, returns_graph=True)
416def heawood_graph(create_using=None):
417 """
418 Returns the Heawood Graph, a (3,6) cage.
420 The Heawood Graph is an undirected graph with 14 nodes and 21 edges,
421 named after Percy John Heawood [1]_.
422 It is cubic symmetric, nonplanar, Hamiltonian, and can be represented
423 in LCF notation as ``[5,-5]^7`` [2]_.
424 It is the unique (3,6)-cage: the regular cubic graph of girth 6 with
425 minimal number of vertices [3]_.
427 Parameters
428 ----------
429 create_using : NetworkX graph constructor, optional (default=nx.Graph)
430 Graph type to create. If graph instance, then cleared before populated.
432 Returns
433 -------
434 G : networkx Graph
435 Heawood Graph with 14 nodes and 21 edges
437 References
438 ----------
439 .. [1] https://en.wikipedia.org/wiki/Heawood_graph
440 .. [2] https://mathworld.wolfram.com/HeawoodGraph.html
441 .. [3] https://www.win.tue.nl/~aeb/graphs/Heawood.html
443 """
444 G = LCF_graph(14, [5, -5], 7, create_using)
445 G.name = "Heawood Graph"
446 return G
449@nx._dispatchable(graphs=None, returns_graph=True)
450def hoffman_singleton_graph():
451 """
452 Returns the Hoffman-Singleton Graph.
454 The Hoffman–Singleton graph is a symmetrical undirected graph
455 with 50 nodes and 175 edges.
456 All indices lie in ``Z % 5``: that is, the integers mod 5 [1]_.
457 It is the only regular graph of vertex degree 7, diameter 2, and girth 5.
458 It is the unique (7,5)-cage graph and Moore graph, and contains many
459 copies of the Petersen graph [2]_.
461 Returns
462 -------
463 G : networkx Graph
464 Hoffman–Singleton Graph with 50 nodes and 175 edges
466 Notes
467 -----
468 Constructed from pentagon and pentagram as follows: Take five pentagons $P_h$
469 and five pentagrams $Q_i$ . Join vertex $j$ of $P_h$ to vertex $h·i+j$ of $Q_i$ [3]_.
471 References
472 ----------
473 .. [1] https://blogs.ams.org/visualinsight/2016/02/01/hoffman-singleton-graph/
474 .. [2] https://mathworld.wolfram.com/Hoffman-SingletonGraph.html
475 .. [3] https://en.wikipedia.org/wiki/Hoffman%E2%80%93Singleton_graph
477 """
478 G = nx.Graph()
479 for i in range(5):
480 for j in range(5):
481 G.add_edge(("pentagon", i, j), ("pentagon", i, (j - 1) % 5))
482 G.add_edge(("pentagon", i, j), ("pentagon", i, (j + 1) % 5))
483 G.add_edge(("pentagram", i, j), ("pentagram", i, (j - 2) % 5))
484 G.add_edge(("pentagram", i, j), ("pentagram", i, (j + 2) % 5))
485 for k in range(5):
486 G.add_edge(("pentagon", i, j), ("pentagram", k, (i * k + j) % 5))
487 G = nx.convert_node_labels_to_integers(G)
488 G.name = "Hoffman-Singleton Graph"
489 return G
492@_raise_on_directed
493@nx._dispatchable(graphs=None, returns_graph=True)
494def house_graph(create_using=None):
495 """
496 Returns the House graph (square with triangle on top)
498 The house graph is a simple undirected graph with
499 5 nodes and 6 edges [1]_.
501 Parameters
502 ----------
503 create_using : NetworkX graph constructor, optional (default=nx.Graph)
504 Graph type to create. If graph instance, then cleared before populated.
506 Returns
507 -------
508 G : networkx Graph
509 House graph in the form of a square with a triangle on top
511 References
512 ----------
513 .. [1] https://mathworld.wolfram.com/HouseGraph.html
514 """
515 G = nx.from_dict_of_lists(
516 {0: [1, 2], 1: [0, 3], 2: [0, 3, 4], 3: [1, 2, 4], 4: [2, 3]},
517 create_using=create_using,
518 )
519 G.name = "House Graph"
520 return G
523@_raise_on_directed
524@nx._dispatchable(graphs=None, returns_graph=True)
525def house_x_graph(create_using=None):
526 """
527 Returns the House graph with a cross inside the house square.
529 The House X-graph is the House graph plus the two edges connecting diagonally
530 opposite vertices of the square base. It is also one of the two graphs
531 obtained by removing two edges from the pentatope graph [1]_.
533 Parameters
534 ----------
535 create_using : NetworkX graph constructor, optional (default=nx.Graph)
536 Graph type to create. If graph instance, then cleared before populated.
538 Returns
539 -------
540 G : networkx Graph
541 House graph with diagonal vertices connected
543 References
544 ----------
545 .. [1] https://mathworld.wolfram.com/HouseGraph.html
546 """
547 G = house_graph(create_using)
548 G.add_edges_from([(0, 3), (1, 2)])
549 G.name = "House-with-X-inside Graph"
550 return G
553@_raise_on_directed
554@nx._dispatchable(graphs=None, returns_graph=True)
555def icosahedral_graph(create_using=None):
556 """
557 Returns the Platonic Icosahedral graph.
559 The icosahedral graph has 12 nodes and 30 edges. It is a Platonic graph
560 whose nodes have the connectivity of the icosahedron. It is undirected,
561 regular and Hamiltonian [1]_.
563 Parameters
564 ----------
565 create_using : NetworkX graph constructor, optional (default=nx.Graph)
566 Graph type to create. If graph instance, then cleared before populated.
568 Returns
569 -------
570 G : networkx Graph
571 Icosahedral graph with 12 nodes and 30 edges.
573 See Also
574 --------
575 tetrahedral_graph, cubical_graph, octahedral_graph, dodecahedral_graph
577 References
578 ----------
579 .. [1] https://mathworld.wolfram.com/IcosahedralGraph.html
580 """
581 G = nx.from_dict_of_lists(
582 {
583 0: [1, 5, 7, 8, 11],
584 1: [2, 5, 6, 8],
585 2: [3, 6, 8, 9],
586 3: [4, 6, 9, 10],
587 4: [5, 6, 10, 11],
588 5: [6, 11],
589 7: [8, 9, 10, 11],
590 8: [9],
591 9: [10],
592 10: [11],
593 },
594 create_using=create_using,
595 )
596 G.name = "Platonic Icosahedral Graph"
597 return G
600@_raise_on_directed
601@nx._dispatchable(graphs=None, returns_graph=True)
602def krackhardt_kite_graph(create_using=None):
603 """
604 Returns the Krackhardt Kite Social Network.
606 A 10 actor social network introduced by David Krackhardt
607 to illustrate different centrality measures [1]_.
609 Parameters
610 ----------
611 create_using : NetworkX graph constructor, optional (default=nx.Graph)
612 Graph type to create. If graph instance, then cleared before populated.
614 Returns
615 -------
616 G : networkx Graph
617 Krackhardt Kite graph with 10 nodes and 18 edges
619 Notes
620 -----
621 The traditional labeling is:
622 Andre=1, Beverley=2, Carol=3, Diane=4,
623 Ed=5, Fernando=6, Garth=7, Heather=8, Ike=9, Jane=10.
625 References
626 ----------
627 .. [1] Krackhardt, David. "Assessing the Political Landscape: Structure,
628 Cognition, and Power in Organizations". Administrative Science Quarterly.
629 35 (2): 342–369. doi:10.2307/2393394. JSTOR 2393394. June 1990.
631 """
632 G = nx.from_dict_of_lists(
633 {
634 0: [1, 2, 3, 5],
635 1: [0, 3, 4, 6],
636 2: [0, 3, 5],
637 3: [0, 1, 2, 4, 5, 6],
638 4: [1, 3, 6],
639 5: [0, 2, 3, 6, 7],
640 6: [1, 3, 4, 5, 7],
641 7: [5, 6, 8],
642 8: [7, 9],
643 9: [8],
644 },
645 create_using=create_using,
646 )
647 G.name = "Krackhardt Kite Social Network"
648 return G
651@nx._dispatchable(graphs=None, returns_graph=True)
652def moebius_kantor_graph(create_using=None):
653 """
654 Returns the Moebius-Kantor graph.
656 The Möbius-Kantor graph is the cubic symmetric graph on 16 nodes.
657 Its LCF notation is [5,-5]^8, and it is isomorphic to the generalized
658 Petersen graph [1]_.
660 Parameters
661 ----------
662 create_using : NetworkX graph constructor, optional (default=nx.Graph)
663 Graph type to create. If graph instance, then cleared before populated.
665 Returns
666 -------
667 G : networkx Graph
668 Moebius-Kantor graph
670 References
671 ----------
672 .. [1] https://en.wikipedia.org/wiki/M%C3%B6bius%E2%80%93Kantor_graph
674 """
675 G = LCF_graph(16, [5, -5], 8, create_using)
676 G.name = "Moebius-Kantor Graph"
677 return G
680@_raise_on_directed
681@nx._dispatchable(graphs=None, returns_graph=True)
682def octahedral_graph(create_using=None):
683 """
684 Returns the Platonic Octahedral graph.
686 The octahedral graph is the 6-node 12-edge Platonic graph having the
687 connectivity of the octahedron [1]_. If 6 couples go to a party,
688 and each person shakes hands with every person except his or her partner,
689 then this graph describes the set of handshakes that take place;
690 for this reason it is also called the cocktail party graph [2]_.
692 Parameters
693 ----------
694 create_using : NetworkX graph constructor, optional (default=nx.Graph)
695 Graph type to create. If graph instance, then cleared before populated.
697 Returns
698 -------
699 G : networkx Graph
700 Octahedral graph
702 See Also
703 --------
704 tetrahedral_graph, cubical_graph, dodecahedral_graph, icosahedral_graph
706 References
707 ----------
708 .. [1] https://mathworld.wolfram.com/OctahedralGraph.html
709 .. [2] https://en.wikipedia.org/wiki/Tur%C3%A1n_graph#Special_cases
711 """
712 G = nx.from_dict_of_lists(
713 {0: [1, 2, 3, 4], 1: [2, 3, 5], 2: [4, 5], 3: [4, 5], 4: [5]},
714 create_using=create_using,
715 )
716 G.name = "Platonic Octahedral Graph"
717 return G
720@nx._dispatchable(graphs=None, returns_graph=True)
721def pappus_graph():
722 """
723 Returns the Pappus graph.
725 The Pappus graph is a cubic symmetric distance-regular graph with 18 nodes
726 and 27 edges. It is Hamiltonian and can be represented in LCF notation as
727 [5,7,-7,7,-7,-5]^3 [1]_.
729 Returns
730 -------
731 G : networkx Graph
732 Pappus graph
734 References
735 ----------
736 .. [1] https://en.wikipedia.org/wiki/Pappus_graph
737 """
738 G = LCF_graph(18, [5, 7, -7, 7, -7, -5], 3)
739 G.name = "Pappus Graph"
740 return G
743@_raise_on_directed
744@nx._dispatchable(graphs=None, returns_graph=True)
745def petersen_graph(create_using=None):
746 """
747 Returns the Petersen graph.
749 The Peterson graph is a cubic, undirected graph with 10 nodes and 15 edges [1]_.
750 Julius Petersen constructed the graph as the smallest counterexample
751 against the claim that a connected bridgeless cubic graph
752 has an edge colouring with three colours [2]_.
754 Parameters
755 ----------
756 create_using : NetworkX graph constructor, optional (default=nx.Graph)
757 Graph type to create. If graph instance, then cleared before populated.
759 Returns
760 -------
761 G : networkx Graph
762 Petersen graph
764 References
765 ----------
766 .. [1] https://en.wikipedia.org/wiki/Petersen_graph
767 .. [2] https://www.win.tue.nl/~aeb/drg/graphs/Petersen.html
768 """
769 G = nx.from_dict_of_lists(
770 {
771 0: [1, 4, 5],
772 1: [0, 2, 6],
773 2: [1, 3, 7],
774 3: [2, 4, 8],
775 4: [3, 0, 9],
776 5: [0, 7, 8],
777 6: [1, 8, 9],
778 7: [2, 5, 9],
779 8: [3, 5, 6],
780 9: [4, 6, 7],
781 },
782 create_using=create_using,
783 )
784 G.name = "Petersen Graph"
785 return G
788@nx._dispatchable(graphs=None, returns_graph=True)
789def sedgewick_maze_graph(create_using=None):
790 """
791 Return a small maze with a cycle.
793 This is the maze used in Sedgewick, 3rd Edition, Part 5, Graph
794 Algorithms, Chapter 18, e.g. Figure 18.2 and following [1]_.
795 Nodes are numbered 0,..,7
797 Parameters
798 ----------
799 create_using : NetworkX graph constructor, optional (default=nx.Graph)
800 Graph type to create. If graph instance, then cleared before populated.
802 Returns
803 -------
804 G : networkx Graph
805 Small maze with a cycle
807 References
808 ----------
809 .. [1] Figure 18.2, Chapter 18, Graph Algorithms (3rd Ed), Sedgewick
810 """
811 G = empty_graph(0, create_using)
812 G.add_nodes_from(range(8))
813 G.add_edges_from([[0, 2], [0, 7], [0, 5]])
814 G.add_edges_from([[1, 7], [2, 6]])
815 G.add_edges_from([[3, 4], [3, 5]])
816 G.add_edges_from([[4, 5], [4, 7], [4, 6]])
817 G.name = "Sedgewick Maze"
818 return G
821@nx._dispatchable(graphs=None, returns_graph=True)
822def tetrahedral_graph(create_using=None):
823 """
824 Returns the 3-regular Platonic Tetrahedral graph.
826 Tetrahedral graph has 4 nodes and 6 edges. It is a
827 special case of the complete graph, K4, and wheel graph, W4.
828 It is one of the 5 platonic graphs [1]_.
830 Parameters
831 ----------
832 create_using : NetworkX graph constructor, optional (default=nx.Graph)
833 Graph type to create. If graph instance, then cleared before populated.
835 Returns
836 -------
837 G : networkx Graph
838 Tetrahedral Graph
840 See Also
841 --------
842 cubical_graph, octahedral_graph, dodecahedral_graph, icosahedral_graph
844 References
845 ----------
846 .. [1] https://en.wikipedia.org/wiki/Tetrahedron#Tetrahedral_graph
848 """
849 G = complete_graph(4, create_using)
850 G.name = "Platonic Tetrahedral Graph"
851 return G
854@_raise_on_directed
855@nx._dispatchable(graphs=None, returns_graph=True)
856def truncated_cube_graph(create_using=None):
857 """
858 Returns the skeleton of the truncated cube.
860 The truncated cube is an Archimedean solid with 14 regular
861 faces (6 octagonal and 8 triangular), 36 edges and 24 nodes [1]_.
862 The truncated cube is created by truncating (cutting off) the tips
863 of the cube one third of the way into each edge [2]_.
865 Parameters
866 ----------
867 create_using : NetworkX graph constructor, optional (default=nx.Graph)
868 Graph type to create. If graph instance, then cleared before populated.
870 Returns
871 -------
872 G : networkx Graph
873 Skeleton of the truncated cube
875 References
876 ----------
877 .. [1] https://en.wikipedia.org/wiki/Truncated_cube
878 .. [2] https://www.coolmath.com/reference/polyhedra-truncated-cube
880 """
881 G = nx.from_dict_of_lists(
882 {
883 0: [1, 2, 4],
884 1: [11, 14],
885 2: [3, 4],
886 3: [6, 8],
887 4: [5],
888 5: [16, 18],
889 6: [7, 8],
890 7: [10, 12],
891 8: [9],
892 9: [17, 20],
893 10: [11, 12],
894 11: [14],
895 12: [13],
896 13: [21, 22],
897 14: [15],
898 15: [19, 23],
899 16: [17, 18],
900 17: [20],
901 18: [19],
902 19: [23],
903 20: [21],
904 21: [22],
905 22: [23],
906 },
907 create_using=create_using,
908 )
909 G.name = "Truncated Cube Graph"
910 return G
913@nx._dispatchable(graphs=None, returns_graph=True)
914def truncated_tetrahedron_graph(create_using=None):
915 """
916 Returns the skeleton of the truncated Platonic tetrahedron.
918 The truncated tetrahedron is an Archimedean solid with 4 regular hexagonal faces,
919 4 equilateral triangle faces, 12 nodes and 18 edges. It can be constructed by truncating
920 all 4 vertices of a regular tetrahedron at one third of the original edge length [1]_.
922 Parameters
923 ----------
924 create_using : NetworkX graph constructor, optional (default=nx.Graph)
925 Graph type to create. If graph instance, then cleared before populated.
927 Returns
928 -------
929 G : networkx Graph
930 Skeleton of the truncated tetrahedron
932 References
933 ----------
934 .. [1] https://en.wikipedia.org/wiki/Truncated_tetrahedron
936 """
937 G = path_graph(12, create_using)
938 G.add_edges_from([(0, 2), (0, 9), (1, 6), (3, 11), (4, 11), (5, 7), (8, 10)])
939 G.name = "Truncated Tetrahedron Graph"
940 return G
943@_raise_on_directed
944@nx._dispatchable(graphs=None, returns_graph=True)
945def tutte_graph(create_using=None):
946 """
947 Returns the Tutte graph.
949 The Tutte graph is a cubic polyhedral, non-Hamiltonian graph. It has
950 46 nodes and 69 edges.
951 It is a counterexample to Tait's conjecture that every 3-regular polyhedron
952 has a Hamiltonian cycle.
953 It can be realized geometrically from a tetrahedron by multiply truncating
954 three of its vertices [1]_.
956 Parameters
957 ----------
958 create_using : NetworkX graph constructor, optional (default=nx.Graph)
959 Graph type to create. If graph instance, then cleared before populated.
961 Returns
962 -------
963 G : networkx Graph
964 Tutte graph
966 References
967 ----------
968 .. [1] https://en.wikipedia.org/wiki/Tutte_graph
969 """
970 G = nx.from_dict_of_lists(
971 {
972 0: [1, 2, 3],
973 1: [4, 26],
974 2: [10, 11],
975 3: [18, 19],
976 4: [5, 33],
977 5: [6, 29],
978 6: [7, 27],
979 7: [8, 14],
980 8: [9, 38],
981 9: [10, 37],
982 10: [39],
983 11: [12, 39],
984 12: [13, 35],
985 13: [14, 15],
986 14: [34],
987 15: [16, 22],
988 16: [17, 44],
989 17: [18, 43],
990 18: [45],
991 19: [20, 45],
992 20: [21, 41],
993 21: [22, 23],
994 22: [40],
995 23: [24, 27],
996 24: [25, 32],
997 25: [26, 31],
998 26: [33],
999 27: [28],
1000 28: [29, 32],
1001 29: [30],
1002 30: [31, 33],
1003 31: [32],
1004 34: [35, 38],
1005 35: [36],
1006 36: [37, 39],
1007 37: [38],
1008 40: [41, 44],
1009 41: [42],
1010 42: [43, 45],
1011 43: [44],
1012 },
1013 create_using=create_using,
1014 )
1015 G.name = "Tutte's Graph"
1016 return G