すべての要求を満たす最小コストの最大フロー

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]))