"""
容量图上的最大流（及最小割）算法。
"""
import networkx as nx
from .boykovkolmogorov import boykov_kolmogorov
from .dinitz_alg import dinitz
from .edmondskarp import edmonds_karp
from .preflowpush import preflow_push
from .shortestaugmentingpath import shortest_augmenting_path
from .utils import build_flow_dict
# Define the default flow function for computing maximum flow.
default_flow_func = preflow_push
__all__ = ["maximum_flow", "maximum_flow_value", "minimum_cut", "minimum_cut_value"]
[docs]
@nx._dispatchable(graphs="flowG", edge_attrs={"capacity": float("inf")})
def maximum_flow(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):
"""查找最大单商品流。
Parameters
----------
flowG : NetworkX 图
图的边应具有一个名为 'capacity' 的属性。如果该属性不存在，则认为该边具有无限容量。
_s : 节点
流的源节点。
_t : 节点
流的汇节点。
capacity : 字符串
图 G 的边应具有一个 capacity 属性，指示该边可以支持多少流量。如果该属性不存在，则认为该边具有无限容量。默认值：'capacity'。
flow_func : 函数
用于计算容量图中一对节点之间的最大流的函数。该函数至少需要接受三个参数：一个图或有向图、一个源节点和一个目标节点，并返回一个遵循 NetworkX 约定的残差网络（见注释）。如果 flow_func 为 None，则使用默认的最大流函数（:meth:`preflow_push` ）。请参阅下面的替代算法。默认函数的选取可能会随版本变化，不应依赖。默认值：None。
kwargs : 任何其他关键字参数都将传递给计算最大流的函数。
Returns
-------
flow_value : 整数, 浮点数
最大流的值，即从源节点流出的净流量。
flow_dict : 字典
包含每条边流量的字典。
Raises
------
NetworkXError
该算法不支持 MultiGraph 和 MultiDiGraph。如果输入图是这两个类之一的实例，则会引发 NetworkXError。
NetworkXUnbounded
如果图具有无限容量的路径，则图上可行流的值是无界的，函数会引发 NetworkXUnbounded。
See Also
--------
:meth:`maximum_flow_value`
:meth:`minimum_cut`
:meth:`minimum_cut_value`
:meth:`edmonds_karp`
:meth:`preflow_push`
:meth:`shortest_augmenting_path`
Notes
-----
flow_func 参数中使用的函数必须返回一个遵循 NetworkX 约定的残差网络：
从输入图 :samp:`G` 得到的残差网络 :samp:`R` 具有与 :samp:`G` 相同的节点。:samp:`R` 是一个有向图，如果 :samp:`(u, v)` 不是自环，并且 :samp:`(u, v)` 和 :samp:`(v, u)` 中至少有一个存在于 :samp:`G` 中，则 :samp:`R` 包含一对边 :samp:`(u, v)` 和 :samp:`(v, u)` 。
对于 :samp:`R` 中的每条边 :samp:`(u, v)` ，如果 :samp:`(u, v)` 在 :samp:`G` 中存在，则 :samp:`R[u][v]['capacity']` 等于 :samp:`(u, v)` 在 :samp:`G` 中的容量，否则为零。如果容量是无限的，:samp:`R[u][v]['capacity']` 将具有一个不影响问题解决方案的高任意有限值。该值存储在 :samp:`R.graph['inf']` 中。对于 :samp:`R` 中的每条边 :samp:`(u, v)` ，:samp:`R[u][v]['flow']` 表示 :samp:`(u, v)` 的流量函数，并满足 :samp:`R[u][v]['flow'] == -R[v][u]['flow']` 。
定义为流入汇节点 :samp:`t` 的总流量的流值存储在 :samp:`R.graph['flow_value']` 中。仅使用边 :samp:`(u, v)` 且 :samp:`R[u][v]['flow'] < R[u][v]['capacity']` 可达 :samp:`t` ，诱导出一个最小 :samp:`s` -:samp:`t` 割。
特定算法可能会在 :samp:`R` 中存储额外数据。
该函数应支持一个可选的布尔参数 value_only。当为 True 时，一旦可以确定最大流值和最小割，它可以选择性地终止算法。
Examples
--------
>>> G = nx.DiGraph()
>>> G.add_edge("x", "a", capacity=3.0)
>>> G.add_edge("x", "b", capacity=1.0)
>>> G.add_edge("a", "c", capacity=3.0)
>>> G.add_edge("b", "c", capacity=5.0)
>>> G.add_edge("b", "d", capacity=4.0)
>>> G.add_edge("d", "e", capacity=2.0)
>>> G.add_edge("c", "y", capacity=2.0)
>>> G.add_edge("e", "y", capacity=3.0)
maximum_flow 返回最大流的值和所有流量的字典。
>>> flow_value, flow_dict = nx.maximum_flow(G, "x", "y")
>>> flow_value
3.0
>>> print(flow_dict["x"]["b"])
1.0
您还可以使用 flow_func 参数使用替代算法计算最大流。
>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> flow_value == nx.maximum_flow(G, "x", "y", flow_func=shortest_augmenting_path)[0]
True
"""
if flow_func is None:
if kwargs:
raise nx.NetworkXError(
"You have to explicitly set a flow_func if"
" you need to pass parameters via kwargs."
)
flow_func = default_flow_func
if not callable(flow_func):
raise nx.NetworkXError("flow_func has to be callable.")
R = flow_func(flowG, _s, _t, capacity=capacity, value_only=False, **kwargs)
flow_dict = build_flow_dict(flowG, R)
return (R.graph["flow_value"], flow_dict)
[docs]
@nx._dispatchable(graphs="flowG", edge_attrs={"capacity": float("inf")})
def maximum_flow_value(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):
"""查找最大单商品流的值。
Parameters
----------
flowG : NetworkX 图
图的边预期具有一个名为 'capacity' 的属性。如果该属性不存在，则认为该边具有无限容量。
_s : 节点
流的源节点。
_t : 节点
流的汇节点。
capacity : 字符串
图 G 的边预期具有一个表示边支持流量的 capacity 属性。如果该属性不存在，则认为该边具有无限容量。默认值：'capacity'。
flow_func : 函数
用于计算容量图中一对节点之间最大流的函数。该函数至少需要接受三个参数：图或有向图、源节点和目标节点，并返回遵循 NetworkX 约定的残差网络（见注释）。如果 flow_func 为 None，则使用默认的最大流函数（:meth:`preflow_push` ）。请参阅下面的替代算法。默认函数的选取可能会随版本变化，不应依赖。默认值：None。
kwargs : 任何其他关键字参数将传递给计算最大流的函数。
Returns
-------
flow_value : 整数, 浮点数
最大流的值，即从源节点的净流出量。
Raises
------
NetworkXError
该算法不支持 MultiGraph 和 MultiDiGraph。如果输入图是这两个类之一的实例，则会引发 NetworkXError。
NetworkXUnbounded
如果图具有无限容量的路径，则图上可行流的值是无界的，函数会引发 NetworkXUnbounded。
See Also
--------
:meth:`maximum_flow`
:meth:`minimum_cut`
:meth:`minimum_cut_value`
:meth:`edmonds_karp`
:meth:`preflow_push`
:meth:`shortest_augmenting_path`
Notes
-----
flow_func 参数中使用的函数必须返回遵循 NetworkX 约定的残差网络：
输入图 :samp:`G` 的残差网络 :samp:`R` 具有与 :samp:`G` 相同的节点。:samp:`R` 是一个有向图，如果 :samp:`(u, v)` 不是自环，并且 :samp:`(u, v)` 和 :samp:`(v, u)` 中至少有一个存在于 :samp:`G` 中，则包含一对边 :samp:`(u, v)` 和 :samp:`(v, u)` 。
对于 :samp:`R` 中的每条边 :samp:`(u, v)` ，如果 :samp:`(u, v)` 在 :samp:`G` 中存在，则 :samp:`R[u][v]['capacity']` 等于 :samp:`(u, v)` 在 :samp:`G` 中的容量，否则为零。如果容量是无限的，:samp:`R[u][v]['capacity']` 将具有一个不影响问题解决方案的高任意有限值。该值存储在 :samp:`R.graph['inf']` 中。对于 :samp:`R` 中的每条边 :samp:`(u, v)` ，:samp:`R[u][v]['flow']` 表示 :samp:`(u, v)` 的流函数，并满足 :samp:`R[u][v]['flow'] == -R[v][u]['flow']` 。
定义为流入汇节点 :samp:`t` 的总流量的流值存储在 :samp:`R.graph['flow_value']` 中。仅使用边 :samp:`(u, v)` 到达 :samp:`t` ，使得 :samp:`R[u][v]['flow'] < R[u][v]['capacity']` ，诱导出最小 :samp:`s` -:samp:`t` 割。
特定算法可能会在 :samp:`R` 中存储额外数据。
该函数应支持一个可选的布尔参数 value_only。当为 True 时，它可以选择在确定最大流值和最小割后立即终止算法。
Examples
--------
>>> G = nx.DiGraph()
>>> G.add_edge("x", "a", capacity=3.0)
>>> G.add_edge("x", "b", capacity=1.0)
>>> G.add_edge("a", "c", capacity=3.0)
>>> G.add_edge("b", "c", capacity=5.0)
>>> G.add_edge("b", "d", capacity=4.0)
>>> G.add_edge("d", "e", capacity=2.0)
>>> G.add_edge("c", "y", capacity=2.0)
>>> G.add_edge("e", "y", capacity=3.0)
maximum_flow_value 仅计算最大流的值：
>>> flow_value = nx.maximum_flow_value(G, "x", "y")
>>> flow_value
3.0
您还可以使用 flow_func 参数使用替代算法计算最大流。
>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> flow_value == nx.maximum_flow_value(
... G, "x", "y", flow_func=shortest_augmenting_path
... )
True
"""
if flow_func is None:
if kwargs:
raise nx.NetworkXError(
"You have to explicitly set a flow_func if"
" you need to pass parameters via kwargs."
)
flow_func = default_flow_func
if not callable(flow_func):
raise nx.NetworkXError("flow_func has to be callable.")
R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)
return R.graph["flow_value"]
[docs]
@nx._dispatchable(graphs="flowG", edge_attrs={"capacity": float("inf")})
def minimum_cut(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):
"""计算最小 (s, t)-割的值和节点划分。
利用最大流最小割定理，即最小容量割的容量等于最大流的流量值。
Parameters
----------
flowG : NetworkX 图
图的边应具有名为 'capacity' 的属性。如果该属性不存在，则认为该边具有无限容量。
_s : 节点
流的源节点。
_t : 节点
流的汇节点。
capacity : 字符串
图 G 的边应具有一个表示边支持流量的 capacity 属性。如果该属性不存在，则认为该边具有无限容量。默认值：'capacity'。
flow_func : 函数
用于计算容量图中一对节点之间最大流的函数。该函数至少需要接受三个参数：图或有向图、源节点和目标节点，并返回遵循 NetworkX 约定的残差网络（见注释）。如果 flow_func 为 None，则使用默认的最大流函数（:meth:`preflow_push` ）。请参阅下面的替代算法。默认函数的选取可能会随版本变化，不应依赖。默认值：None。
kwargs : 任何其他关键字参数都将传递给计算最大流的函数。
Returns
-------
cut_value : 整数, 浮点数
最小割的值。
partition : 节点集对
定义最小割的节点划分。
Raises
------
NetworkXUnbounded
如果图具有无限容量的路径，所有割都具有无限容量，函数将引发 NetworkXError。
See Also
--------
:meth:`maximum_flow`
:meth:`maximum_flow_value`
:meth:`minimum_cut_value`
:meth:`edmonds_karp`
:meth:`preflow_push`
:meth:`shortest_augmenting_path`
Notes
-----
flow_func 参数中使用的函数必须返回遵循 NetworkX 约定的残差网络：
输入图 G 的残差网络 R 具有与 G 相同的节点。R 是一个有向图，如果 (u, v) 不是自环，并且 G 中至少存在 (u, v) 和 (v, u) 之一，则 R 包含一对边 (u, v) 和 (v, u)。
对于 R 中的每条边 (u, v)，R[u][v]['capacity'] 等于 G 中 (u, v) 的容量（如果存在）或零。如果容量是无限的，R[u][v]['capacity'] 将具有一个不影响问题解决方案的高任意有限值。该值存储在 R.graph['inf'] 中。对于 R 中的每条边 (u, v)，R[u][v]['flow'] 表示 (u, v) 的流函数，并满足 R[u][v]['flow'] == -R[v][u]['flow']。
定义为流入汇 t 的总流量的流值存储在 R.graph['flow_value'] 中。仅使用满足 R[u][v]['flow'] < R[u][v]['capacity'] 的边 (u, v) 可达 t 的路径诱导出一个最小 s-t 割。
特定算法可能会在 R 中存储额外数据。
该函数应支持一个可选的布尔参数 value_only。当为 True 时，一旦可以确定最大流值和最小割，算法可以选择性地终止。
Examples
--------
>>> G = nx.DiGraph()
>>> G.add_edge("x", "a", capacity=3.0)
>>> G.add_edge("x", "b", capacity=1.0)
>>> G.add_edge("a", "c", capacity=3.0)
>>> G.add_edge("b", "c", capacity=5.0)
>>> G.add_edge("b", "d", capacity=4.0)
>>> G.add_edge("d", "e", capacity=2.0)
>>> G.add_edge("c", "y", capacity=2.0)
>>> G.add_edge("e", "y", capacity=3.0)
minimum_cut 计算最小割的值和节点划分：
>>> cut_value, partition = nx.minimum_cut(G, "x", "y")
>>> reachable, non_reachable = partition
'partition' 是一个包含定义最小割的两个节点集的元组。你可以按如下方式计算诱导最小割的边集：
>>> cutset = set()
>>> for u, nbrs in ((n, G[n]) for n in reachable):
... cutset.update((u, v) for v in nbrs if v in non_reachable)
>>> print(sorted(cutset))
[('c', 'y'), ('x', 'b')]
>>> cut_value == sum(G.edges[u, v]["capacity"] for (u, v) in cutset)
True
你还可以使用 flow_func 参数使用替代算法计算最小割。
>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> cut_value == nx.minimum_cut(G, "x", "y", flow_func=shortest_augmenting_path)[0]
True
"""
if flow_func is None:
if kwargs:
raise nx.NetworkXError(
"You have to explicitly set a flow_func if"
" you need to pass parameters via kwargs."
)
flow_func = default_flow_func
if not callable(flow_func):
raise nx.NetworkXError("flow_func has to be callable.")
if kwargs.get("cutoff") is not None and flow_func is preflow_push:
raise nx.NetworkXError("cutoff should not be specified.")
R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)
# Remove saturated edges from the residual network
cutset = [(u, v, d) for u, v, d in R.edges(data=True) if d["flow"] == d["capacity"]]
R.remove_edges_from(cutset)
# Then, reachable and non reachable nodes from source in the
# residual network form the node partition that defines
# the minimum cut.
non_reachable = set(dict(nx.shortest_path_length(R, target=_t)))
partition = (set(flowG) - non_reachable, non_reachable)
# Finally add again cutset edges to the residual network to make
# sure that it is reusable.
if cutset is not None:
R.add_edges_from(cutset)
return (R.graph["flow_value"], partition)
[docs]
@nx._dispatchable(graphs="flowG", edge_attrs={"capacity": float("inf")})
def minimum_cut_value(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):
"""计算最小 (s, t)-割的值。
使用最大流最小割定理，即最小容量割的容量等于最大流的流量值。
Parameters
----------
flowG : NetworkX 图
图的边预期具有名为 'capacity' 的属性。如果此属性不存在，则认为该边具有无限容量。
_s : 节点
流的源节点。
_t : 节点
流的汇节点。
capacity : 字符串
图 G 的边预期具有一个表示边支持流量的 capacity 属性。如果此属性不存在，则认为该边具有无限容量。默认值：'capacity'。
flow_func : 函数
用于计算容量图中一对节点之间最大流的函数。该函数至少需要接受三个参数：图或有向图、源节点和目标节点。并返回遵循 NetworkX 约定的残余网络（见注释）。如果 flow_func 为 None，则使用默认的最大流函数（:meth:`preflow_push` ）。请参阅下面的替代算法。默认函数的选取可能会随版本变化，不应依赖。默认值：None。
kwargs : 任何其他关键字参数将传递给计算最大流的函数。
Returns
-------
cut_value : 整数, 浮点数
最小割的值。
Raises
------
NetworkXUnbounded
如果图具有无限容量的路径，所有割都具有无限容量，函数将引发 NetworkXError。
See Also
--------
:meth:`maximum_flow`
:meth:`maximum_flow_value`
:meth:`minimum_cut`
:meth:`edmonds_karp`
:meth:`preflow_push`
:meth:`shortest_augmenting_path`
Notes
-----
flow_func 参数中使用的函数必须返回遵循 NetworkX 约定的残余网络：
输入图 :samp:`G` 的残余网络 :samp:`R` 具有与 :samp:`G` 相同的节点。:samp:`R` 是一个有向图，如果 :samp:`(u, v)` 不是自环，并且 :samp:`(u, v)` 和 :samp:`(v, u)` 中至少有一个存在于 :samp:`G` 中，则包含一对边 :samp:`(u, v)` 和 :samp:`(v, u)` 。
对于 :samp:`R` 中的每条边 :samp:`(u, v)` ，:samp:`R[u][v]['capacity']` 等于 :samp:`G` 中 :samp:`(u, v)` 的容量（如果存在）或零。如果容量是无限的，:samp:`R[u][v]['capacity']` 将具有一个不影响问题解决方案的高任意有限值。该值存储在 :samp:`R.graph['inf']` 中。对于 :samp:`R` 中的每条边 :samp:`(u, v)` ，:samp:`R[u][v]['flow']` 表示 :samp:`(u, v)` 的流函数，并满足 :samp:`R[u][v]['flow'] == -R[v][u]['flow']` 。
定义为流入汇 :samp:`t` 的总流量的流值存储在 :samp:`R.graph['flow_value']` 中。仅使用边 :samp:`(u, v)` 且 :samp:`R[u][v]['flow'] < R[u][v]['capacity']` 可达 :samp:`t` 的可达性诱导出一个最小 :samp:`s` -:samp:`t` 割。
特定算法可能会在 :samp:`R` 中存储额外数据。
该函数应支持一个可选的布尔参数 value_only。当为 True 时，一旦可以确定最大流值和最小割，它可以选择性地终止算法。
Examples
--------
>>> G = nx.DiGraph()
>>> G.add_edge("x", "a", capacity=3.0)
>>> G.add_edge("x", "b", capacity=1.0)
>>> G.add_edge("a", "c", capacity=3.0)
>>> G.add_edge("b", "c", capacity=5.0)
>>> G.add_edge("b", "d", capacity=4.0)
>>> G.add_edge("d", "e", capacity=2.0)
>>> G.add_edge("c", "y", capacity=2.0)
>>> G.add_edge("e", "y", capacity=3.0)
minimum_cut_value 仅计算最小割的值：
>>> cut_value = nx.minimum_cut_value(G, "x", "y")
>>> cut_value
3.0
您还可以使用 flow_func 参数使用替代算法计算最小割。
>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> cut_value == nx.minimum_cut_value(
... G, "x", "y", flow_func=shortest_augmenting_path
... )
True
"""
if flow_func is None:
if kwargs:
raise nx.NetworkXError(
"You have to explicitly set a flow_func if"
" you need to pass parameters via kwargs."
)
flow_func = default_flow_func
if not callable(flow_func):
raise nx.NetworkXError("flow_func has to be callable.")
if kwargs.get("cutoff") is not None and flow_func is preflow_push:
raise nx.NetworkXError("cutoff should not be specified.")
R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)
return R.graph["flow_value"]
