Max bipartite matching - Githubissues

EbTech / rust-algorithms

Common data structures and algorithms in Rust

MIT License

3.77k stars 220 forks source link

Max bipartite matching #7

Closed eric7237cire closed 5 years ago

eric7237cire commented 5 years ago

Another PR adding a test that shows how to use the max flow to find a maximum matching.

I had to refactor the dinic method a bit to return the flow.

eric7237cire commented 5 years ago

This PR actually has the requested changes for PR #5 so merging this one will include both. I hadn't branched the other one. Sorry about that.

eric7237cire commented 5 years ago

Cool, that should work!

Yeah I was pretty surprised the iterative DFS on the wikipedia page wasn't the most space efficient. Maybe because its a touch trickier to implement. Who knows.

EbTech commented 5 years ago

Awesome, I merged it in. Thanks for your contribution!