implementing the Blossom algorithm for maximum weight matching
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
Research direction
Start with the Blossom algorithm overview linked in the issue and inspect how BlossomV.jl and LEMONGraphs.jl currently provide matching support. Define the scope for a pure-Julia implementation, including tests, documentation, default selection, and dependency handling; completion should cover those requested pieces and establish whether performance meets the stated target.
Written by the indexing model from the issue text.
Description
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$ bountyfor implementing a pure-julia Blossom with tests and documentation, making it the default here, and movingBlossomV.jlfrom a dependency to a weak dependency (so that it is not necessary during installation)a 500$ bountyon improving the performance of the new implementation to no-worse than 90% ofBlossomV.jl
- Dominant language
- Julia
- Stars
- 20
- Forks
- 8
- PR merge metrics
- No merged PRs in 30d
Getting set up
This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from JuliaGraphs/GraphsMatching.jl
-
Difficulty 3/5 1-2 days Newbie friendliness 45/100
-
[BUG] different JuMP optimizers give different results in `maximum_weight_matching`May be free again @Krastanov claimed this 483 days ago, and no pull request is open. Openbug
JuliaGraphs/GraphsMatching.jl#24 · 1 assignee ·
-
Difficulty 5/5 Over a week Newbie friendliness 28/100
-
Segfault in `maximum_weight_perfect_matching` when the graph does not have a perfect matchingPossibly taken @etiennedeg claimed this 920 days ago. Open
Difficulty 4/5 3-5 days Newbie friendliness 25/100
-
Difficulty 3/5 1-2 days Newbie friendliness 35/100
JuliaGraphs/GraphsMatching.jl#7 · 4 comments ·
All issues in JuliaGraphs/GraphsMatching.jl
Similar issues
-
Difficulty 1/5 Under an hour Newbie friendliness 62/100
JuliaStats/LogExpFunctions.jl#134 · 2 comments ·
-
code bug PowerSystems 6.0
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
Sienna-Platform/PowerSystems.jl#1849 ·
Maintainers usually reply within 7 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
Maintainers usually reply within 1 day
-
Difficulty 1/5 1-3 hours Newbie friendliness 86/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
FluxML/Metalhead.jl#407 ·
Maintainers usually reply within 1 day