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