This is a continuation of the problem described in this topic: Optimized algorithm to match entities together based on heuristics. I've come a little closer as to what might be the best solution.

I've got a general graph of nodes that contains edges which relate nodes to each other. These edges have a cost, which is calculated using a euclidean distance.

Now I wish to find the maximum amount of matches between these nodes (Where every node can only be connected to one other node), and from there I want to find the "cheapest" result in reference to the cost of the edges.

Currently I've been trying to bruteforce this problem, where I would "look ahead" to minimize the amount of time spend, but it's come to a point where my datasets are so big, that I'd have to split them into smaller groups, as it simply takes too long to calculate the best result.

I've been looking into Edmonds blossom matching algorithm as it seems to fit my needs. (If adjusted to use edge costs'). But I'm having a hard time wrapping my head around the full scale of it.

I've been trying to find some "easy-to-read" examples and pseudocode of it, but it seems very hard to find one that specifically searches for the following criteras:

  1. Most matches
  2. Lowest cost
  3. General graph (allow uneven number of nodes)

Does anyone know where I can find an example of some pseudocode that would fit the requirements above? Or maybe some working sourcecode in either C# or Java?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.