Graph generators

Atlas

graph_atlas_g ()

Return the list [G0,G1,...,G1252] of graphs as named in the Graph Atlas. G0,G1,...,G1252 are all graphs with up to 7 nodes.

Classic

balanced_tree (r, h)	Return the perfectly balanced r-tree of height h.
barbell_graph (m1, m2)	Return 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_bipartite_graph (n1, n2)	Return the complete bipartite graph K_{n1_n2}.
circular_ladder_graph (n)	Return the circular ladder graph CL_n of length n.
cycle_graph (n[, create_using])	Return the cycle graph C_n over n nodes.
dorogovtsev_goltsev_mendes_graph (n)	Return the hierarchically constructed Dorogovtsev-Goltsev-Mendes graph.
empty_graph ([n, create_using])	Return the empty graph with n nodes and zero edges.
grid_2d_graph (m, n[, periodic])	Return the 2d grid graph of mxn nodes, each connected to its nearest neighbors. Optional argument periodic=True will connect boundary nodes via periodic boundary conditions.
grid_graph (dim[, periodic])	Return the n-dimensional grid graph.
hypercube_graph (n)	Return the n-dimensional hypercube.
ladder_graph (n)	Return the Ladder graph of length n.
lollipop_graph (m, n)	Return the Lollipop Graph; K_m connected to P_n.
null_graph ([create_using])	Return the Null graph with no nodes or edges.
path_graph (n[, create_using])	Return the Path graph P_n of n nodes linearly connected by n-1 edges.
star_graph (n)	Return the Star graph with n+1 nodes: one center node, connected to n outer nodes.
trivial_graph ()	Return the Trivial graph with one node (with integer label 0) and no edges.
wheel_graph (n)	Return the wheel graph: a single hub node connected to each node of the (n-1)-node cycle graph.

Small

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

Random Graphs

fast_gnp_random_graph (n, p[, seed])	Return a random graph G_{n,p}.
gnp_random_graph (n, p[, seed])	Return a random graph G_{n,p}.
dense_gnm_random_graph (n, m[, seed])	Return the random graph G_{n,m}.
gnm_random_graph (n, m[, seed])	Return the random graph G_{n,m}.
erdos_renyi_graph (n, p[, seed])	Return a random graph G_{n,p}.
binomial_graph (n, p[, seed])	Return a random graph G_{n,p}.
newman_watts_strogatz_graph (n, k, p[, seed])	Return a Newman-Watts-Strogatz small world graph.
watts_strogatz_graph (n, k, p[, seed])	Return a Watts-Strogatz small world graph.
random_regular_graph (d, n[, seed])	Return a random regular graph of n nodes each with degree d, G_{n,d}. Return False if unsuccessful.
barabasi_albert_graph (n, m[, seed])	Return random graph using Barabási-Albert preferential attachment model.
powerlaw_cluster_graph (n, m, p[, seed])	Holme and Kim algorithm for growing graphs with powerlaw degree distribution and approximate average clustering.
random_lobster (n, p1, p2[, seed])	Return a random lobster.
random_shell_graph (constructor[, seed])	Return a random shell graph for the constructor given.
random_powerlaw_tree (n[, gamma, seed, tries])	Return a tree with a powerlaw degree distribution.
random_powerlaw_tree_sequence (n[, gamma, seed, tries])	Return a degree sequence for a tree with a powerlaw distribution.

Degree Sequence

configuration_model (deg_sequence[, seed])	Return a random pseudograph with the given degree sequence.
expected_degree_graph (w[, seed])	Return a random graph G(w) with expected degrees given by w.
havel_hakimi_graph (deg_sequence)	Return a simple graph with given degree sequence, constructed using the Havel-Hakimi algorithm.
degree_sequence_tree (deg_sequence)	Make a tree for the given degree sequence.
is_valid_degree_sequence (deg_sequence)	Return True if deg_sequence is a valid sequence of integer degrees equal to the degree sequence of some simple graph.
create_degree_sequence (n[, sfunction, max_tries, \*\*kwds)	Attempt to create a valid degree sequence of length n using specified function sfunction(n,**kwds).
double_edge_swap (G[, nswap])	Attempt nswap double-edge swaps on the graph G.
connected_double_edge_swap (G[, nswap])	Attempt nswap double-edge swaps on the graph G.
li_smax_graph (degree_seq)	Generates a graph based with a given degree sequence and maximizing the s-metric. Experimental implementation.
s_metric (G)	Return the “s-Metric” of graph G: the sum of the product deg(u)*deg(v) for every edge u-v in G

Directed

gn_graph (n[, kernel, seed])	Return the GN (growing network) digraph with n nodes.
gnr_graph (n, p[, seed])	Return the GNR (growing network with redirection) digraph with n nodes and redirection probability p.
gnc_graph (n[, seed])	Return the GNC (growing network with copying) digraph with n nodes.

Geometric

random_geometric_graph (n, radius[, create_using, repel, ...])

Random geometric graph in the unit cube

Hybrid

kl_connected_subgraph (G, k, l[, low_memory, same_as_graph])	Returns the maximum locally (k,l) connected subgraph of G.
is_kl_connected (G, k, l[, low_memory])	Returns True if G is kl connected