implementing the Blossom algorithm for maximum weight matching
Nadie ha tomado este issue todavía.
Evaluación
- Dificultad
- 5/5
- Tiempo estimado
- Más de una semana
- Aptitud para principiantes
- 25/100
Línea de trabajo
Comienza con la descripción general del algoritmo Blossom enlazada en el issue e inspecciona cómo BlossomV.jl y LEMONGraphs.jl proporcionan actualmente soporte para matching. Define el alcance de una implementación puramente en Julia, incluidos los tests, la documentación, la selección predeterminada y la gestión de dependencias; la finalización debe cubrir esas piezas solicitadas y determinar si el rendimiento cumple el objetivo indicado.
Escrito por el modelo de indexación a partir del texto del issue.
Descripción
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
- Lenguaje dominante
- Julia
- Estrellas
- 20
- Forks
- 8
- Merge medio
- 9 h 15 min
- PR fusionados (30 d)
- 1
Preparar el entorno
Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.
Primeros pasos
- Lee el issue completo y luego la guía de contribución del proyecto.
- Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
- Haz un fork del repositorio y trabaja en una rama.
- Abre un pull request que haga referencia al número del issue.
Más de JuliaGraphs/GraphsMatching.jl
-
Dificultad 3/5 1-2 días Aptitud para principiantes 45/100
-
[BUG] different JuMP optimizers give different results in `maximum_weight_matching`Quizá libre de nuevo @Krastanov la tomó hace 452 días y no hay ningún pull request abierto. Abiertobug
JuliaGraphs/GraphsMatching.jl#24 · 1 asignado ·
-
Dificultad 5/5 Más de una semana Aptitud para principiantes 28/100
-
Segfault in `maximum_weight_perfect_matching` when the graph does not have a perfect matchingPosiblemente ocupada @etiennedeg la tomó hace 889 días. Abierto
Dificultad 4/5 3-5 días Aptitud para principiantes 25/100
-
Code from GitHub example failsAbierto
Dificultad 3/5 1-2 días Aptitud para principiantes 35/100
JuliaGraphs/GraphsMatching.jl#7 · 4 comentarios ·
Todos los issues de JuliaGraphs/GraphsMatching.jl
Issues similares
-
Add DocStringExtensionsAbiertodocumentation
Dificultad 2/5 1-3 horas Aptitud para principiantes 62/100
ohno/Antique.jl#165 ·
-
Dificultad 2/5 1-3 horas Aptitud para principiantes 78/100
JuliaLang/LinearAlgebra.jl#1749 ·
Los mantenedores suelen responder en 2 días
-
Dificultad 2/5 1-3 horas Aptitud para principiantes 62/100
-
Dificultad 2/5 1-3 horas Aptitud para principiantes 68/100
grame-cncm/faust#1344 · 1 comentario ·
Los mantenedores suelen responder en 1 día
-
Dificultad 2/5 1-3 horas Aptitud para principiantes 70/100
SciML/DiffEqNoiseProcess.jl#342 ·