Skip to content

Segfault in maximum_weight_perfect_matching when the graph does not have a perfect matching #10

New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

#

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

Jump to bottom
Open
etiennedeg opened this issue May 2, 2024 · 0 comments · May be fixed by #11
Open

Segfault in maximum_weight_perfect_matching when the graph does not have a perfect matching #10

etiennedeg opened this issue May 2, 2024 · 0 comments · May be fixed by #11

Comments

@etiennedeg
Copy link
Member

etiennedeg commented May 2, 2024 •
edited
Loading

That's really not a nice behavior :\

the fault seems to be on BlossomV.jl side mlewe/BlossomV.jl#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.
@etiennedeg etiennedeg linked a pull request May 3, 2024 that will close this issue
Open
# for free to join this conversation on GitHub. Already have an account? # to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

fix blossom etiennedeg/GraphsMatching.jl
1 participant
@etiennedeg