Решение взвешенного сетевого потока с использованием Neo4J

Question

У меня есть двудольный график (заметки парня и девушки), где узлы связаны с взвешенными ребрами (насколько совместима пара девушка-парень), и каждый узел имеет емкость 5 (каждый парень / девушка может быть сопоставлен с 5 людьми противоположного Пол). Мне нужно найти лучшее возможное соответствие, чтобы максимизировать вес.

Это можно сформулировать как взвешенный сетевой поток - каждый парень является источником 5 единиц, каждая девушка является источником 5 единиц, а каждая возможная дуга имеет емкость 1 единицу. Проблема может быть решена либо с помощью линейного программирования, либо с помощью алгоритма обхода графа (например, Форда-Фулкерсона).

В настоящее время я ищу возможные решения с использованием Neo4j - кто-нибудь есть идеи, как это сделать? (или я должен просто пойти с решением линейного программирования...)

Answer 1

Я думаю, что-то вроде этого. Найдите пять самых COMPATIBLE отношения упорядочиваются по весу отношений в порядке убывания, а затем создают их как отдельные отношения MATCH,

match (guy:Guy)-[rel:COMPATIBLE]->(girl:Girl)
where guy.id = 'xx'
with guy, rel, girl
order by rel.weight desc
limit 5
create (guy)-[:MATCH]->(girl)