The Wayback Machine - https://web.archive.org/web/20200918172029/https://github.com/EbTech/rust-algorithms/pull/7
Skip to content
Sign in Sign up

/ rust-algorithms

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

Max bipartite matching #7

Merged
merged 12 commits into from Jan 17, 2019
Merged

Max bipartite matching #7

merged 12 commits into from Jan 17, 2019

Conversation

@eric7237cire
Copy link
Contributor

eric7237cire commented Jan 11, 2019

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
Adding a Rust iterator example implementing a DFS iteratively
Loading status checks…
dab69d1
@eric7237cire
Add a bipartite maximum matching test
0a2ad5f 
Refactor dinic to return the actual flow
@eric7237cire eric7237cire changed the title Max matching Max bipartite matching Jan 11, 2019
@EbTech
EbTech requested changes Jan 14, 2019
View changes
src/graph/flow.rs Outdated Show resolved Hide resolved
@EbTech
EbTech reviewed Jan 14, 2019
View changes
src/graph/flow.rs Outdated Show resolved Hide resolved
@eric7237cire
Hopefully no longer O(v^2) is space, clippy, better let syntax
4279d9f
@eric7237cire
feedback
a835319
@eric7237cire
feedback, formatting
72ac030
@eric7237cire
Copy link
Contributor Author

eric7237cire commented Jan 15, 2019

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.
@EbTech
EbTech requested changes Jan 15, 2019
View changes
src/graph/dfs.rs Outdated Show resolved Hide resolved
src/graph/dfs.rs Outdated Show resolved Hide resolved
src/graph/dfs.rs Outdated Show resolved Hide resolved
@EbTech EbTech mentioned this pull request Jan 15, 2019
Closed
@eric7237cire
Maybe O(V) in space?
c676d7a
@eric7237cire
remove println
a07afa1
@eric7237cire
get rid of r
3b7bb6c
@eric7237cire
tweak comment
f33263d
@eric7237cire
tweak comment
75011ae
@eric7237cire
don't need a peekable iterator
ae776e3
@EbTech
EbTech requested changes Jan 17, 2019
View changes
Copy link
Owner

EbTech left a comment

Cool, that should work!
src/graph/dfs.rs Outdated Show resolved Hide resolved
src/graph/dfs.rs Outdated Show resolved Hide resolved
src/graph/dfs.rs Outdated Show resolved Hide resolved
@eric7237cire
Use better rust pattern matching, feedback
6822dc1
@eric7237cire
Copy link
Contributor Author

eric7237cire commented Jan 17, 2019

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
EbTech approved these changes Jan 17, 2019
View changes
@EbTech EbTech merged commit 88b0d6f into EbTech:master Jan 17, 2019
@EbTech
Copy link
Owner

EbTech commented Jan 17, 2019

Awesome, I merged it in. Thanks for your contribution!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@eg-novelt eg-novelt

@EbTech EbTech

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Linked issues

Successfully merging this pull request may close these issues.

None yet

3 participants
@eric7237cire @EbTech @eg-novelt
You can’t perform that action at this time.
Morty Proxy This is a proxified and sanitized view of the page, visit original site.