不能满足所有需求的最小成本的最大流量 [英] Maximum flow with min cost that doesn't satisfy all demands

问题描述

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

I'm using NetworkX to solve a maximum-flow problem with more than one source and sink. I found a function that works relatively well in NetworkX called max_cost_flow however the issue I'm having is that it requires that the net demand be zero, in other words no sink should get less than it needs, otherwise an error is raised.

我可以使用什么(或如何修改此算法)来让它计算出可能的最佳流量，而不必满足所有条件?

What can I use (or how can I modify this algorithm) to allow it to calculate the best possible flow and not necessarily the one satisfies all conditions?

根据克拉斯克维奇的建议:

Per kraskevich's suggestion:

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

推荐答案

1. 您可以通过创建新的源顶点并添加零成本边和从它到所有旧源的旧需求值，将多源流问题转换为单源问题.

1. You can convert a multi-source flow problem to a single-source problem by creating a new source vertex and adding edges with zero cost and the old value of demand from it to all old sources.

你可以对所有水槽做同样的事情(但边缘应该从旧水槽到新水槽).

You can do the same thing think with all sinks (but the edges should from the old sinks to a new one).

之后，您可以使用max_flow_min_cost 函数以最小的成本找到最大的流量(它不需要满足所有需求).

After that, you can use the max_flow_min_cost function to find the maximum flow with the smallest cost (it doesn't require all demands to be satisfied).

更新:您的代码中有一些错误.这是一个工作示例(我稍微更改了图表，使流量非零):

Upd: there're a few bugs in your code. Here's a working example (I have slightly changed the graph so that the flow is non-zero):

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

这篇关于不能满足所有需求的最小成本的最大流量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！