NetworkX 1.10

发布日期：2015年8月2日

此版本中放弃了对 Python 2.6 的支持。

亮点

• 连通分量现在返回生成器

• 新增函数包括

  • enumerate_all_cliques, greedy_coloring, edge_dfs, find_cycle immediate_dominators, harmonic_centrality

  • Hopcraft–Karp 最大匹配算法

  • 最优分支和树形图。

  • all_simple_paths

• 从 GML 读取器/解析器中移除 pyparsing 依赖

• 改进流算法

• 与扩展图相关的新生成器。

• 多部图、非同构树、循环图的新生成器

• 允许图子类使用类似字典的对象代替字典

• 添加了有序图子类

• 添加了 pandas dataframe 读/写功能。

• G.edges() 中的 data 关键字允许直接请求边属性

• 扩展了节点子集的布局灵活性

• Kanesky 的割集和 k_components 算法

• 图的幂函数

• 节点连通性近似计算

• 传递闭包、三元组普查和反链

• 商图和子式

• DAGS 的 longest_path

• 模块度矩阵例程

API 变更

• [#1501] connected_components, weakly_connected_components 和 strongly_connected_components 现在返回节点集合的生成器。之前返回的是节点列表的生成器。此 PR 还重构了 connected_components 和 weakly_connected_components 的实现，使其更快，特别是对于大型图。

• [#1547] Di/Multi/Graphs 类中的 func_iter 函数计划在 NetworkX 2.0 版本中移除。func 将表现得像 func_iter，返回迭代器而不是列表。这些函数在 NetworkX 1.10 版本中已被弃用。

新功能

• [#823] 在 clique 包 (networkx.algorithms.clique) 中新增了一个 enumerate_all_cliques 函数，用于枚举无向图的所有团（包括非最大团）。

• [#1105] 创建了一个 coloring 包 (networkx.algorithms.coloring)，用于图着色算法。最初，提供了一个 greedy_color 函数，用于使用各种贪婪启发式算法为图着色。

• [#1193] 新增的生成器 edge_dfs，添加到 networkx.algorithms.traversal 中，实现了图的边深度优先遍历。这补充了对节点进行深度优先遍历所提供的功能。对于多重图，它允许用户精确地知道沿着哪些边进行了遍历。支持所有 NetworkX 图类型。遍历也可以反转边方向或忽略它们。

• [#1194] 在 networkx.algorithms.cycles 包中新增了 find_cycle 函数，用于在图中查找环。边方向可以选择性地反转或忽略。

• [#1210] 为复制-分化模型添加了一个随机生成器。

• [#1241] 新增了一个 networkx.algorithms.dominance 包，用于有向图的支配/支配者算法。它包含一个 immediate_dominators 函数，用于计算直接支配者/支配者树，以及一个 dominance_frontiers 函数，用于计算支配边界。

• [#1269] 重写了 GML 读取器/解析器和写入器/生成器，移除了对 pyparsing 的依赖，并支持处理任意图数据。

• [#1280] 重写了 networkx.algorithms.flow 包中的网络单纯形法，以提高其性能并支持多重网络和非连通网络。对于某些情况，新实现的性能比旧实现快两到三个数量级。

• [#1286] 添加了 Margulis–Gabber–Galil 图到 networkx.generators。

• [#1306] 添加了弦 p-环图，这是三正则扩展图族的一种温和显式的代数构造。此外，将现有的扩展图生成器函数（用于 Margulis-Gabber-Galil 扩展器）和新的弦循环图函数移动到一个新模块 networkx.generators.expanders。

• [#1314] 允许使用类似字典的对象覆盖基类字典：OrderedGraph, ThinGraph, PrintGraph 等。

• [#1321] 添加了 to_pandas_dataframe 和 from_pandas_dataframe。

• [#1322] 添加了 Hopcroft–Karp 算法，用于查找二分图中的最大基数匹配。

• [#1336] 扩展了 G.edges 中的 data 关键字，并添加了 default 关键字。

• [#1338] 添加了查找最优分支和树形图的支持。

• [#1340] 添加了一个 from_pandas_dataframe 函数，该函数接受 Pandas DataFrame 并返回一个新的图对象。DataFrame 至少必须包含两列，这两列定义了构成一条边的节点。然而，该函数还可以将任意数量的额外列作为边属性处理，例如 'weight'。

• [#1354] 扩展了布局函数，增加了灵活性，可以绘制具有不同布局的节点子集，并将每个布局以给定坐标为中心。

• [#1356] 添加了默认图类的有序变体。

• [#1360] 添加了调和中心性到 network.algorithms.centrality。

• [#1390] generators.bipartite 已被移动到 algorithms.bipartite.generators。这些函数未导入到主命名空间中，因此要使用它，必须导入 bipartite 包。

• [#1391] 添加了 Kanevsky 算法，用于查找无向图中的所有最小割点集。它被实现为一个节点割集生成器。

• [#1399] 添加了简单图的幂函数

• [#1405] 基于 White 和 Newman 用于查找两节点之间节点独立路径的近似算法，添加了节点连通性的快速近似算法。

• [#1413] 在 algorithms.dag 中为有向无环图添加了传递闭包和反链函数。反链函数由 Peter Jipsen 和 Franco Saliola 贡献，最初为 SAGE 项目开发。

• [#1425] 为完全多部图添加了生成器函数。

• [#1427] 添加了非同构树生成器。

• [#1436] 在 networkx.generators.classic 模块中为循环图添加了生成器函数。

• [#1437] 添加了计算商图的函数；同时创建了一个新模块 networkx.algorithms.minors。

• [#1438] 添加了 DAG 的 longest_path 和 longest_path_length。

• [#1439] 在 networkx.algorithms.minors 中添加了节点和边收缩函数。

• [#1445] 在 networkx.linalg 中添加了一个新的模块度矩阵模块，以及相关的谱函数到 networkx.linalg.spectrum 模块中。

• [#1447] 基于 Yen 的 k 最短路径算法，添加了生成所有简单路径（从最短路径开始）的函数到 algorithms.simple_paths。

• [#1455] 在 networkx.linalg.modularity_matrix 模块中添加了有向模块度矩阵。

• [#1474] 添加了 triadic_census 函数；同时创建了一个新模块 networkx.algorithms.triads。

• [#1476] 添加了函数，用于测试图是否包含加权或负加权边。还添加了函数，用于测试图是否为空。这些是 is_weighted, is_negatively_weighted 和 is_empty。

• [#1481] 添加了 Johnson 算法；另一种最短路径算法。它解决了所有对最短路径问题。这是 algorithms.shortest_paths 中的 johnson。

• [#1414] 添加了 Moody 和 White 算法，用于识别图中的 k_components，该算法基于 Kanevsky 算法，用于查找所有最小割点集（在 all_node_cuts #1391 中实现）。

• [#1415] 为 networkx.approximation 包添加了 k_components 的快速近似算法。这基于 White 和 Newman 用于查找两节点之间节点独立路径的近似算法（见 #1405）。

移除的功能

• [#1236] 遗留的 ford_fulkerson 最大流函数已被移除。请改用 edmonds_karp。

其他变更

• [#1192] 放弃了对 Python 2.6 的支持。