6
$\begingroup$

Crossposted on Wolfram Community

A a minimum cost perfect matching is very useful tool.This three links about this demand just related me,let alone all MMA.SE.

But the in-built FindIndependentEdgeSet seem treat weight graph as non-weight graph directly,this often make me depressed.I found a ready-made algorithm for min cost perfect matching here.But as this declaration

The code above is licensed for research purposes only.

I don't sure Wolfram Research will have impetus to add this feature for FindIndependentEdgeSet in future.Can anyone be willing to implement this algorithm in Mathematica or more high efficiency method to improve FindIndependentEdgeSet?As I know,Blossom V itself is very high-efficiency.

Also,I hope the answer can meet a additional demand,that is it can accept negative edge weight value.Then if we use the negative weight value,we can get a maximal cost perfect matching,which is promising.

Help to imporove Mathematica,Help me,Please.

Improve this question
$\endgroup$
4
  • $\begingroup$ I feel like I've answered this before, here mathematica.stackexchange.com/a/109899/242 and here mathematica.stackexchange.com/a/112221/242. Both answers find a minimum cost perfect matching, IIRC? $\endgroup$
    – Niki Estner
    Apr 13, 2017 at 13:38
  • 2
    $\begingroup$ Regarding negative weights: why not just add a constant to all weights to make them nonnegative? This will add the same constant to all possible matchings, so it will not change the result $\endgroup$
    – Niki Estner
    Apr 13, 2017 at 13:39
  • $\begingroup$ Hello @nikie,note the difference of this question.Of course,it relate with my this question,which is about how to get a match with min cost from one list (against your this link) and hard define a direction cost(against your this link) $\endgroup$
    – yode
    Apr 13, 2017 at 13:54
  • $\begingroup$ @nikie As your second comment,see here,please. $\endgroup$
    – yode
    Apr 13, 2017 at 13:59

0

Reset to default

Your Answer

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