NetworkX 1.9#

发布日期：2014年6月21日

在此版本中放弃对Python 3.1的支持。

亮点#

  • 完全重写的最大流和基于流的连通性算法，具有不兼容的接口

  • 社区图生成器

  • Stoer-Wagner最小割算法

  • 线性时间欧拉回路算法

  • 线性代数包更改为使用SciPy稀疏矩阵

  • 代数连接性，Fiedler向量，谱排序算法

  • 链接预测算法

  • Goldberg-Radzik最短路径算法

  • 半连通图和树识别算法

流包#

流包（networkx.algorithms.flow ）已完全重写，具有向后*不兼容*的更改。它引入了流算法的新接口。现有使用流包的代码将无法在NetworkX 1.9中不经修改地工作。

主要更改#

  1. 我们添加了两个新的最大流算法（preflow_push 和:samp:shortest_augmenting_path ），并在:samp:flow_fulkerson 中重写了Edmonds-Karp算法，现在在:samp:edmonds_karp 中。 @ysitu 贡献了所有新的最大流算法的实现。在下一个版本中，仍可使用:samp:ford_fulkerson 中的传统Edmonds-Karp算法实现，但将被移除。

  2. 所有最大流算法实现（包括传统的:samp:ford_fulkerson ）现在在计算最大流后输出一个剩余网络（即:samp:DiGraph ）。请参阅:samp:maximum_flow 文档，了解NetworkX用于定义剩余网络的约定细节。

  3. 我们移除了旧的:samp:max_flow 和:samp:min_cut 函数。流算法的主要入口现在是函数:samp:maximum_flow 、maximum_flow_value 、minimum_cut 和:samp:minimum_cut_value ，它们具有控制最大流计算的新参数：flow_func 用于指定执行实际计算的算法（它接受一个实现最大流算法的函数作为参数）、cutoff 用于建议算法停止的最大流值、value_only 用于在获得流值后立即停止计算，以及:samp:residual 接受一个剩余网络作为参数，以便在重复的最大流计算中重复使用。

  4. 所有流算法都需要接受这些参数的参数，但可以有选择地忽略不适用的参数。例如，如果我们只需要流值，那么:samp:preflow_push 算法可以在预流阶段后停止而不计算最大流，但:samp:edmonds_karp 和:samp:shortest_augmenting_path 始终计算最大流以获得流值。

  5. 新函数:samp:minimum_cut 返回割值和一个节点 定义最小割的分区。函数:samp:minimum_cut_value 仅返回割的值，这是在1.9之前被移除的:samp:min_cut 函数返回的内容。

  6. 实现流算法的函数（即:samp:preflow_push , edmonds_karp , shortest_augmenting_path 和 ford_fulkerson ）未被导入到基本的NetworkX命名空间中。您必须从流包中显式导入它们：

>>> from networkx.algorithms.flow import (ford_fulkerson, preflow_push,
...        edmonds_karp, shortest_augmenting_path)

  1. 我们还添加了一个容量缩放最小成本流算法:samp:capacity_scaling 。它支持:samp:MultiDiGraph 和不连通的网络。

示例#

以下是一些小例子，演示如何使用1.9中引入的新流算法接口获得与NetworkX 1.8.1相同的输出：

>>> import networkx as nx
>>> G = nx.icosahedral_graph()
>>> nx.set_edge_attributes(G, 'capacity', 1)

使用NetworkX 1.8:

>>> flow_value = nx.max_flow(G, 0, 6)  
>>> cut_value = nx.min_cut(G, 0, 6)  
>>> flow_value == cut_value  
True
>>> flow_value, flow_dict = nx.ford_fulkerson(G, 0, 6)

使用NetworkX 1.9:

>>> from networkx.algorithms.flow import (ford_fulkerson, preflow_push,
...        edmonds_karp, shortest_augmenting_path)  
>>> flow_value = nx.maximum_flow_value(G, 0, 6)  
>>> cut_value = nx.minimum_cut_value(G, 0, 6)  
>>> flow_value == cut_value  
True
>>> # 旧版本：这返回与1.8.1中的ford_fulkerson完全相同的输出
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=ford_fulkerson)  
>>> # 我们强烈建议使用新算法：
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6)  
>>> # 如果未传递flow_func作为参数，则使用默认的flow_func（preflow-push）。因此，这与以下内容相同：
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=preflow_push)  
>>> # 您还可以使用替代的最大流算法：
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=shortest_augmenting_path)  
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=edmonds_karp)

连接包#

来自连接包（networkx.algorithms.connectivity ）的基于流的连接和割算法已经适应了新的流算法接口。因此，基于流的连接算法对于某些问题，例如具有高度倾斜度分布的稀疏网络，在某些问题上比NetworkX 1.8快10倍。引入了一些不兼容的变化。

  • 本地连接和割的函数现在接受

为流接口定义的新参数的参数：

flow_func 用于定义执行基础最大流计算的算法，residual 接受 一个剩余网络作为参数，以便在重复的最大流计算中重用， 以及 cutoff 用于定义基础最大流算法停止的最大流值。与1.8相比的主要速度改进主要来自剩余网络的重用和使用 cutoff 。

  • 我们从基本命名空间中删除了基于流的局部连接性和切割函数。现在它们必须从连接性包中显式导入。基于流的连接性和切割函数的主要入口点是函数 edge_connectivity , node_connectivity , minimum_edge_cut , 和 minimum_node_cut 。所有这些函数都接受一对节点作为可选参数，用于计算局部连接性和切割。

  • 我们改进了连接性函数的辅助网络：用于节点连接性和最小节点切割的节点映射字典现在是辅助网络的图属性。因此，我们从连接性和切割函数的本地版本中删除了 mapping 参数。我们还将辅助有向图的参数名称从 aux_digraph 更改为 auxiliary 。

  • 我们将函数 all_pairs_node_connectivity_matrix 的名称更改为 all_pairs_node_connectivity 。该函数现在返回一个字典而不是NumPy 2D数组。我们为仅在 nbunch 中的节点对之间计算节点连接性添加了一个新参数 nbunch 。

  • 为在连接性包中使用 Stoer–Wagner 算法计算无向图的加权最小切割添加了一个 stoer_wagner 函数。该算法不基于最大流。还为此函数在实用程序包 (networkx.utils ) 中添加了几种堆实现。 对于没有经过优化属性访问的Python实现（例如CPython），推荐使用 BinaryHeap 而不是 PairingHeap ，尽管其渐近运行时间较慢。对于具有优化属性访问的Python实现（例如PyPy），PairingHeap 提供更好的性能。

其他新功能#

  • 在中心性包 (networkx.algorithms.centrality ) 中添加了一个 disperson 函数，用于计算图的离散度。

  • 添加了一个社区包 (networkx.generators.community ) 用于生成社区图。

  • 在连接性包 (networkx.algorithms.connectivity ) 中添加了一个 is_semiconnected 函数，用于识别半连通图。

  • 在 Euler 包中的 eulerian_circuit 函数

(networkx.algorithm.euler ) 已更改为使用线性时间算法。

  • 在函数包(networkx.functions )中添加了一个 non_edges 函数，用于枚举图中现有节点之间不存在的边。

  • 线性代数包(networkx.linalg )已更改为使用 SciPy 稀疏矩阵。

  • 在线性代数包(networkx.linalg )中添加了函数 algebraic_connectivity , fiedler_vector 和 spectral_ordering ，用于计算无向图的代数连接性、Fiedler 向量和谱排序。

  • 添加了一个链接预测包(networkx.algorithms.link_prediction )，提供与链接预测相关的功能。

  • 在读/写包(networkx.readwrite )中添加了对 graph6 和 sparse6 格式的写入支持。

  • 在最短路径包(networkx.algorithms.shortest_paths )中添加了一个 goldberg_radzik 函数，用于使用 Goldberg–Radzik 算法计算最短路径。

  • 添加了一个树包(networkx.tree )，提供树识别功能。

  • 在实用程序包(networkx.utils )中添加了一个上下文管理器 reversed ，用于临时地就地反转图。

其他更改#

  • 组件包(networkx.algorithms.components )中的函数，如 connected_components , connected_components_subgraph 现在返回生成器而不是列表。要恢复先前的行为，使用 list(connected_components(G)) 。

  • JSON 图包中的 JSON 辅助函数(networkx.readwrite.json_graph )已移除。请改用标准库中的函数（例如，json.dumps ）。

  • 不再支持 Python 3.1。对于 Jython 2.7 和 IronPython 2.7，添加了基本支持，尽管它们仍未得到官方支持。

  • 修复了许多已报告的问题。

On this page