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

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

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

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

источник

2014-10-30 EugeneMi

Я думаю, что это что-то вроде этого. Найдите пять самых 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)

источник

2014-10-31 14:21:44

Thanks Dave! Тем не менее, это даст вам лучшее совпадение для первых парней, но остальные ребята получат либо плохие матчи, либо вообще никаких матчей. Взвешенный сетевой поток - это проблема оптимизации, которая пытается максимизировать вес всех совпадений. – EugeneMi

Это хороший ответ на другой вопрос. Я думаю, что вопрос непонятен, но я искал Форда-Фулкерсона, и я думаю, вам нужно максимизировать отдачу для всех узлов. Я не думаю, что это возможно с прямым Сайфером. – JohnMark13

Справа - я добавил предложение where в cypher, чтобы сосредоточиться только на одном парне. –

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

ответ

Смежные вопросы