Нахождение минимально взвешенного соответствия в графе источника приемника

У меня есть три списка узлов. источники, раковины и трубы. есть ориентированный взвешенный граф от источников к трубам и стокам. Источники подключаются только к трубам, а трубы только к раковинам. Но источники напрямую не связаны с раковинами. Трубы имеют нулевую сумму, что означает, что сумма весов, приходящих на каждую трубу от источников, равна сумме краев, идущих от этой трубы к раковинам.

Я хотел бы добавить минимальное количество ребер к этому графу от стоков обратно к источникам, чтобы сток и источники также стали нулевыми. Я знаю, что эта проблема 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')

И визуализация этого графика:

изображение графика


python graph algorithm graph-theory network-flow
person yukashima huksay    schedule 31.08.2019    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Это дает неоптимальное решение с менее чем 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           |
---------------------------------------------
person yukashima huksay    schedule 02.09.2019