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?

  • 1
    $\begingroup$ What precisely is the criteria for the solution you want to find? What objective function are you trying to maximize? When you list 3 criteria, that's pretty confusing, as it's likely that no algorithm can simultaneously maximize all 3; so how do you want to deal with that? Please edit the question to be more precise in the problem statement. Then, tell us why you struggled to formulate this as an instance of the assignment problem. Lastly, note that requests for source code are off-topic here. $\endgroup$ – D.W. Nov 10 '16 at 1:28
  • 1
    $\begingroup$ I'm confused by you saying "general graph (allow uneven number of nodes)". By "uneven", do you just mean "odd" (i.e., not a multiple of two)? Otherwise, it sounds like you're talking about a bipartite graph that doesn't have the same number of nodes on each side. If your graph is bipartite, you don't need Edmonds' algorithm. Exactly what problem are you trying to solve? $\endgroup$ – David Richerby Nov 10 '16 at 9:46
  • $\begingroup$ Hello David. Yes I just mean odd. What I meant by that, is that I've seen papers written on the subject, where there tends to be a problem if the total sum of nodes is an odd number. This problem definetly revolves around a general graph, as there is only a single list of nodes, where every node can be matched with a single other node in that list and only be matched with a total of 1 node. $\endgroup$ – user61192 Nov 10 '16 at 9:54

Your Answer

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