capacity_scaling#

capacity_scaling(G, demand='demand', capacity='capacity', weight='weight', heap=<class 'networkx.utils.heaps.BinaryHeap'>)[源]#

在有向图 G 中找到满足所有需求的最小成本流。

这是一个容量缩放的逐次最短增广路径算法。

G 是一个有向图，包含边的成本和容量，其中节点具有需求，即它们希望发送或接收一定量的流。负需求表示节点希望发送流，正需求表示节点希望接收流。如果流入每个节点的净流量等于该节点的需求，则有向图 G 上的流满足所有需求。

参数:
GNetworkX 图

用于查找满足所有需求的最小成本流的有向图或多重有向图。

demand字符串

图 G 的节点应具有一个名为 demand 的属性，表示节点希望发送（负需求）或接收（正需求）的流量。请注意，需求的总和应为 0，否则问题无解。如果此属性不存在，则认为节点的需求为 0。默认值：‘demand’。

capacity字符串

图 G 的边应具有一个名为 capacity 的属性，表示该边可以支持的流量。如果此属性不存在，则认为该边具有无限容量。默认值：‘capacity’。

weight字符串

图 G 的边应具有一个名为 weight 的属性，表示在该边上发送一个单位流量产生的成本。如果不存在，则认为权重为 0。默认值：‘weight’。

heap类

算法中使用的堆类型。它应该是 MinHeap 的子类或实现兼容的接口。

如果要使用现有的堆实现，对于没有优化属性访问的 Python 实现（例如 CPython），建议使用 BinaryHeap 而不是 PairingHeap，尽管前者渐近运行时间较慢。对于优化属性访问的 Python 实现（例如 PyPy），PairingHeap 提供更好的性能。默认值：BinaryHeap。

返回:
flowCost整数

满足所有需求的最小成本流的成本。

flowDict字典

如果 G 是有向图，则返回一个以节点为键的字典的字典，其中 flowDict[u][v] 是边 (u, v) 上的流量。如果 G 是多重有向图，则返回一个以节点为键的字典的字典的字典，其中 flowDict[u][v][key] 是边 (u, v, key) 上的流量。

抛出:
NetworkXError

如果输入图不是有向图或不连通，则抛出此异常。

NetworkXUnfeasible

在以下情况下抛出此异常

  • 需求的总和不为零。此时，不存在满足所有需求的流。

  • 不存在满足所有需求的流。

NetworkXUnbounded

如果该有向图 G 存在具有负成本和无限容量的环，则抛出此异常。此时，满足所有需求的流的成本是无下界的。

另请参阅

network_simplex()

注意

如果边的权重是浮点数，则此算法无效。

示例

一个最小成本流问题的简单示例。

>>> 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, flowDict = nx.capacity_scaling(G)
>>> flowCost
24
>>> flowDict
{'a': {'b': 4, 'c': 1}, 'd': {}, 'b': {'d': 4}, 'c': {'d': 1}}

可以更改算法使用的属性名称。

>>> G = nx.DiGraph()
>>> G.add_node("p", spam=-4)
>>> G.add_node("q", spam=2)
>>> G.add_node("a", spam=-2)
>>> G.add_node("d", spam=-1)
>>> G.add_node("t", spam=2)
>>> G.add_node("w", spam=3)
>>> G.add_edge("p", "q", cost=7, vacancies=5)
>>> G.add_edge("p", "a", cost=1, vacancies=4)
>>> G.add_edge("q", "d", cost=2, vacancies=3)
>>> G.add_edge("t", "q", cost=1, vacancies=2)
>>> G.add_edge("a", "t", cost=2, vacancies=4)
>>> G.add_edge("d", "w", cost=3, vacancies=4)
>>> G.add_edge("t", "w", cost=4, vacancies=1)
>>> flowCost, flowDict = nx.capacity_scaling(
...     G, demand="spam", capacity="vacancies", weight="cost"
... )
>>> flowCost
37
>>> flowDict
{'p': {'q': 2, 'a': 2}, 'q': {'d': 1}, 'a': {'t': 4}, 'd': {'w': 2}, 't': {'q': 1, 'w': 1}, 'w': {}}
在本页