Bug in maximum bipartite matching?

[kmicinski]

Test case:

#lang racket
(require graph)

;; Each vertex is a pair via a struct
(struct vtx (tag contents) #:transparent)

;; List of edges in an undirected graph
(define edges
  (list
   (list (vtx 0 (set 3)) (vtx 1 (set 3 2)))
   (list (vtx 0 (set 0)) (vtx 1 (set 3 0)))
   (list (vtx 0 (set 1)) (vtx 1 (set 1 2)))
   (list (vtx 0 (set 1)) (vtx 1 (set 1 3)))
   (list (vtx 0 (set 3 2)) (vtx 1 (set 3 0 2)))
   (list (vtx 0 (set 0)) (vtx 1 (set 0 2)))
   (list (vtx 0 (set 3)) (vtx 1 (set 1 3)))
   (list (vtx 0 (set 3)) (vtx 1 (set 3 0)))
   (list (vtx 0 (set 1)) (vtx 1 (set 1 3 0)))
   (list (vtx 0 (set 2)) (vtx 1 (set 3 0 2)))
   (list (vtx 0 (set 3 0)) (vtx 1 (set 3 0 2)))
   (list (vtx 0 (set 2)) (vtx 1 (set 0 2)))
   (list (vtx 0 (set 3)) (vtx 1 (set 1 3 0)))
   (list (vtx 0 (set 0)) (vtx 1 (set 3 0 2)))
   (list (vtx 0 (set 1 3)) (vtx 1 (set 1 3 0)))
   (list (vtx 0 (set 2)) (vtx 1 (set 3 2)))
   (list (vtx 0 (set 3)) (vtx 1 (set 3 0 2)))
   (list (vtx 0 (set 2)) (vtx 1 (set 1 2)))
   (list (vtx 0 (set 3 0)) (vtx 1 (set 1 3 0)))
   (list (vtx 0 (set 0)) (vtx 1 (set 1 3 0)))
   (list (vtx 0 (set 0 2)) (vtx 1 (set 3 0 2)))))

;; Perform maximum bipartite matching.
(pretty-print (maximum-bipartite-matching (undirected-graph edges)))

Results in:

(list
 (list (vtx 1 (set 1 3 0)) (vtx 0 (set 1 3)))
 (list (vtx 1 (set 1 3)) (vtx 0 (set 1)))
 (list (vtx 1 (set 0 2)) (vtx 0 (set 0)))
 (list (vtx 0 (set 1)) (vtx 1 (set 1 3 0)))
 (list (vtx 1 (set 3 2)) (vtx 0 (set 2)))
 (list (vtx 1 (set 3 0)) (vtx 0 (set 3)))
 (list (vtx 1 (set 1 2)) (vtx 0 (set 1)))
 (list (vtx 1 (set 3 0 2)) (vtx 0 (set 3 2)))
 (list (vtx 1 (set 1 3 0)) (vtx 0 (set 3 0))))

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 using equal?. 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 respects equal?. So I don't see an obvious reason why this should happen.

Thoughts?

[stchang]

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.

[kmicinski]

Thanks for the response! Yes, that's right: v7.2. Your suspicions here sound like good intuition to me, for sure.

[stchang]

I think 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.

[kmicinski]

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 notifications@github.com 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 https://github.com/stchang/graph/issues/48?email_source=notifications&email_token=AAEC6QQZI5VWF74URG6N3N3QBHIPBA5CNFSM4IFNVP3KYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD22ALQQ#issuecomment-515114434, or mute the thread https://github.com/notifications/unsubscribe-auth/AAEC6QRW2TMGMY5OFTD3HILQBHIPBANCNFSM4IFNVP3A .

[stchang]

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.

[kmicinski]

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 notifications@github.com 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.

[kmicinski]

Wow! Thanks for handling this so quickly!

[stchang]

I think I fixed it.

Problem was that edge-weight was returning inf for non-existent edges, but that is the wrong default for maxflow.

Let me know if anything still seems off.

[stchang]

Thanks again for the report!

[kmicinski]

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 notifications@github.com wrote:

Thanks again for the report!

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/stchang/graph/issues/48?email_source=notifications&email_token=AAEC6QT4GSHDNUGP6YPBSB3QBID3HA5CNFSM4IFNVP3KYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD22VOJI#issuecomment-515200805, or mute the thread https://github.com/notifications/unsubscribe-auth/AAEC6QTXZJG3NDFDJF43QRLQBID3HANCNFSM4IFNVP3A .

[stchang]

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 https://github.com/stchang/graph/pull/37). And I've had mixed experiences with updating this kind of change. But worst case, an uninstall-reinstall should do the trick.

[kmicinski]

Perfect! That worked!

Kris

On Thu, Jul 25, 2019 at 4:44 PM Stephen Chang notifications@github.com 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 https://github.com/stchang/graph/pull/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 https://github.com/stchang/graph/issues/48?email_source=notifications&email_token=AAEC6QWMSBJSIY2SL7ZN6V3QBIGC3A5CNFSM4IFNVP3KYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD22XCDY#issuecomment-515207439, or mute the thread https://github.com/notifications/unsubscribe-auth/AAEC6QWO2DYU6V5VQJKPFJTQBIGC3ANCNFSM4IFNVP3A .