capacity_scaling#

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

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

这是一种容量缩放的连续最短增广路径算法。

G是一个有向图,具有边缘成本和容量,其中节点有需求,即它们希望发送或接收一定数量的流。负需求意味着节点想要发送流,正需求意味着节点想要接收流。如果流入每个节点的净流量等于该节点的需求,则有向图G上的流量满足所有需求。

参数
G网络X图表

找到满足所有要求的最小费用流的有向图或多重有向图。

demand字符串

图G的节点预期具有属性Demand,该属性指示节点想要发送(负需求)或接收(正需求)多少流。注意需求的总和应该是0,否则问题就不可行。如果该属性不存在,则节点被视为具有0需求。默认值:‘Demand’。

capacity字符串

图G的边被期望具有指示该边可以支持多少流的属性容量。如果不存在该属性,则认为该边具有无限容量。默认值:‘Capacity’。

weight字符串

图G的边预期具有属性权重,该属性权重指示在该边上发送一个单元流所产生的成本。如果不存在,则认为权重为0。缺省值:‘权重’。

heap班级

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

如果要使用库存堆实现, BinaryHeap 建议结束 PairingHeap 对于没有优化属性访问(如cpython)的Python实现,尽管运行时间较慢。对于具有优化属性访问(例如pypy)的python实现, PairingHeap 提供更好的性能。默认值: BinaryHeap .

返回
flowCost整数

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

flowDict词典

如果G是有向图,则是由节点键控的字典,使得FLOW DICT [u] [v] 是边上的流(u,v)。如果G是一个多重有向图,则是以节点为关键字的字典的字典,因此流字典 [u] [v] [key] 是边缘上的流(U、V、关键点)。

加薪
NetworkXError

如果输入图形未定向、未连接,则会引发此异常。

NetworkXUnfeasible

在以下情况下会引发此异常:

  • 这些要求的总和不是零。那么,就没有满足所有需求的流了。

  • 没有能满足所有需求的流量。

NetworkXUnbounded

如果有向图G有一个负成本和无限容量的圈,则会引发这个例外。然后,满足所有需求的流的成本在下面是无界的。

笔记

如果边权重是浮点数,则此算法不起作用。

实例

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

>>> 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': {}}