<p><strong>Background:</strong></p>

<p>I've ported <a href="https://en.wikipedia.org/wiki/Blossom_algorithm" rel="nofollow noreferrer">Edmonds Blossom Algorithm</a> with <strong>Maximum Weighted Matching</strong> to Java:</p>

<blockquote>
  <p><a href="https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java" rel="nofollow noreferrer">https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java</a></p>
</blockquote>

<p>The original <a href="http://jorisvr.nl/files/graphmatching/20130407/mwmatching.py" rel="nofollow noreferrer">Python implementation</a> was written by <a href="http://jorisvr.nl/" rel="nofollow noreferrer">Joris van Rantwijk</a> and the papers he based it on are referenced on his <a href="http://jorisvr.nl/article/maximum-matching" rel="nofollow noreferrer">website</a>.</p>

<p>Unfortunately the speed is not adequate for my use case, so I'm looking to improve this. I have added some slow tests to the repo that I will use to measure the performance improvements.</p>

<p>I have further done some research and came up with the following <strong>three</strong> options to improve performance:</p>

<ul>
<li>Parallelizing Edmonds Blossom, in particular reference is this <a href="https://github.com/Xelaadryth/Edmonds-Parallel" rel="nofollow noreferrer">implementation</a></li>
<li>Variable Dual Updates and the use of Priority Queues as described in <a href="https://link.springer.com/article/10.1007/s12532-009-0002-8" rel="nofollow noreferrer">Blossom V</a></li>
</ul>

<p>Based on the Blossom V paper I'm expecting at least improvements in the order of one or two magnitudes. The reference to the parallel approach is unfortunately no longer available.</p>

<p><strong>Questions:</strong></p>

<p>Now before I get started on in-depth reading and more coding I have some questions that I hope will help me channel my efforts:</p>

<ol>
<li>Are there any other algorithmic / implementation improvements available to increase performance significantly?</li>
<li>Are there any papers available on parallelizing the algorithm?</li>
<li>I want to do iterative improvements, do you see any reason why I can not add the suggested improvements independently?</li>
<li>What is the best order to add the improvements? What approach has the most value (complexity of implementation vs speed improvement) in your opinion (assuming ~10 cores) and why?</li>
<li>Is there code refactoring / separation you would recommend doing before starting on optimization?</li>
</ol>

<p><strong>Disclaimer / Misc:</strong></p>

<p>I'm a big believer in <em>Open Source</em> and will keep <a href="https://github.com/simlu/EdmondsBlossom" rel="nofollow noreferrer">the repository</a> up with all the improvements I am making to it!</p>

<p><em>Note:</em> There is also a JavaScript port available <a href="https://github.com/mattkrick/EdmondsBlossom" rel="nofollow noreferrer">here</a>. However not as clean as the Python or Java version.</p>

<p><strong>Edit:</strong></p>

<p>Found a great paper on the Blossom V performance and where to best add parallelization <a href="http://userpages.umbc.edu/~gobbert/papers/REU2015Team6.pdf" rel="nofollow noreferrer">here</a>. That somewhat answers question (2).</p>

<p>I'm now wondering if I should start from scratch and just implement Blossom V.</p>

CC BY-SA 4.0
2018-08-06T03:43:28.527Z
Did you end up working on this more? I see you have https://github.com/mattkrick/EdmondsBlossom which looks like it's js not Java code?
How did you go with it? I'm looking at something similar.
Thanks!
Louise
CC BY-SA 4.0
2018-08-07T16:33:26.727Z
@Louise Pull request is in the work for jgrapht here: https://github.com/jgrapht/jgrapht/pull/595
vincent
CC BY-SA 4.0
2020-10-26T17:52:51.597Z
Couldn't you use the MV Matching Algorithm? https://arxiv.org/pdf/1210.4594.pdf
Fabian Bosler
CC BY-SA 4.0
2020-10-26T18:01:03.550Z
Micali-Vazirani does not support weights. So unfortunately not
vincent
<ds.algorithms><graph-theory><graph-algorithms><optimization><matching>
Optimizing Maximum Weighted Matching (Edmonds Blossom)
vincent
# Optimizing Maximum Weighted Matching (Edmonds Blossom)

(Asked by: username_0 on 2017-08-24)

**Background:**

I've ported [Edmonds Blossom Algorithm](https://en.wikipedia.org/wiki/Blossom_algorithm) with **Maximum Weighted Matching** to Java:

> <https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java>

The original [Python implementation](http://jorisvr.nl/files/graphmatching/20130407/mwmatching.py) was written by [Joris van Rantwijk](http://jorisvr.nl/) and the papers he based it on are referenced on his [website](http://jorisvr.nl/article/maximum-matching).

Unfortunately the speed is not adequate for my use case, so I'm looking to improve this. I have added some slow tests to the repo that I will use to measure the performance improvements.

I have further done some research and came up with the following **three** options to improve performance:

* Parallelizing Edmonds Blossom, in particular reference is this [implementation](https://github.com/Xelaadryth/Edmonds-Parallel)
* Variable Dual Updates and the use of Priority Queues as described in [Blossom V](https://link.springer.com/article/10.1007/s12532-009-0002-8)

Based on the Blossom V paper I'm expecting at least improvements in the order of one or two magnitudes. The reference to the parallel approach is unfortunately no longer available.

**Questions:**

Now before I get started on in-depth reading and more coding I have some questions that I hope will help me channel my efforts:

1. Are there any other algorithmic / implementation improvements available to increase performance significantly?
2. Are there any papers available on parallelizing the algorithm?
3. I want to do iterative improvements, do you see any reason why I can not add the suggested improvements independently?
4. What is the best order to add the improvements? What approach has the most value (complexity of implementation vs speed improvement) in your opinion (assuming ~10 cores) and why?
5. Is there code refactoring / separation you would recommend doing before starting on optimization?

**Disclaimer / Misc:**

I'm a big believer in *Open Source* and will keep [the repository](https://github.com/simlu/EdmondsBlossom) up with all the improvements I am making to it!

*Note:* There is also a JavaScript port available [here](https://github.com/mattkrick/EdmondsBlossom). However not as clean as the Python or Java version.

**Edit:**

Found a great paper on the Blossom V performance and where to best add parallelization [here](http://userpages.umbc.edu/~gobbert/papers/REU2015Team6.pdf). That somewhat answers question (2).

I'm now wondering if I should start from scratch and just implement Blossom V.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, optimization, matching

> **Comments:**
> **username_1**: Did you end up working on this more? I see you have https://github.com/mattkrick/EdmondsBlossom which looks like it's js not Java code? How did you go with it? I'm looking at something similar. Thanks!  
> **username_0**: @username_1 Pull request is in the work for jgrapht here: https://github.com/jgrapht/jgrapht/pull/595  
> **username_2**: Couldn't you use the MV Matching Algorithm? https://arxiv.org/pdf/1210.4594.pdf  
> **username_0**: Micali-Vazirani does not support weights. So unfortunately not  

---

## 0 answers

