implementing the Blossom algorithm for maximum weight matching
まだ誰も着手していません。
評価
調査の方向性
issue にリンクされている Blossom アルゴリズムの概要から始め、BlossomV.jl と LEMONGraphs.jl が現在どのように matching をサポートしているかを調査します。テスト、ドキュメント、デフォルト選択、依存関係の処理を含む、純粋な Julia 実装の範囲を定義します。完了時には、要求された項目を網羅し、パフォーマンスが提示された目標を満たすかどうかを明らかにする必要があります。
索引モデルが issue の本文から書いたものです。
説明
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
- 主要言語
- Julia
- スター
- 20
- フォーク
- 8
- 平均マージ
- 9時間 15分
- マージ済み PR（30日）
- 1
環境構築
このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
JuliaGraphs/GraphsMatching.jl のほかの issue
-
難易度 3/5 1〜2日 初心者へのやさしさ 45/100
-
[BUG] different JuMP optimizers give different results in `maximum_weight_matching`再び着手できるかも @Krastanov が 452 日前に担当しましたが、オープン中のプルリクエストはありません。 オープンbug
JuliaGraphs/GraphsMatching.jl#24 · 担当者 1 名 ·
-
難易度 5/5 1週間以上 初心者へのやさしさ 28/100
-
Segfault in `maximum_weight_perfect_matching` when the graph does not have a perfect matching対応中かも @etiennedeg が 889 日前に担当しました。 オープン
難易度 4/5 3〜5日 初心者へのやさしさ 25/100
-
難易度 3/5 1〜2日 初心者へのやさしさ 35/100
JuliaGraphs/GraphsMatching.jl#7 · コメント 4 件 ·
JuliaGraphs/GraphsMatching.jl の issue をすべて見る
似ている issue
-
documentation
難易度 2/5 1〜3時間 初心者へのやさしさ 62/100
ohno/Antique.jl#165 ·
-
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
JuliaLang/LinearAlgebra.jl#1749 ·
メンテナーはふだん 2 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 62/100
-
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
grame-cncm/faust#1344 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 70/100
SciML/DiffEqNoiseProcess.jl#342 ·