Bug in maximum bipartite matching? about graph HOT 12 CLOSED

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.

from graph.

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

from graph.

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.

from graph.

from graph.

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.

from graph.

from graph.

Wow! Thanks for handling this so quickly!

from graph.

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.

from graph.

Thanks again for the report!

from graph.

from graph.

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). And I've had mixed experiences with updating this kind of change. But worst case, an uninstall-reinstall should do the trick.

from graph.

from graph.