"""
有向连通图上的最小费用流算法。
"""
__all__ = ["min_cost_flow_cost", "min_cost_flow", "cost_of_flow", "max_flow_min_cost"]
import networkx as nx
[docs]
@nx._dispatchable(
node_attrs="demand", edge_attrs={"capacity": float("inf"), "weight": 0}
)
def min_cost_flow_cost(G, demand="demand", capacity="capacity", weight="weight"):
r"""找到满足有向图 G 中所有需求的最低成本流的成本。
G 是一个带有边成本和容量以及节点需求的有向图，即节点希望发送或接收一定量的流量。负需求表示节点希望发送流量，正需求表示节点希望接收流量。在有向图 G 上的流量满足所有需求，如果每个节点的净流入量等于该节点的需求。
Parameters
----------
G : NetworkX 图
要在其上找到满足所有需求的最低成本流的有向图。
demand : 字符串
图 G 的节点应具有一个表示节点希望发送（负需求）或接收（正需求）多少流量的需求属性。注意，需求的总和应为 0，否则问题不可行。如果此属性不存在，则认为节点具有 0 需求。默认值：'demand'。
capacity : 字符串
图 G 的边应具有一个表示边可以支持多少流量的容量属性。如果此属性不存在，则认为边具有无限容量。默认值：'capacity'。
weight : 字符串
图 G 的边应具有一个表示在该边上发送一个单位流量所产生的成本的权重属性。如果不存在，则认为权重为 0。默认值：'weight'。
Returns
-------
flowCost : 整数, 浮点数
满足所有需求的最低成本流的成本。
Raises
------
NetworkXError
如果输入图不是有向的或不连通，则引发此异常。
NetworkXUnfeasible
在以下情况下引发此异常：
* 需求的总和不为零。那么，没有满足所有需求的流量。
* 没有满足所有需求的流量。
NetworkXUnbounded
如果有向图 G 具有负成本和无限容量的循环，则引发此异常。那么，满足所有需求的流量的成本是无界的。
See Also
--------
cost_of_flow, max_flow_min_cost, min_cost_flow, network_simplex
Notes
-----
如果边权重或需求是浮点数，此算法不能保证工作（溢出和舍入误差可能导致问题）。作为一种解决方法，您可以通过将相关边属性乘以一个方便的常数因子（例如 100）来使用整数。
Examples
--------
一个简单的最低成本流问题示例。
>>> G = nx.DiGraph()
>>> G.add_node("a", demand=-5)
>>> G.add_node("d", demand=5)
>>> G.add_edge("a", "b", weight=3, capacity=4)
>>> G.add_edge("a", "c", weight=6, capacity=10)
>>> G.add_edge("b", "d", weight=1, capacity=9)
>>> G.add_edge("c", "d", weight=2, capacity=5)
>>> flowCost = nx.min_cost_flow_cost(G)
>>> flowCost
24
"""
return nx.network_simplex(G, demand=demand, capacity=capacity, weight=weight)[0]
[docs]
@nx._dispatchable(
node_attrs="demand", edge_attrs={"capacity": float("inf"), "weight": 0}
)
def min_cost_flow(G, demand="demand", capacity="capacity", weight="weight"):
r"""返回一个满足有向图 G 中所有需求的最低成本流。
G 是一个带有边成本和容量以及节点需求的有向图，即节点希望发送或接收一定量的流。负需求表示节点希望发送流，正需求表示节点希望接收流。如果每个节点的净流入量等于该节点的需求，则有向图 G 上的流满足所有需求。
Parameters
----------
G : NetworkX 图
要在其上找到满足所有需求的最低成本流的有向图。
demand : 字符串
图 G 的节点应具有一个表示节点希望发送（负需求）或接收（正需求）多少流的属性 demand。注意，需求的总和应为 0，否则问题不可行。如果此属性不存在，则认为节点具有 0 需求。默认值：'demand'。
capacity : 字符串
图 G 的边应具有一个表示边可以支持多少流的属性 capacity。如果此属性不存在，则认为边具有无限容量。默认值：'capacity'。
weight : 字符串
图 G 的边应具有一个表示在该边上发送一个单位流所产生的成本的属性 weight。如果不存在，则认为权重为 0。默认值：'weight'。
Returns
-------
flowDict : 字典
以节点为键的字典的字典，使得 flowDict[u][v] 是边 (u, v) 的流量。
Raises
------
NetworkXError
如果输入图不是有向的或不连通，则引发此异常。
NetworkXUnfeasible
在以下情况下引发此异常：
* 需求的总和不为零。那么，没有满足所有需求的流。
* 没有满足所有需求的流。
NetworkXUnbounded
如果有向图 G 具有负成本和无限容量的循环，则引发此异常。那么，满足所有需求的流的成本是无界的。
See Also
--------
cost_of_flow, max_flow_min_cost, min_cost_flow_cost, network_simplex
Notes
-----
如果边权重或需求是浮点数，此算法不保证能工作（溢出和舍入误差可能导致问题）。作为一种解决方法，可以通过将相关的边属性乘以一个方便的常数因子（例如 100）来使用整数。
Examples
--------
一个简单的最低成本流问题示例。
>>> G = nx.DiGraph()
>>> G.add_node("a", demand=-5)
>>> G.add_node("d", demand=5)
>>> G.add_edge("a", "b", weight=3, capacity=4)
>>> G.add_edge("a", "c", weight=6, capacity=10)
>>> G.add_edge("b", "d", weight=1, capacity=9)
>>> G.add_edge("c", "d", weight=2, capacity=5)
>>> flowDict = nx.min_cost_flow(G)
>>> flowDict
{'a': {'b': 4, 'c': 1}, 'd': {}, 'b': {'d': 4}, 'c': {'d': 1}}
"""
return nx.network_simplex(G, demand=demand, capacity=capacity, weight=weight)[1]
[docs]
@nx._dispatchable(edge_attrs={"weight": 0})
def cost_of_flow(G, flowDict, weight="weight"):
"""计算图G上由flowDict给定的流的费用。
请注意，此函数不检查flowDict流的有效性。如果图G和流不具有相同的边集，此函数将失败。
Parameters
----------
G : NetworkX图
要在其上找到满足所有需求的最低成本流的DiGraph。
weight : 字符串
图G的边应具有一个属性weight，该属性指示在该边上发送一个单位的流所产生的成本。如果不存在，则权重被视为0。默认值：'weight'。
flowDict : 字典
由节点键控的字典的字典，使得flowDict[u][v]是边(u, v)的流。
Returns
-------
cost : 整数, 浮点数
流的总成本。这是通过对所有边的流的乘积和边的权重求和得到的。
See Also
--------
max_flow_min_cost, min_cost_flow, min_cost_flow_cost, network_simplex
Notes
-----
如果边权重或需求是浮点数，此算法不保证能工作（溢出和舍入误差可能导致问题）。作为一种解决方法，您可以通过将相关的边属性乘以一个方便的常数因子（例如100）来使用整数。
Examples
--------
>>> G = nx.DiGraph()
>>> G.add_node("a", demand=-5)
>>> G.add_node("d", demand=5)
>>> G.add_edge("a", "b", weight=3, capacity=4)
>>> G.add_edge("a", "c", weight=6, capacity=10)
>>> G.add_edge("b", "d", weight=1, capacity=9)
>>> G.add_edge("c", "d", weight=2, capacity=5)
>>> flowDict = nx.min_cost_flow(G)
>>> flowDict
{'a': {'b': 4, 'c': 1}, 'd': {}, 'b': {'d': 4}, 'c': {'d': 1}}
>>> nx.cost_of_flow(G, flowDict)
24
"""
return sum((flowDict[u][v] * d.get(weight, 0) for u, v, d in G.edges(data=True)))
[docs]
@nx._dispatchable(edge_attrs={"capacity": float("inf"), "weight": 0})
def max_flow_min_cost(G, s, t, capacity="capacity", weight="weight"):
"""返回一个最小成本的最大 (s, t)-流。
G 是一个带有边成本和容量的有向图。图中有一个源节点 s 和一个汇节点 t。此函数找到从 s 到 t 的最大流，其总成本最小。
Parameters
----------
G : NetworkX 图
要在其上找到满足所有需求的最小成本流的 DiGraph。
s: 节点标签
流的源节点。
t: 节点标签
流的汇节点。
capacity: 字符串
图 G 的边应具有一个属性 capacity，指示该边可以支持多少流量。如果此属性不存在，则认为该边具有无限容量。默认值：'capacity'。
weight: 字符串
图 G 的边应具有一个属性 weight，指示在该边上发送一个单位的流量所产生的成本。如果不存在，则认为权重为 0。默认值：'weight'。
Returns
-------
flowDict: 字典
由节点键控的字典的字典，使得 flowDict[u][v] 是边 (u, v) 的流量。
Raises
------
NetworkXError
如果输入图不是有向的或不连通，则引发此异常。
NetworkXUnbounded
如果 G 中存在从 s 到 t 的无限容量路径，则引发此异常。在这种情况下，没有最大流。如果有向图 G 具有负成本和无限容量的循环，也会引发此异常。在这种情况下，流成本无下界。
See Also
--------
cost_of_flow, min_cost_flow, min_cost_flow_cost, network_simplex
Notes
-----
如果边权重或需求是浮点数，此算法不保证能正常工作（溢出和舍入误差可能导致问题）。作为一种解决方法，可以通过将相关边属性乘以一个方便的常数因子（例如 100）来使用整数。
Examples
--------
>>> G = nx.DiGraph()
>>> G.add_edges_from(
... [
... (1, 2, {"capacity": 12, "weight": 4}),
... (1, 3, {"capacity": 20, "weight": 6}),
... (2, 3, {"capacity": 6, "weight": -3}),
... (2, 6, {"capacity": 14, "weight": 1}),
... (3, 4, {"weight": 9}),
... (3, 5, {"capacity": 10, "weight": 5}),
... (4, 2, {"capacity": 19, "weight": 13}),
... (4, 5, {"capacity": 4, "weight": 0}),
... (5, 7, {"capacity": 28, "weight": 2}),
... (6, 5, {"capacity": 11, "weight": 1}),
... (6, 7, {"weight": 8}),
... (7, 4, {"capacity": 6, "weight": 6}),
... ]
... )
>>> mincostFlow = nx.max_flow_min_cost(G, 1, 7)
>>> mincost = nx.cost_of_flow(G, mincostFlow)
>>> mincost
373
>>> from networkx.algorithms.flow import maximum_flow
>>> maxFlow = maximum_flow(G, 1, 7)[1]
>>> nx.cost_of_flow(G, maxFlow) >= mincost
True
>>> mincostFlowValue = sum((mincostFlow[u][7] for u in G.predecessors(7))) - sum(
... (mincostFlow[7][v] for v in G.successors(7))
... )
>>> mincostFlowValue == nx.maximum_flow_value(G, 1, 7)
True
"""
maxFlow = nx.maximum_flow_value(G, s, t, capacity=capacity)
H = nx.DiGraph(G)
H.add_node(s, demand=-maxFlow)
H.add_node(t, demand=maxFlow)
return min_cost_flow(H, capacity=capacity, weight=weight)
