Graph generators#

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#

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.

path_graph(n[, create_using])

Returns the Path graph P_n of linearly connected nodes.

star_graph(n[, create_using])

Return the star graph

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.

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#

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.

Small#

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])

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.

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.

Duplication Divergence#

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#

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.

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 some directed graphs, including growing network (GN) graphs and scale-free 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.

thresholded_random_geometric_graph(n, ...[, ...])

Returns a thresholded random geometric graph in the unit cube.

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#

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#

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#

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

Returns a random simple graph with spectrum resembling that of G

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#

nonisomorphic_trees(order[, create])

Returns a list of nonisomporphic trees

number_of_nonisomorphic_trees(order)

Returns the number of nonisomorphic trees

Triads#

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#

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.

Sudoku#

sudoku_graph([n])

Returns the n-Sudoku graph.