NetworkX 1.9#

发布日期：2014 年 6 月 21 日

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

亮点#

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

  • 社区图生成器

  • Stoer–Wagner 最小割算法

  • 线性时间欧拉回路算法

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

  • 代数连通性、Fiedler 向量、谱排序算法

  • 链接预测算法

  • Goldberg–Radzik 最短路径算法

  • 半连通图和树识别算法

流包#

流包 (networkx.algorithms.flow) 已完全重写，包含向后不兼容的改动。它引入了一个新的流算法接口。使用旧版流包的现有代码在使用 NetworkX 1.9 时将无法直接工作。

主要改动#

  1. 我们新增了两个最大流算法 (preflow_push 和 shortest_augmenting_path)，并重写了 flow_fulkerson 中的 Edmonds–Karp 算法，该算法现在位于 edmonds_karp 中。 @ysitu 贡献了所有新最大流算法的实现。旧版 ford_fulkerson 中的 Edmonds–Karp 算法实现仍然可用，但将在下一版本中移除。

  2. 所有最大流算法实现（包括旧版 ford_fulkerson）现在在计算最大流后都会输出一个残差网络（即一个 DiGraph）。有关 NetworkX 定义残差网络的惯例详情，请参阅 maximum_flow 的文档。

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

  4. 所有流算法都需要接受这些参数作为参数，但可能会选择性地忽略不适用的参数。例如，如果我们只需要流值，preflow_push 算法可以在预流阶段结束后停止而不计算最大流，但 edmonds_karp 和 shortest_augmenting_path 总是计算最大流以获得流值。

  5. 新函数 minimum_cut 返回割值和一个定义最小割的节点分区。minimum_cut_value 函数仅返回割值，这正是 1.9 版本之前移除的 min_cut 函数返回的值。

  6. 实现流算法的函数（即 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. 我们还添加了一个容量缩放最小成本流算法：capacity_scaling。它支持 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
>>> # Legacy: this returns the exact same output than ford_fulkerson in 1.8.1
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=ford_fulkerson)  
>>> # We strongly recommend to use the new algorithms:
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6)  
>>> # If no flow_func is passed as argument, the default flow_func
>>> # (preflow-push) is used. Therefore this is the same than:
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=preflow_push)  
>>> # You can also use alternative maximum flow algorithms:
>>> 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) 中也添加了几种堆实现，用于此函数。BinaryHeap 比 PairingHeap 更推荐用于没有优化属性访问的 Python 实现（例如 CPython），尽管其渐近运行时间较慢。对于具有优化属性访问的 Python 实现（例如 PyPy），PairingHeap 提供了更好的性能。

其他新功能#

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

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

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

  • Euler 包 (networkx.algorithm.euler) 中的 eulerian_circuit 函数已更改为使用线性时间算法。

  • 在函数包 (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 图包 (networkx.readwrite.json_graph) 中的 JSON 助手已移除。请改用标准库中的函数（例如，json.dumps）。

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

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

在此页面上