NetworkX 2.7#

发布日期：2022 年 2 月 28 日

支持 Python 3.8、3.9 和 3.10

NetworkX 是一个用于创建、操作和研究复杂网络结构、动力学和功能的 Python 包。

更多信息，请访问我们的网站和我们的示例图库。请将评论和问题发送至 networkx-discuss 邮件列表。

亮点#

此版本是 33 位贡献者在 7 个月内完成超过 166 个拉取请求的成果。亮点包括

警告

weisfeiler_lehman_graph_hash 输出中观察到的哈希值在 2.7 版本中因错误修复而发生变化。详情请参见 gh-4946。这意味着使用不同版本的 NetworkX（即 2.7 版本之前和之后）计算的同一图的哈希值进行比较，可能会错误地导致同构测试失败（同构图总是具有匹配的 Weisfeiler-Lehman 哈希值）。建议用户在升级时重新计算他们可能存储的任何图哈希值。

  • 取消了对 Python 3.7 的支持。

  • 增加了 Asadpour 算法，用于解决非对称旅行商问题：asadpour_atsp。

  • 增加了 Louvain 社区检测算法：louvain_communities 和 louvain_partitions

  • 移除了所有内部使用 numpy.matrix 类的地方，并为所有返回 numpy.matrix 实例的函数添加了 FutureWarning。在 NetworkX 3.0 中，numpy.matrix 类将被 2D numpy.ndarray 实例取代。

  • 增加了对 scipy.sparse 数组接口的支持。这包括 to_scipy_sparse_array 和 from_scipy_sparse_array。在 NetworkX 3.0 中，稀疏数组将取代稀疏矩阵成为与 scipy.sparse 交互的主要接口。新的代码应该使用 to_scipy_sparse_array 和 from_scipy_sparse_array，而不是它们对应的矩阵函数。此外，许多当前返回稀疏矩阵的函数现在会引发 FutureWarning，表明在 NetworkX 3.0 中它们将返回稀疏数组。

  • 为 to_numpy_array 添加了通用 dtype 支持。这增加了对通用属性的支持，例如具有复杂权重的邻接矩阵。这也增加了对处理多图权重的通用归约函数（如 mean 或 median）的支持。最后，这还包括对结构化 dtypes 的支持，这使得创建多属性邻接矩阵成为可能，并取代了通用性较差的 to_numpy_recarray。

  • 增加了对计算多图介数中心性的支持

  • 为 greedy_modularity_communities 增加了对有向图和多图的支持。

GSoC 拉取请求#

我们添加了来自四个 Google Summer of Code 项目的工作成果

改进#

  • [#4740] 增加了 Asadpour 算法，用于解决非对称旅行商问题。

  • [#4897] 改进了 nx.is_matching、nx.is_maximal_matching 和 nx.is_perfect_matching 的验证和性能。

  • [#4924] 修复了计算 nx.common_neighbor_centrality 时对非连通图的处理。

  • [#4929] 添加了 Louvain 社区检测。

  • [#4946] 添加了 Weisfeiler-Lehman 哈希子图哈希。

  • [#4950] 为 greedy_modularity_communities 添加了 n_communities 参数，以便在找到所需数量的社区时终止搜索。

  • [#4965] 和 [#4996] 修复了 greedy_modularity_communities 中对重新标记节点的问题。

  • [#4976] 添加了多图的介数中心性计算。

  • [#4999] 修复了有向图的 degree_assortativity_coefficient 计算。

  • [#5007] 为 greedy_modularity_communities 增加了对有向图和多图的支持。

  • [#5017] 改进了 descendants 和 ancestors 的实现和文档。

  • [#5019] 改进了有向无环图模块的文档和测试。

  • [#5029] 改进了 descendants_at_distance 的文档和测试。

  • [#5032] 改进了 complement_edges 的性能。

  • [#5045] 将 geometric_edges 添加到 nx 命名空间。

  • [#5051] 为使用 read_edgelist 读取数据增加了对注释字符的支持。

  • [#5052] 改进了 transitive_closure 的性能，并增加了对无向图和多图的支持。

  • [#5058] 改进了以 GraphML 格式写入数据时的异常处理。

  • [#5065] 改进了对 greedy_modularity_communities 中浮点权重和分辨率值的支持。

  • [#5077] 修复了有向图中 fast_gnp_random_graph 的边概率问题。

  • [#5086] 修复了 lowest_common_ancestors 中的缺陷。

  • [#5089] 添加了 find_negative_cycle 函数，用于查找加权图中的负循环。

  • [#5099] 改进了二元运算符的文档和测试。

  • [#5104] 为 vertex_cover 添加了对自环边的支持，并改进了性能。

  • [#5121] 改进了 *_all 二元运算符的性能。

  • [#5131] 绘制有向图的边时，允许 edge_style 为样式列表。

  • [#5139] 增加了对 scipy.sparse 数组接口的支持。

  • [#5144] 改进了 node_classification 函数的可读性。

  • [#5145] 采用了 Python 3.8 中添加的 math.hypot。

  • [#5153] 修复了非数字节点的图的 multipartite_layout 问题。

  • [#5154] 绘制边时，允许 arrowsize 为箭头大小列表。

  • [#5172] 为 find_cliques 添加了 nodes 关键字参数，以支持查找仅包含给定节点集合的最大团。

  • [#5197] 使用高级索引改进了 resistance_distance。

  • [#5216] 使 omega() 更接近已发表的算法。值略有变化。niter 参数在 lattice_reference() 中的默认值从 1 变为 5，在 omega 中从 100 变为 5。

  • [#5217] 改进了 betweenness_centrality 的性能和可读性。

  • [#5232] 为双向 Dijkstra 算法增加了对 None 边权重的支持。

  • [#5247] 改进了用于社区检测的异步标签传播算法 asyn_lpa_communities 的性能。

  • [#5250] 为 to_numpy_array 添加了通用 dtype 支持。

  • [#5285] 通过更新为原始论文中的加权版本来改进 karate_club_graph。

  • [#5287] 改进了 json_graph 的输入验证。

  • [#5288] 改进了 strongly_connected_components 的性能。

  • [#5324] 为 to_numpy_array 添加了对结构化 dtypes 的支持。

  • [#5336] 增加了对 numpy.random.Generator 接口的支持，用于生成随机数。

API 变更#

  • rescale_layout_dict 返回字典中的值现在是 numpy.ndarray 对象，而不是元组。这使得 rescale_layout_dict 的返回类型与其他所有布局函数一致。

  • 为 google_matrix 添加了一个 FutureWarning，表明在 NetworkX 3.0 中其返回类型将从 numpy.matrix 对象更改为 numpy.ndarray 对象。

  • 为 attr_matrix 添加了一个 FutureWarning，表明在 NetworkX 3.0 中其返回类型将从 numpy.matrix 对象更改为 numpy.ndarray 对象。

  • is_*_matching 函数现在对于不在图 G 中任何边的节点会引发异常。

弃用#

  • [#5055] 弃用 random_state 别名，转而使用 np_random_state

  • [#5114] 弃用 union 函数中未使用的 name 关键字参数。

  • [#5143] 弃用 euclidean，转而使用 math.dist。

  • [#5166] 弃用 node_classification 中的 hmn 和 lgc 模块。

  • [#5262] 弃用 to_scipy_sparse_matrix 和 from_scipy_sparse_matrix，转而分别使用 to_scipy_sparse_array 和 from_scipy_sparse_array。

  • [#5283] 弃用 networkx.generators.small 模块中的 make_small_graph 和 make_small_undirected_graph。

  • [#5330] 弃用 to_numpy_recarray，转而使用带有结构化 dtype 的 to_numpy_array。

  • [#5341] 弃用冗余的 info。

合并的拉取请求#

共提交了 166 项更改。

  • 在读取/解析边列表时支持 comments=None (#5051)

  • 在 gml docstring 中添加 de/stringizers 的“另请参见”引用。 (#5053)

  • 添加 weisfeiler lehman 子图哈希 (#4946)

  • 弃用 random_state 装饰器 (#5055)

  • 问题 #5023 的错误修复：single_source_dijkstra 中的边界情况错误 (#5033)

  • 更具信息性的 GraphML 异常 (#5058)

  • 对 tutorial.rst 进行小幅更新，并为 nodes/edges 的 data 方法添加 docstring (#5039)

  • 文档化 geometric_edges 并将其添加到主命名空间 (#5045)

  • 修复 trophic_levels 文档中的一个小错误 (#5087)

  • 重构 transitive_closure (#5052)

  • 修复有向图的 fast_gnp_random_graph 问题 (issue #3389) (#5077)

  • 通过调用适当的方法获取边数 (#5095)

  • 更新文档中的指导项目部分 (#5056)

  • 参数化最短路径节点检查测试 (#5078)

  • 创建 FUNDING.yml

  • 弃用 union name 参数 (#5114)

  • 更新 FUNDING.yml

  • vertex_cover：添加了对自环节点的支持 (#5104)

  • 更新核心开发团队 (#5119)

  • algorithms/operators/all.py 中更快的运算符 (#5121)

  • 文档：添加已完成项目的提案链接 (#5122)

  • rescale_layout 和 rescale_layout_dict 的字典输出中一致的返回类型 (#5091)

  • 将异常变量名 e 更改为 err (#5130)

  • assortativity 文档和代码中的小调整 (#5129)

  • 绘制有向图时，允许边样式为样式列表 (#5131)

  • 为 operators/binary.py 添加示例并进行小幅文档重构 (#5099)

  • 改进 gnp 生成器的随机图测试套件 (issue #5092) (#5115)

  • 为 all_simple_paths 添加关于检查路径存在性的说明 (#5059)

  • 修复装饰器中引发异常的消息 (#5136)

  • 重构 FancyArrowPatches 的线条样式测试 (#5132)

  • 弃用 Py37 (#5143)

  • 使用 math.hypot (#5145)

  • 将 pyupgrade 添加到 pre-commit (#5146)

  • 在 Python 3.10 上进行测试 (#4807)

  • 使用 black 21.9b0 (#5148)

  • 使用 sphinx 4.2 (#5150)

  • 更新示例要求 (#5151)

  • 更新 nx_pylab 绘制边颜色和宽度测试 (#5134)

  • 重构 node_classification 以提高简洁性和可读性 (#5144)

  • 添加临时 pyparsing 锁定以修复 CI (#5156)

  • 添加选项，允许 arrowsize 为列表 (#5154)

  • 列出策略 (#5159)

  • 问题 5123 的错误修复 (#5153)

  • 在 py3.10 上测试 scipy 和 pandas (#5174)

  • 弃用 node_classification 包中的 hmn 和 lgc 模块 (#5166)

  • 移除将 ax.transOffset 传递给 LineCollection 的操作 (#5173)

  • 添加一个使用 bellman_ford 查找负循环的函数 (#5089)

  • 在贡献者常见问题解答中添加关于算法接受策略的问答 (#5177)

  • 文档：修复加权最短路径文档中的拼写错误 (#5181)

  • 回滚“添加临时 pyparsing 锁定以修复 CI (#5156)” (#5180)

  • 仅在使用时计算最短路径长度 (#5183)

  • 添加 Mypy 类型检查基础设施 (#5127)

  • xfail pydot 测试 (#5187)

  • 从 algebraicconnectivity 中移除未使用的内部求解器 (#5190)

  • 移除关于 scipy 1.1 行为的检查/注释 (#5191)

  • 在 Python 3.10 上进行测试 (#5185)

  • 添加包含无向图的祖先/后代回归测试 (#5188)

  • 移除内部函数，转而使用高级索引 (#5197)

  • 修复 laplacian 函数中缺失的导入和测试 (#5194)

  • 调查预发布测试失败 (#5208)

  • 移除断言方法，转而使用 assert 语句 (#5214)

  • 移除 mycielski.py 中未使用的变量 (#5210)

  • 使用队列代替普通列表 (#5217)

  • 为 google_matrix 添加关于矩阵到数组输出的 FutureWarning (#5219)

  • 一些 np.matrix 清理工作 (#5218)

  • 移除内部 laplacian，转而使用 laplacian_matrix (#5196)

  • [MRG] 创建 plot_subgraphs.py 示例 (#5165)

  • 将旅行商问题添加到示例图库 (#4874)

  • 修复了 DiGraph.edges() 中 nbunch 参数文档不一致的问题 (#5037)

  • 与 numpy/scipy/pytest rc 测试的兼容性更新 (#5226)

  • 将内部 close 函数替换为 math.isclose (#5224)

  • 修复 Python 3.10 使用整除引发的弃用警告 (#5231)

  • 子图图库示例的修饰和建议 (#5225)

  • 使用新包名 (#5234)

  • 允许双向 Dijkstra 权重函数中使用 None 边 (#5232)

  • 添加关于分配问题的常见问题解答 (#5182)

  • 更新开发依赖 (#5243)

  • 更新带有 tex 符号的小文档问题 (#5244)

  • 为社区检测的异步标签传播算法进行小幅改动以加速 (#5247)

  • small.py 模块的 Docstring (#5240)

  • 使用 scipy.sparse 数组数据结构 (#5139)

  • 更新 sphinx (#5272)

  • 更新年份 (#5273)

  • 更新额外依赖 (#5263)

  • 更新文档中的 gexf 网站链接 (#5275)

  • 更新 numpydoc (#5274)

  • lazy_import 函数的初步设置 (#4909)

  • 弃用 scipy 稀疏矩阵转换函数 (#5262)

  • 修复 lowest_common_ancestors (issue #4942) (#5086)

  • 使小型图生成器节点测试更具体 (#5282)

  • 在 generators.small 中使用 from_dict_of_lists 代替 make_small_graph (#5267)

  • 使用高级索引重构 to_numpy_array (#5250)

  • 修复：更新 louvain_partitions 的阈值（在每个级别将 mod 更新为 new_mod）(#5284)

  • 为非连通图添加异常 (#5287)

  • 修复了 Tarjan 强连通分量算法的实现，使其时间复杂度为 O(|E|+|V|) 而不是 O(|V|^3)。 (#5288)

  • 为 karate club graph 添加权重 (#5285)

  • 修复变量 __all__ 中出现但在 NX2.7 文档中未列出的函数 (#5289)

  • 更新到 black 的稳定版本 (#5296)

  • 为 attr_matrix 添加 FutureWarning 以通知用户返回类型将发生变化 (#5300)

  • 文档：将 NXEP2 的状态更改为已接受，添加决议 (#5297)

  • 更新测试要求 (#5304)

  • 更新 scipy (#5276)

  • 文档：更新文档，包含 weight 参数的可调用对象 (#5307)

  • 更新 pygraphviz (#5314)

  • 在 to_numpy_recarray docstring 中记录默认 dtype (#5315)

  • 移除未使用的 AbstractSet (#5317)

  • 弃用 make_small_graph 和 make_small_undirected_graph (#5283)

  • 更新 draw_ docstring，包含使用示例 (#5264)

  • NX2.7 的更多 numpy.matrix 清理工作 (#5319)

  • 维护：清理 assortativity 模块，移除未使用的变量 (#5301)

  • 为绘制多重边标签添加信息性异常 (#5316)

  • 解决文档中函数完整路径的潜在方案 (#5049)

  • 维护：清理 link analysis 模块，移除未使用的变量 (#5306)

  • 使用 pytest-mpl (#4579)

  • 将 omega 保持在 [-1, 1] 范围内 (#5216)

  • 添加对查找包含一组节点的最大团的支持 (#5172)

  • 维护：移除不必要的辅助函数，使用内置方法生成线图 (#5327)

  • 从 dict_keys 对象采样已弃用 (#5337)

  • 增加了对 numpy.random.Generator 的支持 (#5336)

  • 更新匹配函数以进行错误验证和提高速度 (#4897)

  • 更新发布要求 (#5338)

  • 为 to_numpy_array 添加结构化 dtypes (#5324)

  • 弃用 to_numpy_recarray (#5330)

  • 2.7 版本说明初稿 (#5342)

  • 添加 pickle 和 yaml 迁移信息 (#5345)

  • 弃用 info (#5341)

  • 修复 pandas 警告 (#5346)

  • 在 3.11-dev 上进行测试 (#5339)

  • 指定为 2.7rc1 版本

  • 提升版本号

  • 更新发布流程 (#5348)

  • 更新指导项目信息，包括预期时间投入 (#5349)

  • 在示例中使用 np.random.default_rng + 其他更新 (#5356)

  • 移除 conda 不支持的内容 (#5361)

  • 修复 equidistant=True 时 spiral_layout 的问题 (#5354)

  • 修复文档 (#5364)

贡献者#

  • Will Badart

  • Ross Barnowski

  • Mathieu Bastian

  • Martin Becker

  • Anutosh Bhat

  • Alejandro Candioti

  • Divyansh

  • Andrew Eckart

  • Yossi Eliaz

  • Casper van Elteren

  • Simone Gasperini

  • Daniel Haden

  • Leo Klarner

  • Andrew Knyazev

  • Fabrizio Kuruc

  • Paarth Madan

  • Jarrod Millman

  • Achille Nazaret

  • NikHoh

  • Sultan Orazbayev

  • Dimitrios Papageorgiou

  • Aishwarya Ramasethu

  • Ryuki

  • Katalin Schmidt

  • Dan Schult

  • Mridul Seth

  • Cirus Thenter

  • James Trimble

  • Vadim

  • Hnatiuk Vladyslav

  • Aaron Z

  • eskountis

  • kpberry

本页内容