모든 요구 사항을 만족하지 않는 최소 비용의 최대 플로우

Question

NetworkX을 사용하여 둘 이상의 소스 및 싱크에 대한 최대 플로우 문제를 해결합니다. 나는 NetworkX에서 비교적 잘 작동하는 함수를 찾았지만 그러나 문제는 순 수요가 0이어야한다는 것입니다. 즉 싱크가 필요 이상으로 줄어들지 않아야합니다. 그렇지 않으면 오류가 발생합니다.

최적의 흐름을 계산할 수 있도록 허용 할 수있는 방법 (또는이 알고리즘을 어떻게 수정할 수 있습니까?)이 모든 알고리즘이 반드시 모든 조건을 만족시키는 것은 아닙니까? 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 함수를 사용하여 가장 적은 비용으로 최대 플로우를 찾을 수 있습니다 (모든 요구 사항을 만족할 필요는 없습니다).

업데이트 : 코드에 몇 가지 버그가 있습니다. 다음은 작동하는 예제입니다 (그래프가 약간 변경되어 플로우가 0이 아니게되었습니다).

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