Source code for networkx.generators.small

"""
Various small and named graphs, together with some compact generators.

"""

__all__ = [
    "make_small_graph",
    "LCF_graph",
    "bull_graph",
    "chvatal_graph",
    "cubical_graph",
    "desargues_graph",
    "diamond_graph",
    "dodecahedral_graph",
    "frucht_graph",
    "heawood_graph",
    "hoffman_singleton_graph",
    "house_graph",
    "house_x_graph",
    "icosahedral_graph",
    "krackhardt_kite_graph",
    "moebius_kantor_graph",
    "octahedral_graph",
    "pappus_graph",
    "petersen_graph",
    "sedgewick_maze_graph",
    "tetrahedral_graph",
    "truncated_cube_graph",
    "truncated_tetrahedron_graph",
    "tutte_graph",
]

import networkx as nx
from networkx.generators.classic import (
    empty_graph,
    cycle_graph,
    path_graph,
    complete_graph,
)
from networkx.exception import NetworkXError


def make_small_undirected_graph(graph_description, create_using=None):
    """
    Return a small undirected graph described by graph_description.

    See make_small_graph.
    """
    G = empty_graph(0, create_using)
    if G.is_directed():
        raise NetworkXError("Directed Graph not supported")
    return make_small_graph(graph_description, G)


[docs]def make_small_graph(graph_description, create_using=None): """ Return the small graph described by graph_description. graph_description is a list of the form [ltype,name,n,xlist] Here ltype is one of "adjacencylist" or "edgelist", name is the name of the graph and n the number of nodes. This constructs a graph of n nodes with integer labels 0,..,n-1. If ltype="adjacencylist" then xlist is an adjacency list with exactly n entries, in with the j'th entry (which can be empty) specifies the nodes connected to vertex j. e.g. the "square" graph C_4 can be obtained by >>> G = nx.make_small_graph( ... ["adjacencylist", "C_4", 4, [[2, 4], [1, 3], [2, 4], [1, 3]]] ... ) or, since we do not need to add edges twice, >>> G = nx.make_small_graph(["adjacencylist", "C_4", 4, [[2, 4], [3], [4], []]]) If ltype="edgelist" then xlist is an edge list written as [[v1,w2],[v2,w2],...,[vk,wk]], where vj and wj integers in the range 1,..,n e.g. the "square" graph C_4 can be obtained by >>> G = nx.make_small_graph( ... ["edgelist", "C_4", 4, [[1, 2], [3, 4], [2, 3], [4, 1]]] ... ) Use the create_using argument to choose the graph class/type. """ if graph_description[0] not in ("adjacencylist", "edgelist"): raise NetworkXError("ltype must be either adjacencylist or edgelist") ltype = graph_description[0] name = graph_description[1] n = graph_description[2] G = empty_graph(n, create_using) nodes = G.nodes() if ltype == "adjacencylist": adjlist = graph_description[3] if len(adjlist) != n: raise NetworkXError("invalid graph_description") G.add_edges_from([(u - 1, v) for v in nodes for u in adjlist[v]]) elif ltype == "edgelist": edgelist = graph_description[3] for e in edgelist: v1 = e[0] - 1 v2 = e[1] - 1 if v1 < 0 or v1 > n - 1 or v2 < 0 or v2 > n - 1: raise NetworkXError("invalid graph_description") else: G.add_edge(v1, v2) G.name = name return G
[docs]def LCF_graph(n, shift_list, repeats, create_using=None): """ Return the cubic graph specified in LCF notation. LCF notation (LCF=Lederberg-Coxeter-Fruchte) is a compressed notation used in the generation of various cubic Hamiltonian graphs of high symmetry. See, for example, dodecahedral_graph, desargues_graph, heawood_graph and pappus_graph below. n (number of nodes) The starting graph is the n-cycle with nodes 0,...,n-1. (The null graph is returned if n < 0.) shift_list = [s1,s2,..,sk], a list of integer shifts mod n, repeats integer specifying the number of times that shifts in shift_list are successively applied to each v_current in the n-cycle to generate an edge between v_current and v_current+shift mod n. For v1 cycling through the n-cycle a total of k*repeats with shift cycling through shiftlist repeats times connect v1 with v1+shift mod n The utility graph $K_{3,3}$ >>> G = nx.LCF_graph(6, [3, -3], 3) The Heawood graph >>> G = nx.LCF_graph(14, [5, -5], 7) See http://mathworld.wolfram.com/LCFNotation.html for a description and references. """ if n <= 0: return empty_graph(0, create_using) # start with the n-cycle G = cycle_graph(n, create_using) if G.is_directed(): raise NetworkXError("Directed Graph not supported") G.name = "LCF_graph" nodes = sorted(list(G)) n_extra_edges = repeats * len(shift_list) # edges are added n_extra_edges times # (not all of these need be new) if n_extra_edges < 1: return G for i in range(n_extra_edges): shift = shift_list[i % len(shift_list)] # cycle through shift_list v1 = nodes[i % n] # cycle repeatedly through nodes v2 = nodes[(i + shift) % n] G.add_edge(v1, v2) return G
# ------------------------------------------------------------------------------- # Various small and named graphs # -------------------------------------------------------------------------------
[docs]def bull_graph(create_using=None): """Returns the Bull graph.""" description = [ "adjacencylist", "Bull Graph", 5, [[2, 3], [1, 3, 4], [1, 2, 5], [2], [3]], ] G = make_small_undirected_graph(description, create_using) return G
[docs]def chvatal_graph(create_using=None): """Returns the Chvátal graph.""" description = [ "adjacencylist", "Chvatal Graph", 12, [ [2, 5, 7, 10], [3, 6, 8], [4, 7, 9], [5, 8, 10], [6, 9], [11, 12], [11, 12], [9, 12], [11], [11, 12], [], [], ], ] G = make_small_undirected_graph(description, create_using) return G
[docs]def cubical_graph(create_using=None): """Returns the 3-regular Platonic Cubical graph.""" description = [ "adjacencylist", "Platonic Cubical Graph", 8, [ [2, 4, 5], [1, 3, 8], [2, 4, 7], [1, 3, 6], [1, 6, 8], [4, 5, 7], [3, 6, 8], [2, 5, 7], ], ] G = make_small_undirected_graph(description, create_using) return G
[docs]def desargues_graph(create_using=None): """Return the Desargues graph.""" G = LCF_graph(20, [5, -5, 9, -9], 5, create_using) G.name = "Desargues Graph" return G
[docs]def diamond_graph(create_using=None): """Returns the Diamond graph.""" description = [ "adjacencylist", "Diamond Graph", 4, [[2, 3], [1, 3, 4], [1, 2, 4], [2, 3]], ] G = make_small_undirected_graph(description, create_using) return G
[docs]def dodecahedral_graph(create_using=None): """Return the Platonic Dodecahedral graph.""" G = LCF_graph(20, [10, 7, 4, -4, -7, 10, -4, 7, -7, 4], 2, create_using) G.name = "Dodecahedral Graph" return G
[docs]def frucht_graph(create_using=None): """Returns the Frucht Graph. The Frucht Graph is the smallest cubical graph whose automorphism group consists only of the identity element. """ G = cycle_graph(7, create_using) G.add_edges_from( [ [0, 7], [1, 7], [2, 8], [3, 9], [4, 9], [5, 10], [6, 10], [7, 11], [8, 11], [8, 9], [10, 11], ] ) G.name = "Frucht Graph" return G
[docs]def heawood_graph(create_using=None): """Return the Heawood graph, a (3,6) cage.""" G = LCF_graph(14, [5, -5], 7, create_using) G.name = "Heawood Graph" return G
[docs]def hoffman_singleton_graph(): """Return the Hoffman-Singleton Graph.""" G = nx.Graph() for i in range(5): for j in range(5): G.add_edge(("pentagon", i, j), ("pentagon", i, (j - 1) % 5)) G.add_edge(("pentagon", i, j), ("pentagon", i, (j + 1) % 5)) G.add_edge(("pentagram", i, j), ("pentagram", i, (j - 2) % 5)) G.add_edge(("pentagram", i, j), ("pentagram", i, (j + 2) % 5)) for k in range(5): G.add_edge(("pentagon", i, j), ("pentagram", k, (i * k + j) % 5)) G = nx.convert_node_labels_to_integers(G) G.name = "Hoffman-Singleton Graph" return G
[docs]def house_graph(create_using=None): """Returns the House graph (square with triangle on top).""" description = [ "adjacencylist", "House Graph", 5, [[2, 3], [1, 4], [1, 4, 5], [2, 3, 5], [3, 4]], ] G = make_small_undirected_graph(description, create_using) return G
[docs]def house_x_graph(create_using=None): """Returns the House graph with a cross inside the house square.""" description = [ "adjacencylist", "House-with-X-inside Graph", 5, [[2, 3, 4], [1, 3, 4], [1, 2, 4, 5], [1, 2, 3, 5], [3, 4]], ] G = make_small_undirected_graph(description, create_using) return G
[docs]def icosahedral_graph(create_using=None): """Returns the Platonic Icosahedral graph.""" description = [ "adjacencylist", "Platonic Icosahedral Graph", 12, [ [2, 6, 8, 9, 12], [3, 6, 7, 9], [4, 7, 9, 10], [5, 7, 10, 11], [6, 7, 11, 12], [7, 12], [], [9, 10, 11, 12], [10], [11], [12], [], ], ] G = make_small_undirected_graph(description, create_using) return G
[docs]def krackhardt_kite_graph(create_using=None): """ Return the Krackhardt Kite Social Network. A 10 actor social network introduced by David Krackhardt to illustrate: degree, betweenness, centrality, closeness, etc. The traditional labeling is: Andre=1, Beverley=2, Carol=3, Diane=4, Ed=5, Fernando=6, Garth=7, Heather=8, Ike=9, Jane=10. """ description = [ "adjacencylist", "Krackhardt Kite Social Network", 10, [ [2, 3, 4, 6], [1, 4, 5, 7], [1, 4, 6], [1, 2, 3, 5, 6, 7], [2, 4, 7], [1, 3, 4, 7, 8], [2, 4, 5, 6, 8], [6, 7, 9], [8, 10], [9], ], ] G = make_small_undirected_graph(description, create_using) return G
[docs]def moebius_kantor_graph(create_using=None): """Returns the Moebius-Kantor graph.""" G = LCF_graph(16, [5, -5], 8, create_using) G.name = "Moebius-Kantor Graph" return G
[docs]def octahedral_graph(create_using=None): """Returns the Platonic Octahedral graph.""" description = [ "adjacencylist", "Platonic Octahedral Graph", 6, [[2, 3, 4, 5], [3, 4, 6], [5, 6], [5, 6], [6], []], ] G = make_small_undirected_graph(description, create_using) return G
[docs]def pappus_graph(): """Return the Pappus graph.""" G = LCF_graph(18, [5, 7, -7, 7, -7, -5], 3) G.name = "Pappus Graph" return G
[docs]def petersen_graph(create_using=None): """Returns the Petersen graph.""" description = [ "adjacencylist", "Petersen Graph", 10, [ [2, 5, 6], [1, 3, 7], [2, 4, 8], [3, 5, 9], [4, 1, 10], [1, 8, 9], [2, 9, 10], [3, 6, 10], [4, 6, 7], [5, 7, 8], ], ] G = make_small_undirected_graph(description, create_using) return G
[docs]def sedgewick_maze_graph(create_using=None): """ Return a small maze with a cycle. This is the maze used in Sedgewick,3rd Edition, Part 5, Graph Algorithms, Chapter 18, e.g. Figure 18.2 and following. Nodes are numbered 0,..,7 """ G = empty_graph(0, create_using) G.add_nodes_from(range(8)) G.add_edges_from([[0, 2], [0, 7], [0, 5]]) G.add_edges_from([[1, 7], [2, 6]]) G.add_edges_from([[3, 4], [3, 5]]) G.add_edges_from([[4, 5], [4, 7], [4, 6]]) G.name = "Sedgewick Maze" return G
[docs]def tetrahedral_graph(create_using=None): """Return the 3-regular Platonic Tetrahedral graph.""" G = complete_graph(4, create_using) G.name = "Platonic Tetrahedral graph" return G
[docs]def truncated_cube_graph(create_using=None): """Returns the skeleton of the truncated cube.""" description = [ "adjacencylist", "Truncated Cube Graph", 24, [ [2, 3, 5], [12, 15], [4, 5], [7, 9], [6], [17, 19], [8, 9], [11, 13], [10], [18, 21], [12, 13], [15], [14], [22, 23], [16], [20, 24], [18, 19], [21], [20], [24], [22], [23], [24], [], ], ] G = make_small_undirected_graph(description, create_using) return G
[docs]def truncated_tetrahedron_graph(create_using=None): """Returns the skeleton of the truncated Platonic tetrahedron.""" G = path_graph(12, create_using) # G.add_edges_from([(1,3),(1,10),(2,7),(4,12),(5,12),(6,8),(9,11)]) G.add_edges_from([(0, 2), (0, 9), (1, 6), (3, 11), (4, 11), (5, 7), (8, 10)]) G.name = "Truncated Tetrahedron Graph" return G
[docs]def tutte_graph(create_using=None): """Returns the Tutte graph.""" description = [ "adjacencylist", "Tutte's Graph", 46, [ [2, 3, 4], [5, 27], [11, 12], [19, 20], [6, 34], [7, 30], [8, 28], [9, 15], [10, 39], [11, 38], [40], [13, 40], [14, 36], [15, 16], [35], [17, 23], [18, 45], [19, 44], [46], [21, 46], [22, 42], [23, 24], [41], [25, 28], [26, 33], [27, 32], [34], [29], [30, 33], [31], [32, 34], [33], [], [], [36, 39], [37], [38, 40], [39], [], [], [42, 45], [43], [44, 46], [45], [], [], ], ] G = make_small_undirected_graph(description, create_using) return G