implementing the Blossom algorithm for maximum weight matching

[Krastanov]

Edit: The bounty is removed as the urgency to fix this is gone now that we have working MWPM on all platforms thanks to LEMONGraphs.jl. Leaving this up as a feature request.

Implement the well-known Blossom algorithm for maximum weight (perfect) matching in generic graphs.

• wiki link: https://en.wikipedia.org/wiki/Blossom_algorithm
• many simple (not-optimized) implementations of the algorithm from class projects and the like are available if one searches online for "blossom algorithm simple"

Two bounties are available here:

• ~~a 500$ bounty~~ for implementing a pure-julia Blossom with tests and documentation, making it the default here, and moving BlossomV.jl from a dependency to a weak dependency (so that it is not necessary during installation)
• ~~a 500$ bounty~~ on improving the performance of the new implementation to no-worse than 90% of BlossomV.jl

[aybanda]

Hey @Krastanov submitted a PR, see if that helps

[cmhyett]

I'm certainly interested in implementing this - though obviously @aybanda should get first consideration for the 'exclusive' time if they want it.

Name: Criston Hyett github: cmhyett projects: contributor to MethodOfLines.jl, working on modeling PDEs/ROMs on networks, implemented the Hopcroft planarity testing algorithm (as a class project years ago), and coincidentally returning to graph matching algorithms in the context of optimal transport. This would be a nice deviation to learn a new alg.

[Krastanov]

Thank you both for the interest! For bigger bounties, usually (as mentioned in the description of the bounty program), I proceed like with a Google Summer of Code application -- I wait a few days to gather applications and then pick as many as I have funding and projects for. However, I do understand that preparing an actual application takes time, and I want to avoid duplication of effort, so I would suggest proceeding sequentially and seeing whether @aybanda's PR gains momentum.

Also, FYI, more Graph bounties will be coming (although possibly of a more limited scope and amount).

[AntoineBut]

Hey, I would love to contribute to this as well! I currently have a limited amount of time because of another big deadline, but I will have more time in a few weeks. If this goes as @Krastanov mentions (1 month for the first stage to get a working implementation with all tests, docs, benchmarks...), then I would love to look at the various ways to speed things up in the second stage as this happens to be the part I like the most.

• Name : Antoine Buttier
• github username : AntoineBut
• Previous project :

I am still fairly new to Julia (but I had the chance to learn from the best), I completed a project on parallelism in graph algorithms (in particular, BFS and coloring) under the supervision of @gdalle. The main outcome of this is on this repo, though we never really took the time to clean it up and make it comply with the usual standards.

The large graphs needed for benchmarking then led me to contribute some performance fixes on Graphs.jl (see dorogostev-mendes and greedy coloring).

I'll definitely be checking this from time to time and see if I find something to improve!

[Krastanov]

Thank you all for the expressed interest! For the time being we will give some exclusive time to Criston to engage with the first stage of the bounty. We will be opening related bounties throughout the Graph ecosystem and we will be sure to tag you to make sure we do not waste your tallents -- the julia graphs ecosystem would really benefit from your participation.

[omarsoufiane]

hello @Krastanov, I'm the founder of BountyHub which is a new platform dedicated to bounties on public GitHub repositories. It's one way to let the attempters know that the reward is already available. As a bounty creator you decide if the attempter should get the reward after submitting a pull request, and if no one solves your issue you can retract your bounty and get your money back. I would be very happy if you use it for your upcoming bounties.

[Krastanov]

Hi, @AntoineBut ! Are you still interested in this bounty? I was a bit slow to convey the messages, but Criston messaged me that he would not have the time to finish the work. If you are interested, both portions of the bounty are still available.

[AntoineBut]

Sure @Krastanov, I'd love to get a chance to work on this! And I need to freshen up my Julia development workflow for a new project that will start in February, so it looks like the perfect opportunity :))

[Krastanov]

great! Marking it as reserved for you

[AntoineBut]

Hi @Krastanov !

Im making a quick post to report on my progress after a month. I've got to admit the algorithm is trickier than I thought, and I wasn't able to make a working implementation yet. I've made good progress, which is available on this fork. Main data types are starting to get stable, initialization is working, and I started making progress on the core logic of the algorithm.

If that's okay, I'd love to get another week or two to see if I can get a first functioning prototype!

[Krastanov]

Thanks, @AntoineBut ! The 1month schedule is just a very rough guideline. No worries if you need another month.

[Krastanov]

Hi, @AntoineBut , how are things progressing?

[AntoineBut]

Hi @Krastanov !

Unfortunately, I could finish before the exams came around, and now the next semester has begun so I don't have much free time anymore.

If someone else wants to pick up the bounty they can, I'm happy to explain what I did so far to another contributor so they can carry on without starting from scratch. If no one else comes around I could maybe get back to it this summer.

Thank you nonetheless for the opportunity, and good luck to anyone up for this challenge!

[Krastanov]

Ok, I am opening this up again. Feel free to get back to it later on. Anyone else, feel free to reserve it as well.

[aybanda]

Hey @Krastanov I would appreciate the opportunity to try again if you're willing to assign me.

[Krastanov]

Certainly! Thanks for volunteering, it is much appreciated!

[Krastanov]

@aybanda , thanks for looking into this bounty! Could you let us know how things are going?

[Krastanov]

@aybanda , just checking in, let us know how things are going. There are other volunteers in the queue and just wanted to make sure they have a chance to tackle this if it is open.

[aybanda]

Hey @Krastanov really sorry that I could not reply earlier caught up with work, I'm almost ready with the PR you can expect this very soon.

[Krastanov]

hi, @aybanda ! I am really appreciative you have you expressed interest in this bounty, but I would like to open it up for other contributors in a day or two if you have not had a chance to complete it yet.

[simonschoelly]

Some suggestions:

• Why not implement the original blossom algorithm first? It only works for unweighted graphs - but as far as I know the Kolmogorov algorithm is based on that.
• Instead on creating an optimal algorithm create a working algorithm first - it might potentially waste one or two loop iterations and use non-optimal data structures but we can work from that on.
• JGraphT has an implementation that might be worth looking at.

[Krastanov]

I concur (and the bounty explicitly is split in two parts where the first one does not require a fast implementation at all)

A few other open source implementations:

• https://lemon.cs.elte.hu/trac/lemon
• https://github.com/igraph/igraph/issues/2403 (see the list in the first comment)
• https://github.com/igraph/igraph/pull/2550

[Krastanov]

Ok, let's do another round. @amicciche, you had expressed interest in this bounty. Could you comment here to confirm you indeed want to take on it for the next month or so?

[amicciche]

Yes! I'd love to give this a try. Thanks!

[Krastanov]

Sounds good, marking as reserved!

[amicciche]

While still interested in this bug bounty, I don't think I will be able to start working on it for a little while, and I think it would be best to let another interested person work on this.

[Krastanov]

The bounty is removed as the urgency to fix this is gone now that we have working MWPM on all platforms thanks to LEMONGraphs.jl. Leaving this up as a feature request.