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

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.

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.

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.