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 generator 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 generators 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)	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])	Generates the circulant graph \(Ci_n(x_1, x_2, ..., x_m)\) with \(n\) vertices.
`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 vertices.
`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 (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.

`make_small_graph`(graph_description[, …])	Return the small graph described by graph_description.
`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])	Return the Desargues graph.
`diamond_graph`([create_using])	Returns the Diamond graph.
`dodecahedral_graph`([create_using])	Return the Platonic Dodecahedral graph.
`frucht_graph`([create_using])	Returns the Frucht Graph.
`heawood_graph`([create_using])	Return the Heawood graph, a (3,6) cage.
`hoffman_singleton_graph`()	Return 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])	Return 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`()	Return 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])	Return 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 according to the Barabási–Albert preferential attachment model.
`dual_barabasi_albert_graph`(n, m1, m2, p[, seed])	Returns a random graph according to the dual Barabási–Albert preferential attachment model.
`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.

`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.
`geographical_threshold_graph`(n, theta[, …])	Returns a geographical threshold graph.
`waxman_graph`(n[, beta, alpha, L, domain, …])	Returns a Waxman random graph.
`navigable_small_world_graph`(n[, p, q, r, …])	Returns a navigable small-world graph.
`thresholded_random_geometric_graph`(n, …[, …])	Returns a thresholded random geometric graph in the unit cube.

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.

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])	Returns a uniformly random tree on `n` nodes.
`prefix_tree`(paths)	Creates a directed prefix tree from the given list of iterables.

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 7 1 | 2 5 9 3 2 5 | 8 4 9 | 7 6 1 9 7 1 | 2 6 5 | 8 4 3 ——+——-+—— 4 3 6 | 1 9 2 | 5 8 7 1 9 8 | 6 5 7 | 4 3 2 2 5 7 | 4 8 3 | 9 1 6 ——+——-+—— 6 8 9 | 7 3 4 | 1 2 5 7 1 3 | 5 2 8 | 6 9 4 5 4 2 | 9 1 6 | 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.

`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.

Graph generators¶

Atlas¶

Classic¶

Expanders¶

Lattice¶

Small¶

Random Graphs¶

Duplication Divergence¶

Degree Sequence¶

Random Clustered¶

Directed¶

Geometric¶

Line Graph¶

Ego Graph¶

Stochastic¶

AS graph¶

Intersection¶

Social Networks¶

Community¶

Spectral¶

Trees¶

Non Isomorphic Trees¶

Triads¶

Joint Degree Sequence¶

Mycielski¶

Harary Graph¶

Cographs¶

Interval Graph¶

Sudoku¶