网络X 1.9#

上映日期：2014年6月21日

在此版本中，不再支持Python3.1。

集锦#

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

  • 社区图生成器

  • 斯托尔-瓦格纳最小割法

  • 线性时间欧拉电路算法

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

  • 代数连通性、菲德勒向量、谱排序算法

  • 链接预测算法

  • Goldberg-Radzik最短路径算法

  • 半连通图和树识别算法

流程包#

流程包 (networkx.algorithms.flow ）完全用向后重写 不相容的 变化。它引入了一种新的流算法接口。使用流包的现有代码在未修改networkx 1.9的情况下无法工作。

主要变化#

  1. 我们添加了两个新的最大流量算法 (preflow_push 和 shortest_augmenting_path ）并在 flow_fulkerson 现在在 edmonds_karp . @ysitu 贡献了所有新的最大流量算法的实现。传统的Edmonds–karp算法实现 ford_fulkerson 仍然可用，但将在下一版本中删除。

  2. 所有最大流量算法实现（包括传统 ford_fulkerson ）现在输出剩余网络（即 DiGraph ）计算最大流量后。见 maximum_flow 有关networkx用于定义剩余网络的约定的详细信息的文档。

  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 只返回剪切值，这是删除的 min_cut 用于返回1.9之前的函数。

  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中介绍的新的流接口算法获得与Networkx1.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 ）是为了利用新的接口流算法。因此，对于某些问题（例如高度倾斜度分布的稀疏网络），基于流的连接算法比Networkx1.8快10倍。后退 不相容的 引入了变化。

  • 本地连接和剪切的函数现在接受为流接口定义的新参数的参数： flow_func 定义将执行基本最大流量计算的算法， residual 接受在重复的最大流量计算中重用的剩余网络作为参数，以及 cutoff 用于定义基本最大流算法停止的最大流值。与1.8相比，大幅提高速度主要是因为剩余网络的重用和 cutoff .

  • 我们从基名称空间中删除了基于流的本地连接和剪切函数。现在必须从连接包中显式导入它们。基于流的连通性和CUT函数的主要入口点是函数 edge_connectivity ， node_connectivity ， minimum_edge_cut 和 minimum_node_cut . 所有这些函数都接受几个节点作为计算本地连接和剪切的可选参数。

  • 我们改进了连接功能的辅助网络：节点连接和最小节点切割所需的节点映射dict现在是辅助网络的图形属性。因此我们移除了 mapping 连接和剪切函数的本地版本的参数。我们还将辅助有向图的参数名从 aux_digraph 到 auxiliary .

  • 我们更改了函数的名称 all_pairs_node_connectiviy_matrix 到 all_pairs_node_connectivity . 此函数现在返回字典而不是numpy 2d数组。我们添加了一个新参数 nbunch 仅用于计算中节点对之间的节点连接 nbunch .

  • A stoer_wagner 函数被添加到连接包中，用于使用Stoer–Wagner算法计算无向图的加权最小割集。该算法不基于最大流量。在实用程序包中还添加了几个堆实现 (networkx.utils ）用于此函数。 BinaryHeap 建议结束 PairingHeap 对于没有优化属性访问（如cpython）的Python实现，尽管运行时间较慢。对于具有优化属性访问（例如pypy）的python实现， PairingHeap 提供更好的性能。

其他新功能#

  • A disperson 函数添加到中心性包中 (networkx.algorithms.centrality ）用于计算图的分散度。

  • 社区套餐 (networkx.generators.community ）添加以生成社区图。

  • 安 is_semiconnected 在连接包中添加了函数 (networkx.algorithms.connectivity ）用于识别半连接图。

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

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

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

  • 功能 algebraic_connectivity ， fiedler_vector 和 spectral_ordering 在线性代数包中添加 (networkx.linalg ）用于计算无向图的代数连通性、费德勒向量和谱序。

  • 链路预测包 (networkx.algorithms.link_prediction ）添加以提供链接预测相关功能。

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

  • A goldberg_radzik 在最短路径包中添加函数 (networkx.algorithms.shortest_paths ）使用goldberg–radzik算法计算最短路径。

  • 树包 (networkx.tree ）添加以提供树识别功能。

  • 上下文管理器 reversed 添加到实用程序包中 (networkx.utils ）用于图的临时就地反转。

其他变更#

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

  • JSON图形包中的JSON帮助程序 (networkx.readwrite.json_graph 被移除。使用标准库中的函数（例如， json.dumps 相反。

  • 不再支持Python3.1。对Jython2.7和Ironpython 2.7添加了基本支持，尽管它们仍然没有得到正式支持。

  • 许多报告的问题都得到了解决。