edge_disjoint_paths#

edge_disjoint_paths(G, s, t, flow_func=None, cutoff=None, auxiliary=None, residual=None)[source]#

返回源节点和目标节点之间的边不相交路径。

边不相交路径是不共享任何边的路径。源节点和目标节点之间的边不相交路径数量等于它们的边连通性。

参数:
GNetworkX 图
s节点

流的源节点。

t节点

流的汇节点。

flow_func函数

一个计算一对节点之间最大流的函数。该函数必须接受至少三个参数：一个有向图、一个源节点和一个目标节点。并返回一个遵循 NetworkX 约定（详见 maximum_flow()）的残差网络。如果 flow_func 为 None，则使用默认的最大流函数 (edmonds_karp())。默认函数的选择可能因版本而异，不应依赖。默认值：None。

cutoff整数或 None (默认值: None)

最大产出路径数。如果指定，当流值达到或超过 cutoff 时，最大流算法将终止。这仅适用于支持 cutoff 参数的流算法（大多数都支持），否则将被忽略。

auxiliaryNetworkX 有向图

用于计算基于流的边连通性的辅助有向图。它必须有一个名为 mapping 的图属性，该属性是一个字典，用于映射图 G 和辅助有向图中的节点名称。如果提供，将重用而不是重新创建。默认值：None。

residualNetworkX 有向图

用于计算最大流的残差网络。如果提供，将重用而不是重新创建。默认值：None。

返回:
paths生成器

一个边不相交路径的生成器。

引发:
NetworkXNoPath

如果源节点和目标节点之间没有路径。

NetworkXError

如果源节点或目标节点不在图 G 中。

另请参阅

node_disjoint_paths()
edge_connectivity()
maximum_flow()
edmonds_karp()
preflow_push()
shortest_augmenting_path()

注释

这是边不相交路径的一个基于流的实现。我们在辅助有向网络上计算源节点和目标节点之间的最大流。运行最大流算法后，残差网络中的饱和边对应于原始网络中源节点和目标节点之间的边不相交路径。此函数支持有向图和无向图，并且可以使用 NetworkX 流包中的所有流算法。

示例

在此示例中，我们使用柏拉图正二十面体图，该图的边连通性为 5，因此任意一对节点之间存在 5 条边不相交路径。

>>> G = nx.icosahedral_graph()
>>> len(list(nx.edge_disjoint_paths(G, 0, 6)))
5

如果您需要在同一个图上计算多对节点之间的边不相交路径，建议您重用 NetworkX 在计算中使用的 数据结构：用于边连通性的辅助有向图，以及用于底层最大流计算的残差网络。

如何在重用数据结构的情况下计算柏拉图正二十面体图所有节点对之间边不相交路径的示例。

>>> import itertools
>>> # You also have to explicitly import the function for
>>> # building the auxiliary digraph from the connectivity package
>>> from networkx.algorithms.connectivity import build_auxiliary_edge_connectivity
>>> H = build_auxiliary_edge_connectivity(G)
>>> # And the function for building the residual network from the
>>> # flow package
>>> from networkx.algorithms.flow import build_residual_network
>>> # Note that the auxiliary digraph has an edge attribute named capacity
>>> R = build_residual_network(H, "capacity")
>>> result = {n: {} for n in G}
>>> # Reuse the auxiliary digraph and the residual network by passing them
>>> # as arguments
>>> for u, v in itertools.combinations(G, 2):
...     k = len(list(nx.edge_disjoint_paths(G, u, v, auxiliary=H, residual=R)))
...     result[u][v] = k
>>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2))
True

您还可以使用替代的流算法来计算边不相交路径。例如，在密集网络中，算法 shortest_augmenting_path() 通常比默认的 edmonds_karp() 表现更好，后者对于度分布高度倾斜的稀疏网络更快。替代的流函数必须从 flow 包中显式导入。

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> len(list(nx.edge_disjoint_paths(G, 0, 6, flow_func=shortest_augmenting_path)))
5
在此页面上