Skip to content
New issue

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

Sign up for GitHub

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

Already on GitHub? Sign in to your account

Jump to bottom

maximum_weighted_matching() segfaults with constant weights #199

Open
count0 opened this issue Jan 20, 2020 · 11 comments · May be fixed by #400
Open

maximum_weighted_matching() segfaults with constant weights #199

count0 opened this issue Jan 20, 2020 · 11 comments · May be fixed by #400
Labels
bug

Comments

@count0
Copy link

count0 commented Jan 20, 2020

Some graphs cause maximum_weighted_matching() to segfault due to a stack overflow when unit weights are used.

Please see minimal example linked below which is a simple modification of the standard example from the library.

https://gist.github.com/count0/551867e10973d4b2dc047b8528908281
@yi-ji
Copy link
Contributor

yi-ji commented Jan 25, 2020

Thank you for the bug report, I've confirmed it. I will look into it for a fix (might take me some time).
Meanwhile this might be is helpful: the O(n^4) implementation in an earlier commit seems to be fine, regarding this problem.

@count0
Copy link
Author

count0 commented Jan 28, 2020

@yi-ji Thanks for looking into it.

However, when trying the O(n^4) implementation from the commit you mentioned, I also get a segfault for the same example...

@count0
Copy link
Author

count0 commented Jan 2, 2022

@yi-ji is there any update on this? Or at least a previous version that is known to work?

@jeremy-murphy
Copy link
Contributor

If you have a minimal unit test that fails, I would be happy to merge that even without a fix.

Btw, if you two are regular users of BGL, we could do with help in terms of reviewing pull requests.
I don't have time to deeply check every pull request, and I don't actually expect other people to either, but at least if three people all agree that something looks good then we can merge it with some confidence.
And if it turns out to be bad, then no single person is to blame. ;)

@count0
Copy link
Author

count0 commented Jan 4, 2022

@jeremy-murphy The minimal unit test is here: https://gist.github.com/count0/551867e10973d4b2dc047b8528908281

I'd be happy to help reviewing pull requests.

@cmdawson
Copy link

cmdawson commented Jan 4, 2022 via email

@jeremy-murphy
Copy link
Contributor

Great. Can you all email me and we can start organizing.

@jeremy-murphy
Copy link
Contributor

I just realized, after all this time, that maybe you can't see my email address on my GitHub profile. :)
That's OK, now that I've rediscovered this thread and reminded myself who you are, I'll tag you on other issues of importance. I think this is not the only issue related to maximum_weighted_matching.

@SneakyPeaky
Copy link

SneakyPeaky commented Mar 31, 2023 •
edited
Loading

Can't boost just take any implementation from https://uoj.ac/problem/81 (see https://uoj.ac/submission/559649) ?
I am using the fastest implementation from there because boost fails with segfaults on random tests.

@jeremy-murphy
Copy link
Contributor

Can't boost just take any implementation from https://uoj.ac/problem/81 (see https://uoj.ac/submission/559649) ? I am using the fastest implementation from there because boost fails with segfaults on random tests.

I can't merge it if you haven't made a pull request for it.

@SneakyPeaky
Copy link

Can't boost just take any implementation from https://uoj.ac/problem/81 (see https://uoj.ac/submission/559649) ? I am using the fastest implementation from there because boost fails with segfaults on random tests.

I can't merge it if you haven't made a pull request for it.

Oh, no, I mean why don't @yi-ji just base his implementation on the one from in UOJ? Just scratch the whole
maximum_weighted_matching and replace it with code in link I sent. It's clearly much better.

@jorisvr jorisvr mentioned this issue Dec 5, 2024
Open
@jorisvr jorisvr linked a pull request Jan 13, 2025 that will close this issue
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Replace implementation of maximum_weighted_matching() jorisvr/boost-graph
5 participants
@count0 @cmdawson @jeremy-murphy @yi-ji @SneakyPeaky