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. |
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. |
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. |
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. |
relaxed_caveman_graph(l, k, p[, seed]) |
Returns a relaxed caveman graph. |
random_partition_graph(sizes, p_in, p_out[, …]) |
Returns the random partition graph with a partition of sizes. |
planted_partition_graph(l, k, p_in, p_out[, …]) |
Returns the planted l-partition graph. |
gaussian_random_partition_graph(n, s, v, …) |
Generate a Gaussian random partition 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
is_valid_joint_degree(joint_degrees) |
Checks whether the given joint degree dictionary is realizable as a simple graph. |
joint_degree_graph(joint_degrees[, seed]) |
Generates a random simple graph with the given joint degree dictionary. |
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. |