最小流量，不满足所有需求

Question

我使用NetworkX来解决具有多个源和汇的最大流量问题。我发现一个在NetworkX中运行得相当好的函数叫做max_cost_flow，但是我遇到的问题是它要求净需求为零，换句话说，没有接收器应该小于它的需要，否则会引发错误。

我可以使用什么（或者我怎样才能修改这个算法）来允许它计算出最佳可能流量，而不一定满足所有条件？

每kraskevich的建议：

import networkx as nx 

def convert(graph): 

    allNodes = graph.nodes() 

    newSource = len(allNodes) + 1 
    newSink = len(allNodes) + 2 

    graph.add_node(newSource) 
    graph.add_node(newSink) 


    for currentNode in allNodes: 

     demand = graph.node[currentNode]['demand'] 

     if demand < 0 : 
      graph.add_edge(newSource, currentNode, weight=0, capacity=demand) 


     if demand > 0: 
      graph.add_edge(newSink, currentNode, weight=0, capacity=demand) 

    return graph 



g = nx.DiGraph() 

g.add_node(1, demand = 1) 
g.add_node(2, demand = -2) 
g.add_node(3, demand = 2) 
g.add_node(4, demand = -4) 

g.add_edge(1, 2, weight=4, capacity=100) 
g.add_edge(1, 4, weight=3, capacity=100) 
g.add_edge(3, 2, weight=5, capacity=100) 
g.add_edge(3, 4, weight=2, capacity=100) 
g.add_edge(3, 1, weight=1) 
newGraph = convert(g) 
print(nx.max_flow_min_cost(g, newGraph.nodes()[-2],newGraph.nodes()[-1])) 

Answer 1

1. 您可以通过创建一个新的源点，并添加具有零成本的旧值边缘转换多源流问题的单一来源问题对它的需求来自所有的旧资源。

2. 你可以用所有接收器来做同样的事情（但边缘应该从旧接收器到新接收器）。

3. 之后，您可以使用max_flow_min_cost函数来查找成本最小的最大流量（它不需要满足所有需求）。

更新：在你的代码中有一些错误。下面是一个工作示例（我稍微改变了图表，使流量不为零）：

import networkx as nx 

def convert(graph): 
    allNodes = graph.nodes() 
    newSource = len(allNodes) + 1 
    newSink = len(allNodes) + 2 

    graph.add_node(newSource) 
    graph.add_node(newSink) 

    for currentNode in allNodes: 
     demand = graph.node[currentNode]['demand'] 
     # Direction matters 
     # It goes FROM the new source and TO the new sink 
     if demand < 0: 
      graph.add_edge(newSource, currentNode, weight=0, capacity=-demand) 
     if demand > 0: 
      graph.add_edge(currentNode, newSink, weight=0, capacity=demand) 
     # We also need to zero out all demands 
     graph.node[currentNode]['demand'] = 0 
    return graph 



g = nx.DiGraph() 

g.add_node(1, demand = 1) 
g.add_node(2, demand = -2) 
g.add_node(3, demand = 2) 
g.add_node(4, demand = -4) 

g.add_edge(1, 2, weight=4, capacity=100) 
g.add_edge(1, 4, weight=3, capacity=100) 
g.add_edge(2, 3, weight=5, capacity=100) 
g.add_edge(4, 3, weight=2, capacity=100) 
g.add_edge(1, 3, weight=1) 
newGraph = convert(g) 
# The order of s and t matters here, too 
print(nx.max_flow_min_cost(g, g.nodes()[-2], g.nodes()[-1]))