edge_disjoint_paths#

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

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

边缘不相交路径是不共享任何边缘的路径。源和目标之间的边缘不相交路径数等于它们的边缘连接。

参数

G网络X图表
s结点: 流的源节点。
t结点: 流的汇聚节点。
flow_func功能: 一种函数，用于计算一对节点之间的最大流。该函数必须接受至少三个参数：有向图、源节点和目标节点。并返回遵循NetworkX约定的剩余网络(请参见 maximum_flow() 有关详细信息，请参见)。如果FLOW_FUNC为NONE，则默认的最大流量函数 (edmonds_karp() )被使用。默认功能的选择可能因版本不同而有所不同，不应依赖。默认值：无。
cutoff集成: 要放弃的最大路径数。一些最大流量算法，例如 edmonds_karp() (默认值)和 shortest_augmenting_path() 支持截断参数，当流量值达到或超过截止值时终止。其他算法将忽略此参数。默认值：无。
auxiliary网络X有向图: 计算基于流的边连通性的辅助有向图。它必须有一个名为map的图属性，并有一个字典映射G和辅助有向图中的节点名称。如果提供，它将被重复使用，而不是重新创建。默认值：无。
residual网络X有向图: 计算最大流量的残差网络。如果提供，它将被重复使用，而不是重新创建。默认值：无。

返回

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() 对于高度倾斜度分布的稀疏网络，这一点更快。必须从流包显式导入可选流函数。

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