JuliaGraphs / JuliaGraphs/GraphsMatching.jl
Segfault in `maximum_weight_perfect_matching` when the graph does not have a perfect matching
Nobody has claimed this yet.
- Dominant language
- Julia
- Stars
- 20
- Forks
- 8
- Avg merge
- 9h 15m
- Merged PRs (30d)
- 1
Description
That's really not a nice behavior :\
the fault seems to be on BlossomV.jl side https://github.com/mlewe/BlossomV.jl/issues/25
Ok, in fact, the problem seems to originate from Blossom V itself, this is so bad :(
// Computes a perfect matching of minimum cost.
// NOTE: a perfect matching of finite cost must exist (otherwise the behaviour is not specified).
We can get around this by adding dummy edges with big weights.
Contributor guide
No contributing guide indexed for this repository
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.
Research direction
Reproduce maximum_weight_perfect_matching on a graph without a perfect matching, then inspect its entry point and the referenced BlossomV.jl issue #25. Before changing behavior, determine and document the intended non-segfault outcome, since the issue only notes dummy edges as a possible workaround.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- julia
- Domain
- data
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100