Neo4j中的完美匹配算法

Question

我尝试在cypher中实现perfect match算法，以在加权双峰网络中查找约束集(对)。

例如，有员工和他们可以执行的一组任务。一名员工可以完成多项任务。每个任务都有一个优先级，在这种情况下是一个边权重。考虑到优先级，我希望获得最优的任务-员工匹配。我想我应该遍历按degree x priority值排序的两个节点集，但我不知道如何迭代。

我已经浏览了目前Neo4j中包含的算法列表，但找不到任何类似的算法。我想知道是否有任何算法的实现或任何接近它的东西？我认为在Neo有一个可能是有用的。

Answer 1

我刚刚写了几篇博客文章，可能会对你有所帮助。

https://medium.com/@nsmith_piano/the-perfect-dorm-room-assignment-exploring-the-bipartite-matching-problem-with-neo4j-c59ade420acb

https://medium.com/@nsmith_piano/a-market-for-matches-finding-prices-with-neo4j-71ab085f8cd2

这是我用来匹配"student“和"room”节点的cypher。

CALL apoc.periodic.commit(
"MATCH (s:Student)
WHERE NOT s:Matched
WITH s LIMIT 1
CALL apoc.path.expandConfig(s, {relationshipFilter:'INTERESTED_IN,MATCHED_WITH,INTERESTED_IN',
nodeFilter:'Room|Student', 
minLevel:1, 
maxLevel:7, 
filterStartNode:false}) 
yield path AS alternatingPath
WITH s, alternatingPath,
nodes(alternatingPath)[-1] AS lastNode,
relationships(alternatingPath) as rels
WHERE lastNode:Room
AND NOT lastNode:Matched
WITH s, lastNode, rels
LIMIT 1
SET lastNode:Matched
SET s:Matched
WITH s, rels
UNWIND rels AS rel
CALL apoc.refactor.setType(rel, CASE TYPE(rel) WHEN 'MATCHED_WITH' THEN 'INTERESTED_IN' ELSE 'MATCHED_WITH' END) YIELD output
RETURN count(*)")