graph
graph copied to clipboard
boostorg
maximum_weighted_matching() segfaults with constant weights
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
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.
@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...
@yi-ji is there any update on this? Or at least a previous version that is known to work?
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. ;)
@jeremy-murphy The minimal unit test is here: https://gist.github.com/count0/551867e10973d4b2dc047b8528908281
I'd be happy to help reviewing pull requests.
Also happy to review pull requests.
On Tue, Jan 4, 2022 at 6:23 PM Tiago de Paula Peixoto < @.***> wrote:
@jeremy-murphy https://github.com/jeremy-murphy The minimal unit test is here: https://gist.github.com/count0/551867e10973d4b2dc047b8528908281
I'd be happy to help reviewing pull requests.
— Reply to this email directly, view it on GitHub https://github.com/boostorg/graph/issues/199#issuecomment-1004609090, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABABHWJIIN7XDDQIUO77ZTTUUKVBTANCNFSM4KJGVBMQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.
You are receiving this because you are subscribed to this thread.Message ID: @.***>
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.
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.
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.
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.