0

I have a bipartite graph (guy and girl notes) where nodes are connected with weighted edges (how compatible the girl-guy pair is) and each node has a capacity of 5 (each guy/girl can get matched to 5 people of the opposite gender). I need to find the best possible matching to maximize the weights.

This can be formulated as a weighted network flow - each guy is a source of 5 units, each girl is a sink of 5 units, and each possible arc has capacity of 1 unit. The problem can be solved either using linear programming, or a graph traversal algorithm (such as Ford–Fulkerson).

I'm currently looking into possible solutions using Neo4j - does anybody have any idea how to go about it? (or should I just go with a linear programming solution...)

1 Answer 1

0

I think it is something like this. Find the five most COMPATIBLE relationships ordering by the weight of the relationship in descending order and then create them as a separate relationship 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)
3
  • Thanks Dave! However, this will give you the best match for the first few guys, but the rest of the guys will get either poor matches, or no matches at all. Weighted network flow is an optimization problem that tries maximize the weight of all the matches
    – EugeneMi
    Oct 31, 2014 at 16:05
  • This is a good answer to a different question. I think that the question is unclear, but I looked up Ford-Fulkerson and I think you need to maximize return for all nodes. I don't think it is possible with straight Cypher.
    – JohnMark13
    Oct 31, 2014 at 16:08
  • Right - i added the where clause to the cypher to focus on just one guy. Oct 31, 2014 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.