-
Notifications
You must be signed in to change notification settings - Fork 21
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.
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
Bug in maximum bipartite matching? #48
Comments
Thanks for the report. A first wild guess would be that the algorithm depends on some unreliable behavior, e.g., hash table ordering. I assume you're using a recent version of Racket? It's been a while since I've checked the tests against the latest Racket so I'm going to do that first. Then I will revisit this bug. |
Thanks for the response! Yes, that's right: v7.2. Your suspicions here sound like good intuition to me, for sure. |
I think I see the problem. The Looking into possible fixes. |
Hm.. That makes some sense, but isn't the standard reduction from network
flow to bipartite graph matching performed on directed graphs?
For example, the middle pages of these slides gives the reduction I'm
familiar with:
https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/matching.pdf
Thanks for your work on this! No particular rush, I realize you have other
things going on. If you can think of a fix that you think works, I might be
able to learn enough about your codebase to write some stress tests or
fuzzers and integrate them into the test suite.
Kris
…On Thu, Jul 25, 2019 at 12:31 PM Stephen Chang ***@***.***> wrote:
I see the problem. The maximum-bipartite-matching function uses a max
flow algorithm for *directed graphs*. So giving it an undirected graph
counts the edges twice.
Looking into possible fixes.
—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
<#48?email_source=notifications&email_token=AAEC6QQZI5VWF74URG6N3N3QBHIPBA5CNFSM4IFNVP3KYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD22ALQQ#issuecomment-515114434>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/AAEC6QRW2TMGMY5OFTD3HILQBHIPBANCNFSM4IFNVP3A>
.
|
Actually, you are right. Looking at the code more closely, it looks like the duplicate edges are removed before calling the max flow algorithm, so it should work out. Back to testing. |
Good luck!! Please do let me know if I can be of more help. Don't met
me commandeer too much of your time!
…On Thu, Jul 25, 2019 at 12:38 PM Stephen Chang ***@***.***> wrote:
Actually, you are right. Looking at the code more closely, it looks like the duplicate edges are removed before calling the max flow algorithm, so it should work out. Back to testing.
—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub, or mute the thread.
|
Wow! Thanks for handling this so quickly! |
I think I fixed it. Problem was that Let me know if anything still seems off. |
Thanks again for the report! |
That sounds like exactly the kind of thing that could have caused the
problem. Sounds awesome for now. Stupid question on my end: since I
installed this as a Racket package, is there a good way to get the fixed
version in a way that is harmonious? Can I just update via planet?
…On Thu, Jul 25, 2019 at 4:25 PM Stephen Chang ***@***.***> wrote:
Thanks again for the report!
—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
<#48?email_source=notifications&email_token=AAEC6QT4GSHDNUGP6YPBSB3QBID3HA5CNFSM4IFNVP3KYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD22VOJI#issuecomment-515200805>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/AAEC6QTXZJG3NDFDJF43QRLQBID3HANCNFSM4IFNVP3A>
.
|
Normally, yes. But the commits before this fix were somewhat drastic. Specifically, they modernized the package by splitting docs/tests/core into different packages, to accommodate min-racket installs and minimize dependencies (see #37). And I've had mixed experiences with updating this kind of change. But worst case, an uninstall-reinstall should do the trick. |
Perfect! That worked!
Kris
…On Thu, Jul 25, 2019 at 4:44 PM Stephen Chang ***@***.***> wrote:
since I installed this as a Racket package, is there a good way to get the
fixed version in a way that is harmonious?
Normally, yes. But the commits before this fix were somewhat drastic.
Specifically, they modernized the package by splitting docs/tests/core into
different packages, to accommodate min-racket installs and minimize
dependencies (see #37 <#37>). And
I've had mixed experiences with updating this kind of change. But worst
case, an uninstall-reinstall should do the trick.
—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
<#48?email_source=notifications&email_token=AAEC6QWMSBJSIY2SL7ZN6V3QBIGC3A5CNFSM4IFNVP3KYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD22XCDY#issuecomment-515207439>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/AAEC6QWO2DYU6V5VQJKPFJTQBIGC3ANCNFSM4IFNVP3A>
.
|
Test case:
Results in:
I believe this is wrong, since I see
(vtx 0 (set 1))
included in two edges here. Given that this is a maximal bipartite graph matching, this should not occur, as long as vertices are compared usingequal?
. I did a quick test to ensure that(equal? (vtx 0 (set 1)) (vtx 0 set 1))
is true. Next, I dug into the source of the implementation, and it does seem that the implementation respectsequal?
. So I don't see an obvious reason why this should happen.Thoughts?
The text was updated successfully, but these errors were encountered: