python - 在汇源图中找到最小加权匹配

Question

我有三个节点列表。源、汇和管道。有一个从源到管道到汇的有向加权图。源仅连接到管道，管道仅连接到接收器。但是源不直接连接到接收器。管道是零和的，这意味着从源到每个管道的权重之和等于从该管道到汇的边的总和。

我想将最小数量的边添加到从接收器返回到源的图中，以便接收器和源也变成零和。我知道这个问题是 np-complete 我很想看看这个问题是否有任何好的多项式近似可以在现实生活中工作。

用更简单的话来说： 我有一个接收器和源的列表。每个接收器都有一个负数，每个源都有一个正数，因此图中节点中所有数字的总和为零（到目前为止没有边）。我想在该图中添加最小边数，以使出/入每个节点的边的权重之和等于该节点上的数量。

这是一个示例代码，用于测试一个图表是否总结了另一个图表：

from functools import reduce
from collections import Counter

source_edges = {
    "a0": {"p0": 1, "p2": 5}, 
    "a1": {"p0": 2}, 
    "a2": {"p1": 3}
}
sink_edges = {
    "b0": {"p0": 1},
    "b1": {"p0": 1, "p1": 1},
    "b2": {"p0": 1, "p1": 2, "p2": 5},
}
res = {
    "a0": {"b0": 1, "b2": 5}, 
    "a1": {"b1": 2}, 
    "a2": {"b2": 3}
}

sink_degs1 = {k: sum(v.values()) for k, v in sink_edges.items()} 
sink_degs2 = dict(reduce(lambda x, y: x + y, (Counter(v) for v in res.values())))
source_degs1 ={k: sum(v.values()) for k, v in res.items()} 
source_degs2 ={k: sum(v.values()) for k, v in source_edges.items()}

if sink_degs1 == sink_degs2 and source_degs1 == source_degs2:
    print('res summerizes the graph')
else:
    print('res does not summerize this graph')

以及该图的可视化：

Answer 1

这给出了具有少于 n-1 个边的次优解决方案。

from numpy.random import randint
from collections import defaultdict
import copy


def create_sample(source_count=5000, sink_count=200):
    diff = -1
    while diff < 0:
        sinks = [["b" + str(i), randint(source_count)] for i in range(sink_count)]
        sources = [["a" + str(i), randint(sink_count)] for i in range(source_count)]
        sink_sum = sum([x[1] for x in sinks])
        source_sum = sum([x[1] for x in sources])
        diff = sink_sum - source_sum
    avg_refill = diff // source_count + 1
    weights_match = False
    while not weights_match:
        for i in range(source_count):
            if not diff:
                break
            rnd = randint(avg_refill * 2.5) if diff > 10 * (avg_refill) else diff
            diff -= rnd
            sources[i][1] += rnd
        weights_match = sum([x[1] for x in sources]) == sum([x[1] for x in sinks])
    return sources, sinks


def solve(sources, sinks):
    src = sorted(copy.deepcopy(sources), key=lambda x: x[1])
    snk = sorted(copy.deepcopy(sinks), key=lambda x: x[1])
    res = []
    while snk:
        if src[0][1] > snk[0][1]:
            edge = (src[0][0], *snk[0])
            src[0][1] -= snk[0][1]
            del snk[0]
        elif src[0][1] < snk[0][1]:
            edge = (src[0][0], snk[0][0], src[0][1])
            snk[0][1] -= src[0][1]
            del src[0]
        else:
            edge = (src[0][0], *snk[0])
            del src[0], snk[0]
        res += [edge]
    return res


def test(sources, sinks):
    res = solve(sources, sinks)
    d_sources = defaultdict(int)
    d_sinks = defaultdict(int)
    w_sources = defaultdict(int)
    w_sinks = defaultdict(int)
    for a, b, c in res:
        d_sources[a] += 1
        d_sinks[b] += 1
        w_sources[a] += c
        w_sinks[b] += c
    print("source " + ("is" if dict(sources) == w_sources else "isn't") + " source")
    print("sink " + ("is" if dict(sinks) == w_sinks else "isn't") + " sink")
    print(
        f"source:\n \tdeg_sum = {sum(d_sources.values())}\n\tmax_deg = {max(d_sources.values())}"
    )
    print(
        f"sink:\n \tdeg_sum = {sum(d_sinks.values())}\n\tmax_deg = {max(d_sinks.values())}"
    )

这是一个示例运行：

In [1]: %run solver.py
In [2]: test(*create_sample())
source is source
sink is sink
source:
        deg_sum = 5196
        max_deg = 3
sink:
        deg_sum = 5196
        max_deg = 56

这是它如何工作的说明：

sources: 4,5,3,2
sinks: 2,7,2,2,1

sorted:
        55555|44|44|33|32|2
        77777|77|22|22|22|1
So we have 6 edges.

这是使用此算法的排序和未排序解决方案之间的比较：

---------------------------------------------
|                (1000,1000)                |
---------------------------------------------
| criteria          | sorted | random order |
| source degree sum | 1991   | 1999         |
| source max degree | 3      | 7            |
| sink degreee sum  | 1991   | 1999         |
| sink max degree   | 3      | 8            |
---------------------------------------------

---------------------------------------------
|                (200,5000)                 |
---------------------------------------------
| criteria          | sorted | random order |
| source degree sum | 5198   | 5198         |
| source max degree | 2      | 3            |
| sink degreee sum  | 5198   | 5198         |
| sink max degree   | 43     | 54           |
---------------------------------------------