图生成器

图谱 (Atlas)

用于生成小型图谱的生成器。

graph_atlas(i)	返回图谱中序号为 i 的图。
graph_atlas_g()	返回图谱中所有节点数不超过七的图的列表。

经典图

用于生成一些经典图的生成器。

典型的图构建函数调用方式如下：

>>> G = nx.complete_graph(100)

返回节点数为 n (标记为 0, .., 99) 的完全图，作为简单图。除了 empty_graph，此模块中的所有函数都返回一个 Graph 类（即一个简单、无向图）。

balanced_tree(r, h[, create_using])	返回高度为 h 的完美平衡 r 叉树。
barbell_graph(m1, m2[, create_using])	返回杠铃图：两个完全图通过一条路径连接。
binomial_tree(n[, create_using])	返回 n 阶二项树。
complete_graph(n[, create_using])	返回具有 n 个节点的完全图 K_n。
complete_multipartite_graph(*subset_sizes)	返回具有指定子集大小的完全多部图。
circular_ladder_graph(n[, create_using])	返回长度为 n 的环形梯图 \(CL_n\)。
circulant_graph(n, offsets[, create_using])	返回具有 \(n\) 个节点的循环图 \(Ci_n(x_1, x_2, ..., x_m)\)。
cycle_graph(n[, create_using])	返回由循环连接节点组成的环图 \(C_n\)。
dorogovtsev_goltsev_mendes_graph(n[, ...])	返回分层构建的 Dorogovtsev--Goltsev--Mendes 图。
empty_graph([n, create_using, default])	返回具有 n 个节点和零条边的空图。
full_rary_tree(r, n[, create_using])	创建一个具有 n 个节点的完全 r 叉树。
kneser_graph(n, k)	返回参数为 n 和 k 的 Kneser 图。
ladder_graph(n[, create_using])	返回长度为 n 的梯图。
lollipop_graph(m, n[, create_using])	返回棒棒糖图；K_m 连接到 P_n。
null_graph([create_using])	返回没有节点或边的空图。
path_graph(n[, create_using])	返回由线性连接节点组成的路径图 P_n。
star_graph(n[, create_using])	返回星图
tadpole_graph(m, n[, create_using])	返回 (m,n)-蝌蚪图；C_m 连接到 P_n。
trivial_graph([create_using])	返回具有一个节点（标签为 0）且没有边的平凡图。
turan_graph(n, r)	返回图兰图
wheel_graph(n[, create_using])	返回轮图

扩展图 (Expanders)

提供扩展图的显式构造方法。

margulis_gabber_galil_graph(n[, create_using])	返回具有 n^2 个节点的 Margulis-Gabber-Galil 无向多重图。
chordal_cycle_graph(p[, create_using])	返回具有 p 个弦节点的环图。
paley_graph(p[, create_using])	返回具有 \(p\) 个节点的 Paley \((\frac{p-1)}{2}\) -正则图。
maybe_regular_expander(n, d, *[, ...])	创建随机正则扩展图的工具。
is_regular_expander(G, *[, epsilon])	确定图 G 是否为正则扩展图。
random_regular_expander_graph(n, d, *[, ...])	返回具有 \(n\) 个节点和度数 \(d\) 的随机正则扩展图。

格图 (Lattice)

用于生成网格图和格图的函数

函数 grid_2d_graph()、triangular_lattice_graph() 和 hexagonal_lattice_graph() 分别对应于平面上的三种正则密铺：正方形密铺、三角形密铺和六边形密铺。 grid_graph() 和 hypercube_graph() 对于任意维度是类似的。有关三角形密铺以及正方形、六边形和三角形网格的有用讨论可以在此处找到。

grid_2d_graph(m, n[, periodic, create_using])	返回二维网格图。
grid_graph(dim[, periodic])	返回 n 维网格图。
hexagonal_lattice_graph(m, n[, periodic, ...])	返回一个 m 乘 n 的六边形格图。
hypercube_graph(n)	返回 n 维超立方体图。
triangular_lattice_graph(m, n[, periodic, ...])	返回 \(m\) 乘 \(n\) 的三角形格图。

小型图

各种小型具名图，以及一些紧凑的生成器。

LCF_graph(n, shift_list, repeats[, create_using])	返回 LCF 表示法中指定的立方图。
bull_graph([create_using])	返回牛头图 (Bull Graph)
chvatal_graph([create_using])	返回 Chvátal 图
cubical_graph([create_using])	返回 3-正则柏拉图立方图
desargues_graph([create_using])	返回 Desargues 图
diamond_graph([create_using])	返回钻石图
dodecahedral_graph([create_using])	返回柏拉图十二面体图。
frucht_graph([create_using])	返回 Frucht 图。
heawood_graph([create_using])	返回 Heawood 图，一个 (3,6) 笼。
hoffman_singleton_graph()	返回 Hoffman-Singleton 图。
house_graph([create_using])	返回房屋图（顶部带有三角形的正方形）
house_x_graph([create_using])	返回在房屋正方形内带有一个交叉的房屋图。
icosahedral_graph([create_using])	返回柏拉图二十面体图。
krackhardt_kite_graph([create_using])	返回 Krackhardt 风筝社交网络。
moebius_kantor_graph([create_using])	返回 Moebius-Kantor 图。
octahedral_graph([create_using])	返回柏拉图八面体图。
pappus_graph()	返回 Pappus 图。
petersen_graph([create_using])	返回 Petersen 图。
sedgewick_maze_graph([create_using])	返回带有环的小迷宫。
tetrahedral_graph([create_using])	返回 3-正则柏拉图四面体图。
truncated_cube_graph([create_using])	返回截角立方体的骨架图。
truncated_tetrahedron_graph([create_using])	返回截角柏拉图四面体的骨架图。
tutte_graph([create_using])	返回 Tutte 图。

随机图

用于生成随机图的生成器。

fast_gnp_random_graph(n, p[, seed, ...])	返回一个 \(G_{n,p}\) 随机图，也称为 Erdős-Rényi 图或二项图。
gnp_random_graph(n, p[, seed, directed, ...])	返回一个 \(G_{n,p}\) 随机图，也称为 Erdős-Rényi 图或二项图。
dense_gnm_random_graph(n, m[, seed, ...])	返回一个 \(G_{n,m}\) 随机图。
gnm_random_graph(n, m[, seed, directed, ...])	返回一个 \(G_{n,m}\) 随机图。
erdos_renyi_graph(n, p[, seed, directed, ...])	返回一个 \(G_{n,p}\) 随机图，也称为 Erdős-Rényi 图或二项图。
binomial_graph(n, p[, seed, directed, ...])	返回一个 \(G_{n,p}\) 随机图，也称为 Erdős-Rényi 图或二项图。
newman_watts_strogatz_graph(n, k, p[, seed, ...])	返回 Newman–Watts–Strogatz 小世界图。
watts_strogatz_graph(n, k, p[, seed, ...])	返回 Watts–Strogatz 小世界图。
connected_watts_strogatz_graph(n, k, p[, ...])	返回一个连通的 Watts–Strogatz 小世界图。
random_regular_graph(d, n[, seed, create_using])	返回一个具有 \(n\) 个节点和度数 \(d\) 的随机 \(d\)-正则图。
barabasi_albert_graph(n, m[, seed, ...])	使用 Barabási–Albert 优先连接方法返回一个随机图
dual_barabasi_albert_graph(n, m1, m2, p[, ...])	使用双重 Barabási–Albert 优先连接方法返回一个随机图
extended_barabasi_albert_graph(n, m, p, q[, ...])	返回一个扩展的 Barabási–Albert 模型图。
powerlaw_cluster_graph(n, m, p[, seed, ...])	用于生成具有幂律度分布和近似平均聚类的增长图的 Holme 和 Kim 算法。
random_kernel_graph(n, kernel_integral[, ...])	返回基于指定核函数的随机图。
random_lobster(n, p1, p2[, seed, create_using])	返回一个随机龙虾图。
random_shell_graph(constructor[, seed, ...])	返回根据给定的构造器生成的随机壳图。
random_powerlaw_tree(n[, gamma, seed, ...])	返回一个具有幂律度分布的树。
random_powerlaw_tree_sequence(n[, gamma, ...])	返回一个具有幂律分布的树的度序列。
random_kernel_graph(n, kernel_integral[, ...])	返回基于指定核函数的随机图。

复制-分化图

基于“复制”方法生成图的函数。

这些图生成器从一个小型初始图开始，然后复制节点并（部分）复制它们的边。这些函数通常受到生物网络的启发。

duplication_divergence_graph(n, p[, seed, ...])	使用复制-分化模型返回一个无向图。
partial_duplication_graph(N, n, p, q[, ...])	使用部分复制模型返回一个随机图。

度序列图

生成具有给定度序列或期望度序列的图。

configuration_model(deg_sequence[, ...])	返回一个具有给定度序列的随机图。
directed_configuration_model(...[, ...])	返回一个具有给定度序列的有向随机图。
expected_degree_graph(w[, seed, selfloops])	返回一个具有给定期望度数的随机图。
havel_hakimi_graph(deg_sequence[, create_using])	使用 Havel-Hakimi 算法构造并返回具有给定度序列的简单图。
directed_havel_hakimi_graph(in_deg_sequence, ...)	返回一个具有给定度序列的有向图。
degree_sequence_tree(deg_sequence[, ...])	为给定的度序列构造一棵树。
random_degree_sequence_graph(sequence[, ...])	返回一个具有给定度序列的简单随机图。

随机聚类图

生成具有给定度序列和三角形序列的图。

random_clustered_graph(joint_degree_sequence)

生成一个具有给定联合独立边度序列和三角形度序列的随机图。

有向图

用于生成一些有向图的生成器，包括增长网络 (GN) 图和无标度图。

gn_graph(n[, kernel, create_using, seed])	返回具有 n 个节点的增长网络 (GN) 有向图。
gnr_graph(n, p[, create_using, seed])	返回具有 n 个节点和重定向概率 p 的带重定向增长网络 (GNR) 有向图。
gnc_graph(n[, create_using, seed])	返回具有 n 个节点的带复制增长网络 (GNC) 有向图。
random_k_out_graph(n, k, alpha[, ...])	返回一个带优先连接的随机 k-出度图。
scale_free_graph(n[, alpha, beta, gamma, ...])	返回一个无标度有向图。

几何图

用于生成几何图的生成器。

geometric_edges(G, radius[, p, pos_name])	返回彼此距离在 radius 范围内的节点对的边列表。
geographical_threshold_graph(n, theta[, ...])	返回地理阈值图。
navigable_small_world_graph(n[, p, q, r, ...])	返回可导航小世界图。
random_geometric_graph(n, radius[, dim, ...])	返回维度为 dim 的单位立方体中的随机几何图。
soft_random_geometric_graph(n, radius[, ...])	返回单位立方体中的软随机几何图。
thresholded_random_geometric_graph(n, ...[, ...])	返回单位立方体中的阈值随机几何图。
waxman_graph(n[, beta, alpha, L, domain, ...])	返回 Waxman 随机图。
geometric_soft_configuration_graph(*, beta)	返回几何软配置模型中的随机图。

线图 (Line Graph)

用于生成线图的函数。

line_graph(G[, create_using])	返回图或有向图 G 的线图。
inverse_line_graph(G)	返回图 G 的逆线图。

自我中心图 (Ego Graph)

自我中心图。

ego_graph(G, n[, radius, center, ...])

返回以节点 n 为中心、在给定半径范围内的邻居的诱导子图。

随机图 (Stochastic)

用于从给定加权有向图生成随机图的函数。

stochastic_graph(G[, copy, weight])

返回有向图 G 的右随机表示。

自治系统图 (AS graph)

生成类似于互联网自治系统网络的图

random_internet_as_graph(n[, seed])

生成一个类似于互联网AS网络的随机无向图

交集图

用于生成随机交集图的生成器。

uniform_random_intersection_graph(n, m, p[, ...])	返回一个均匀随机交集图。
k_random_intersection_graph(n, m, k[, seed])	返回一个交集图，其中每个节点的属性集是随机选择且大小相等 (k)。
general_random_intersection_graph(n, m, p[, ...])	返回一个随机交集图，其中节点与属性集之间的连接具有独立的概率。

社交网络

著名的社交网络。

karate_club_graph()	返回 Zachary 的空手道俱乐部图。
davis_southern_women_graph()	返回 Davis 南方女性社交网络。
florentine_families_graph()	返回佛罗伦萨家族图。
les_miserables_graph()	返回小说《悲惨世界》中角色的共同出现网络。

社区

用于生成社会网络研究中使用的图类别的生成器。

caveman_graph(l, k)	返回由 l 个大小为 k 的派系组成的穴居人图。
connected_caveman_graph(l, k)	返回由 l 个大小为 k 的派系组成的连通穴居人图。
gaussian_random_partition_graph(n, s, v, ...)	生成一个高斯随机划分图。
LFR_benchmark_graph(n, tau1, tau2, mu[, ...])	返回 LFR 基准图。
planted_partition_graph(l, k, p_in, p_out[, ...])	返回植入的 l-划分图。
random_partition_graph(sizes, p_in, p_out[, ...])	返回具有给定划分大小的随机划分图。
relaxed_caveman_graph(l, k, p[, seed])	返回一个松弛的穴居人图。
ring_of_cliques(num_cliques, clique_size)	定义一个“派系环”图。
stochastic_block_model(sizes, p[, nodelist, ...])	返回一个随机块模型图。
windmill_graph(n, k)	生成一个风车图。

谱图

生成具有给定特征向量结构的图

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

返回一个随机简单图，其谱类似于 G

树

用于生成树的函数。

本模块中用于随机采样树的函数有两种变体：有标签和无标签。有标签变体从给定节点数的每种可能的树中均匀随机采样。无标签变体从给定节点数的每种可能的*同构类*树中均匀随机采样。

为了理解它们之间的区别，考虑以下示例。有四节点的树有两种同构类。一种是路径图，另一种是星形图。无标签变体将以 1/2 的概率返回路径图或星形图。

有标签变体将以 3/4 的概率返回路径图，以 1/4 的概率返回星形图，因为路径图的有标签变体比星形图多。更准确地说，路径图的自同构群阶数为 2，而星形图的自同构群阶数为 6，所以路径图的有标签变体是星形图的三倍，因此有三次更高的被抽到的机会。

此外，本模块中的一些函数可以均匀随机采样有根树和有根森林。有根树是指具有指定根节点的树。有根森林是不相交的有根树的并集。

prefix_tree(paths)	从路径列表中创建一个有向前缀树。
random_labeled_tree(n, *[, seed])	返回一个在 n 个节点上均匀随机选择的有标签树。
random_labeled_rooted_tree(n, *[, seed])	返回一个具有 n 个节点的有标签有根树。
random_labeled_rooted_forest(n, *[, seed])	返回一个具有 n 个节点的有标签有根森林。
random_unlabeled_tree(n, *[, ...])	随机选择并返回一棵树或多棵树的列表。
random_unlabeled_rooted_tree(n, *[, ...])	均匀随机返回一定数量的无标签有根树
random_unlabeled_rooted_forest(n, *[, q, ...])	随机选择并返回一个森林或多个森林的列表。

非同构树

实现了 Wright, Richmond, Odlyzko 和 McKay (WROM) 算法，用于枚举给定阶数的所有非同构自由树。有根树由层次序列表示，即列表，其中第 i 个元素指定顶点 i 到根的距离。

nonisomorphic_trees(order[, create])	生成非同构树的列表
number_of_nonisomorphic_trees(order)	返回非同构树的数量

三元组图

生成三元组图的函数，即三个节点上可能的有向图。

triad_graph(triad_name)

返回给定名称的三元组图。

联合度序列

生成具有给定联合度和有向联合度的图

is_valid_joint_degree(joint_degrees)	检查给定的联合度字典是否可实现。
joint_degree_graph(joint_degrees[, seed])	生成一个具有给定联合度字典的随机简单图。
is_valid_directed_joint_degree(in_degrees, ...)	检查给定的有向联合度输入是否可实现
directed_joint_degree_graph(in_degrees, ...)	生成具有联合度的随机简单有向图。

Mycielski

与 Mycielski 运算和 Mycielskian 图族相关的函数。

mycielskian(G[, iterations])	返回简单无向图 G 的 Mycielskian
mycielski_graph(n)	第 n 个 Mycielski 图的生成器。

Harary 图

Harary 图的生成器

本模块提供了两个 Harary 图的生成器，该图由著名数学家 Frank Harary 在其 1962 年的作品 [H] 中提出。第一个生成器给出在给定节点数和边数下最大化节点连通度的 Harary 图。第二个生成器给出在给定节点连通度和节点数下最小化图边数的 Harary 图。

参考文献

[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])	返回具有给定节点数和边数的 Harary 图。
hkn_harary_graph(k, n[, create_using])	返回具有给定节点连通度和节点数的 Harary 图。

Cographs (补图)

Cographs 的生成器

Cograph 是一个不包含四个顶点上的路径的图。Cographs 或 \(P_4\) 无图可以通过对单个顶点进行不相交并集和补运算获得。

参考文献

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

返回一个具有 \(2 ^ n\) 个节点的随机 cograph。

区间图

区间图的生成器。

interval_graph(intervals)

为给定的区间列表生成一个区间图。

数独

数独图的生成器

本模块提供了 n-数独图的生成器。可用于开发解决或生成数独谜题的算法。

一个完成的数独网格是一个 9x9 的整数数组，值在 1 到 9 之间，同一行、同一列或同一 3x3 宫中没有数字重复出现。

8 6 4 3 2 5 9 7 1	3 7 1 8 4 9 2 6 5	2 5 9 7 6 1 8 4 3
4 3 6 1 9 8 2 5 7	1 9 2 6 5 7 4 8 3	5 8 7 4 3 2 9 1 6
6 8 9 7 1 3 5 4 2	7 3 4 5 2 8 9 1 6	1 2 5 6 9 4 3 7 8

数独图是一个无向图，有 81 个顶点，对应于数独网格的单元格。它是一个度数为 20 的正则图。两个不同的顶点相邻当且仅当它们对应的单元格属于同一行、同一列或同一宫。一个完成的数独网格对应于数独图的九种颜色着色。

更一般地说，n-数独图是一个具有 n^4 个顶点的图，对应于 n^2 x n^2 网格的单元格。两个不同的顶点相邻当且仅当它们属于同一行、同一列或同一 n x n 宫。

参考文献

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

返回 n-数独图。

时间序列

时间序列图

visibility_graph(series)

返回输入时间序列的可见性图。