Graph generators

Atlas

Generators for the small graph atlas.

graph_atlas(i)	Returns graph number i from the Graph Atlas.
graph_atlas_g()	Returns the list of all graphs with up to seven nodes named in the Graph Atlas.

Classic

Generators for some classic graphs.

The typical graph builder function is called as follows:

>>> G = nx.complete_graph(100)

returning the complete graph on n nodes labeled 0, .., 99 as a simple graph. Except for empty_graph, all the functions in this module return a Graph class (i.e. a simple, undirected graph).

balanced_tree(r, h[, create_using])	Returns the perfectly balanced r-ary tree of height h.
barbell_graph(m1, m2[, create_using])	Returns the Barbell Graph: two complete graphs connected by a path.
binomial_tree(n[, create_using])	Returns the Binomial Tree of order n.
complete_graph(n[, create_using])	Return the complete graph K_n with n nodes.
complete_multipartite_graph(*subset_sizes)	Returns the complete multipartite graph with the specified subset sizes.
circular_ladder_graph(n[, create_using])	Returns the circular ladder graph \(CL_n\) of length n.
circulant_graph(n, offsets[, create_using])	Returns the circulant graph \(Ci_n(x_1, x_2, ..., x_m)\) with \(n\) nodes.
cycle_graph(n[, create_using])	Returns the cycle graph \(C_n\) of cyclically connected nodes.
dorogovtsev_goltsev_mendes_graph(n[, ...])	Returns the hierarchically constructed Dorogovtsev-Goltsev-Mendes graph.
empty_graph([n, create_using, default])	Returns the empty graph with n nodes and zero edges.
full_rary_tree(r, n[, create_using])	Creates a full r-ary tree of n nodes.
ladder_graph(n[, create_using])	Returns the Ladder graph of length n.
lollipop_graph(m, n[, create_using])	Returns the Lollipop Graph; K_m connected to P_n.
null_graph([create_using])	Returns the Null graph with no nodes or edges.
path_graph(n[, create_using])	Returns the Path graph P_n of linearly connected nodes.
star_graph(n[, create_using])	Return the star graph
trivial_graph([create_using])	Return the Trivial graph with one node (with label 0) and no edges.
turan_graph(n, r)	Return the Turan Graph
wheel_graph(n[, create_using])	Return the wheel graph

Expanders

Provides explicit constructions of expander graphs.

margulis_gabber_galil_graph(n[, create_using])	Returns the Margulis-Gabber-Galil undirected MultiGraph on n^2 nodes.
chordal_cycle_graph(p[, create_using])	Returns the chordal cycle graph on p nodes.
paley_graph(p[, create_using])	Returns the Paley \(\frac{(p-1)}{2}\) -regular graph on \(p\) nodes.

Lattice

Functions for generating grid graphs and lattices

The grid_2d_graph(), triangular_lattice_graph(), and hexagonal_lattice_graph() functions correspond to the three regular tilings of the plane, the square, triangular, and hexagonal tilings, respectively. grid_graph() and hypercube_graph() are similar for arbitrary dimensions. Useful relevant discussion can be found about Triangular Tiling, and Square, Hex and Triangle Grids

grid_2d_graph(m, n[, periodic, create_using])	Returns the two-dimensional grid graph.
grid_graph(dim[, periodic])	Returns the n-dimensional grid graph.
hexagonal_lattice_graph(m, n[, periodic, ...])	Returns an m by n hexagonal lattice graph.
hypercube_graph(n)	Returns the n-dimensional hypercube graph.
triangular_lattice_graph(m, n[, periodic, ...])	Returns the \(m\) by \(n\) triangular lattice graph.

Small

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

LCF_graph(n, shift_list, repeats[, create_using])	Return the cubic graph specified in LCF notation.
bull_graph([create_using])	Returns the Bull Graph
chvatal_graph([create_using])	Returns the Chvátal Graph
cubical_graph([create_using])	Returns the 3-regular Platonic Cubical Graph
desargues_graph([create_using])	Returns the Desargues Graph
diamond_graph([create_using])	Returns the Diamond graph
dodecahedral_graph([create_using])	Returns the Platonic Dodecahedral graph.
frucht_graph([create_using])	Returns the Frucht Graph.
heawood_graph([create_using])	Returns the Heawood Graph, a (3,6) cage.
hoffman_singleton_graph()	Returns the Hoffman-Singleton Graph.
house_graph([create_using])	Returns the House graph (square with triangle on top)
house_x_graph([create_using])	Returns the House graph with a cross inside the house square.
icosahedral_graph([create_using])	Returns the Platonic Icosahedral graph.
krackhardt_kite_graph([create_using])	Returns the Krackhardt Kite Social Network.
moebius_kantor_graph([create_using])	Returns the Moebius-Kantor graph.
octahedral_graph([create_using])	Returns the Platonic Octahedral graph.
pappus_graph()	Returns the Pappus graph.
petersen_graph([create_using])	Returns the Petersen graph.
sedgewick_maze_graph([create_using])	Return a small maze with a cycle.
tetrahedral_graph([create_using])	Returns the 3-regular Platonic Tetrahedral graph.
truncated_cube_graph([create_using])	Returns the skeleton of the truncated cube.
truncated_tetrahedron_graph([create_using])	Returns the skeleton of the truncated Platonic tetrahedron.
tutte_graph([create_using])	Returns the Tutte graph.

Random Graphs

Generators for random graphs.

fast_gnp_random_graph(n, p[, seed, directed])	Returns a \(G_{n,p}\) random graph, also known as an Erdős-Rényi graph or a binomial graph.
gnp_random_graph(n, p[, seed, directed])	Returns a \(G_{n,p}\) random graph, also known as an Erdős-Rényi graph or a binomial graph.
dense_gnm_random_graph(n, m[, seed])	Returns a \(G_{n,m}\) random graph.
gnm_random_graph(n, m[, seed, directed])	Returns a \(G_{n,m}\) random graph.
erdos_renyi_graph(n, p[, seed, directed])	Returns a \(G_{n,p}\) random graph, also known as an Erdős-Rényi graph or a binomial graph.
binomial_graph(n, p[, seed, directed])	Returns a \(G_{n,p}\) random graph, also known as an Erdős-Rényi graph or a binomial graph.
newman_watts_strogatz_graph(n, k, p[, seed])	Returns a Newman–Watts–Strogatz small-world graph.
watts_strogatz_graph(n, k, p[, seed])	Returns a Watts–Strogatz small-world graph.
connected_watts_strogatz_graph(n, k, p[, ...])	Returns a connected Watts–Strogatz small-world graph.
random_regular_graph(d, n[, seed])	Returns a random \(d\)-regular graph on \(n\) nodes.
barabasi_albert_graph(n, m[, seed, ...])	Returns a random graph using Barabási–Albert preferential attachment
dual_barabasi_albert_graph(n, m1, m2, p[, ...])	Returns a random graph using dual Barabási–Albert preferential attachment
extended_barabasi_albert_graph(n, m, p, q[, ...])	Returns an extended Barabási–Albert model graph.
powerlaw_cluster_graph(n, m, p[, seed])	Holme and Kim algorithm for growing graphs with powerlaw degree distribution and approximate average clustering.
random_kernel_graph(n, kernel_integral[, ...])	Returns an random graph based on the specified kernel.
random_lobster(n, p1, p2[, seed])	Returns a random lobster graph.
random_shell_graph(constructor[, seed])	Returns a random shell graph for the constructor given.
random_powerlaw_tree(n[, gamma, seed, tries])	Returns a tree with a power law degree distribution.
random_powerlaw_tree_sequence(n[, gamma, ...])	Returns a degree sequence for a tree with a power law distribution.
random_kernel_graph(n, kernel_integral[, ...])	Returns an random graph based on the specified kernel.

Duplication Divergence

Functions for generating graphs based on the “duplication” method.

These graph generators start with a small initial graph then duplicate nodes and (partially) duplicate their edges. These functions are generally inspired by biological networks.

duplication_divergence_graph(n, p[, seed])	Returns an undirected graph using the duplication-divergence model.
partial_duplication_graph(N, n, p, q[, seed])	Returns a random graph using the partial duplication model.

Degree Sequence

Generate graphs with a given degree sequence or expected degree sequence.

configuration_model(deg_sequence[, ...])	Returns a random graph with the given degree sequence.
directed_configuration_model(...[, ...])	Returns a directed_random graph with the given degree sequences.
expected_degree_graph(w[, seed, selfloops])	Returns a random graph with given expected degrees.
havel_hakimi_graph(deg_sequence[, create_using])	Returns a simple graph with given degree sequence constructed using the Havel-Hakimi algorithm.
directed_havel_hakimi_graph(in_deg_sequence, ...)	Returns a directed graph with the given degree sequences.
degree_sequence_tree(deg_sequence[, ...])	Make a tree for the given degree sequence.
random_degree_sequence_graph(sequence[, ...])	Returns a simple random graph with the given degree sequence.

Random Clustered

Generate graphs with given degree and triangle sequence.

random_clustered_graph(joint_degree_sequence)

Generate a random graph with the given joint independent edge degree and triangle degree sequence.

Directed

Generators for some directed graphs, including growing network (GN) graphs and scale-free graphs.

gn_graph(n[, kernel, create_using, seed])	Returns the growing network (GN) digraph with n nodes.
gnr_graph(n, p[, create_using, seed])	Returns the growing network with redirection (GNR) digraph with n nodes and redirection probability p.
gnc_graph(n[, create_using, seed])	Returns the growing network with copying (GNC) digraph with n nodes.
random_k_out_graph(n, k, alpha[, ...])	Returns a random k-out graph with preferential attachment.
scale_free_graph(n[, alpha, beta, gamma, ...])	Returns a scale-free directed graph.

Geometric

Generators for geometric graphs.

geometric_edges(G, radius[, p])	Returns edge list of node pairs within radius of each other.
geographical_threshold_graph(n, theta[, ...])	Returns a geographical threshold graph.
navigable_small_world_graph(n[, p, q, r, ...])	Returns a navigable small-world graph.
random_geometric_graph(n, radius[, dim, ...])	Returns a random geometric graph in the unit cube of dimensions dim.
soft_random_geometric_graph(n, radius[, ...])	Returns a soft random geometric graph in the unit cube.
thresholded_random_geometric_graph(n, ...[, ...])	Returns a thresholded random geometric graph in the unit cube.
waxman_graph(n[, beta, alpha, L, domain, ...])	Returns a Waxman random graph.

Line Graph

Functions for generating line graphs.

line_graph(G[, create_using])	Returns the line graph of the graph or digraph G.
inverse_line_graph(G)	Returns the inverse line graph of graph G.

Ego Graph

Ego graph.

ego_graph(G, n[, radius, center, ...])

Returns induced subgraph of neighbors centered at node n within a given radius.

Stochastic

Functions for generating stochastic graphs from a given weighted directed graph.

stochastic_graph(G[, copy, weight])

Returns a right-stochastic representation of directed graph G.

AS graph

Generates graphs resembling the Internet Autonomous System network

random_internet_as_graph(n[, seed])

Generates a random undirected graph resembling the Internet AS network

Intersection

Generators for random intersection graphs.

uniform_random_intersection_graph(n, m, p[, ...])	Returns a uniform random intersection graph.
k_random_intersection_graph(n, m, k[, seed])	Returns a intersection graph with randomly chosen attribute sets for each node that are of equal size (k).
general_random_intersection_graph(n, m, p[, ...])	Returns a random intersection graph with independent probabilities for connections between node and attribute sets.

Social Networks

Famous social networks.

karate_club_graph()	Returns Zachary's Karate Club graph.
davis_southern_women_graph()	Returns Davis Southern women social network.
florentine_families_graph()	Returns Florentine families graph.
les_miserables_graph()	Returns coappearance network of characters in the novel Les Miserables.

Community

Generators for classes of graphs used in studying social networks.

caveman_graph(l, k)	Returns a caveman graph of l cliques of size k.
connected_caveman_graph(l, k)	Returns a connected caveman graph of l cliques of size k.
gaussian_random_partition_graph(n, s, v, ...)	Generate a Gaussian random partition graph.
LFR_benchmark_graph(n, tau1, tau2, mu[, ...])	Returns the LFR benchmark graph.
planted_partition_graph(l, k, p_in, p_out[, ...])	Returns the planted l-partition graph.
random_partition_graph(sizes, p_in, p_out[, ...])	Returns the random partition graph with a partition of sizes.
relaxed_caveman_graph(l, k, p[, seed])	Returns a relaxed caveman graph.
ring_of_cliques(num_cliques, clique_size)	Defines a "ring of cliques" graph.
stochastic_block_model(sizes, p[, nodelist, ...])	Returns a stochastic block model graph.
windmill_graph(n, k)	Generate a windmill graph.

Spectral

Generates graphs with a given eigenvector structure

spectral_graph_forge(G, alpha[, ...])

Returns a random simple graph with spectrum resembling that of G

Trees

Functions for generating trees.

random_tree(n[, seed, create_using])	Returns a uniformly random tree on n nodes.
prefix_tree(paths)	Creates a directed prefix tree from a list of paths.

Non Isomorphic Trees

Implementation of the Wright, Richmond, Odlyzko and McKay (WROM) algorithm for the enumeration of all non-isomorphic free trees of a given order. Rooted trees are represented by level sequences, i.e., lists in which the i-th element specifies the distance of vertex i to the root.

nonisomorphic_trees(order[, create])	Returns a list of nonisomporphic trees
number_of_nonisomorphic_trees(order)	Returns the number of nonisomorphic trees

Triads

Functions that generate the triad graphs, that is, the possible digraphs on three nodes.

triad_graph(triad_name)

Returns the triad graph with the given name.

Joint Degree Sequence

Generate graphs with a given joint degree and directed joint degree

is_valid_joint_degree(joint_degrees)	Checks whether the given joint degree dictionary is realizable.
joint_degree_graph(joint_degrees[, seed])	Generates a random simple graph with the given joint degree dictionary.
is_valid_directed_joint_degree(in_degrees, ...)	Checks whether the given directed joint degree input is realizable
directed_joint_degree_graph(in_degrees, ...)	Generates a random simple directed graph with the joint degree.

Mycielski

Functions related to the Mycielski Operation and the Mycielskian family of graphs.

mycielskian(G[, iterations])	Returns the Mycielskian of a simple, undirected graph G
mycielski_graph(n)	Generator for the n_th Mycielski Graph.

Harary Graph

Generators for Harary graphs

This module gives two generators for the Harary graph, which was introduced by the famous mathematician Frank Harary in his 1962 work [H]. The first generator gives the Harary graph that maximizes the node connectivity with given number of nodes and given number of edges. The second generator gives the Harary graph that minimizes the number of edges in the graph with given node connectivity and number of nodes.

References

[H]

Harary, F. “The Maximum Connectivity of a Graph.” Proc. Nat. Acad. Sci. USA 48, 1142-1146, 1962.

hnm_harary_graph(n, m[, create_using])	Returns the Harary graph with given numbers of nodes and edges.
hkn_harary_graph(k, n[, create_using])	Returns the Harary graph with given node connectivity and node number.

Cographs

Generators for cographs

A cograph is a graph containing no path on four vertices. Cographs or \(P_4\)-free graphs can be obtained from a single vertex by disjoint union and complementation operations.

References

[0]

D.G. Corneil, H. Lerchs, L.Stewart Burlingham, “Complement reducible graphs”, Discrete Applied Mathematics, Volume 3, Issue 3, 1981, Pages 163-174, ISSN 0166-218X.

random_cograph(n[, seed])

Returns a random cograph with \(2 ^ n\) nodes.

Interval Graph

Generators for interval graph.

interval_graph(intervals)

Generates an interval graph for a list of intervals given.

Sudoku

Generator for Sudoku graphs

This module gives a generator for n-Sudoku graphs. It can be used to develop algorithms for solving or generating Sudoku puzzles.

A completed Sudoku grid is a 9x9 array of integers between 1 and 9, with no number appearing twice in the same row, column, or 3x3 box.

8 6 4 3 2 5 9 7 1	3 7 1 8 4 9 2 6 5	2 5 9 7 6 1 8 4 3
4 3 6 1 9 8 2 5 7	1 9 2 6 5 7 4 8 3	5 8 7 4 3 2 9 1 6
6 8 9 7 1 3 5 4 2	7 3 4 5 2 8 9 1 6	1 2 5 6 9 4 3 7 8

The Sudoku graph is an undirected graph with 81 vertices, corresponding to the cells of a Sudoku grid. It is a regular graph of degree 20. Two distinct vertices are adjacent if and only if the corresponding cells belong to the same row, column, or box. A completed Sudoku grid corresponds to a vertex coloring of the Sudoku graph with nine colors.

More generally, the n-Sudoku graph is a graph with n^4 vertices, corresponding to the cells of an n^2 by n^2 grid. Two distinct vertices are adjacent if and only if they belong to the same row, column, or n by n box.

References

[1]

Herzberg, A. M., & Murty, M. R. (2007). Sudoku squares and chromatic polynomials. Notices of the AMS, 54(6), 708-717.

[2]

Sander, Torsten (2009), “Sudoku graphs are integral”, Electronic Journal of Combinatorics, 16 (1): Note 25, 7pp, MR 2529816

[3]

Wikipedia contributors. “Glossary of Sudoku.” Wikipedia, The Free Encyclopedia, 3 Dec. 2019. Web. 22 Dec. 2019.

sudoku_graph([n])

Returns the n-Sudoku graph.