feat: add Min S-T Cut algorithm #847
Open
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This reverts commit d3170dc.
also rename `sink` to `destination` to make it compatible with ford_fulkerson
github-merge-queue bot
pushed a commit
that referenced
this pull request
Jul 27, 2025
See also #740 and #847 # Add Dinic's Maximum Flow Algorithm Computes the maximum flow of a weighted directed graph. Implementation inspired by existing [Ford Fulkerson](https://github.com/petgraph/petgraph/blob/9f778ec11b218ef6d1dfaaa51467b24c8c939fca/src/algo/maximum_flow/ford_fulkerson.rs) in Petgraph. Also, creates a `maximum_flow` submodule inside `algo` module to group flow network algorithms. References: * https://en.wikipedia.org/wiki/Dinic%27s_algorithm * https://cp-algorithms.com/graph/dinic.html I also added some more benches that build graphs where Dinics strongly outperforms Ford Fulkerson, as the graph built in the existent bench in the library favored Ford Fulkerson method. * Dinics ``` > cargo bench --bench dinics running 5 tests test dinics_bench ... bench: 52,870.19 ns/iter (+/- 5,405.82) test dinics_bench_dense_middle ... bench: 680,920.00 ns/iter (+/- 120,617.64) test dinics_bench_dense_middle_varying_weights ... bench: 1,527,980.00 ns/iter (+/- 281,240.50) test dinics_bench_many_edges ... bench: 335,548.12 ns/iter (+/- 59,469.62) test dinics_bench_wide ... bench: 163,606.25 ns/iter (+/- 4,729.17) test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured; 0 filtered out; finished in 18.47s ``` * Ford Fulkerson ``` > cargo bench --bench ford_fulkerson running 5 tests test ford_fulkerson_bench ... bench: 15,360.68 ns/iter (+/- 3,189.80) test ford_fulkerson_bench_dense_middle ... bench: 1,129,970.00 ns/iter (+/- 194,473.25) test ford_fulkerson_bench_dense_middle_varying_weights ... bench: 14,432,700.00 ns/iter (+/- 1,127,474.00) test ford_fulkerson_bench_many_edges ... bench: 153,336.25 ns/iter (+/- 20,860.00) test ford_fulkerson_bench_wide ... bench: 3,733,340.00 ns/iter (+/- 957,471.00) test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured; 0 filtered out; finished in 15.93s``` ``` --------- Co-authored-by: Raoul Luqué <125205120+RaoulLuque@users.noreply.github.com> Co-authored-by: Paul Buehne <64769435+cactusdualcore@users.noreply.github.com> Co-authored-by: cactusdualcore <cactusdualcore@noreply.codeberg.org>
RaoulLuque
added a commit
to RaoulLuque/petgraph
that referenced
this pull request
Sep 21, 2025
See also petgraph#740 and petgraph#847 # Add Dinic's Maximum Flow Algorithm Computes the maximum flow of a weighted directed graph. Implementation inspired by existing [Ford Fulkerson](https://github.com/petgraph/petgraph/blob/9f778ec11b218ef6d1dfaaa51467b24c8c939fca/src/algo/maximum_flow/ford_fulkerson.rs) in Petgraph. Also, creates a `maximum_flow` submodule inside `algo` module to group flow network algorithms. References: * https://en.wikipedia.org/wiki/Dinic%27s_algorithm * https://cp-algorithms.com/graph/dinic.html I also added some more benches that build graphs where Dinics strongly outperforms Ford Fulkerson, as the graph built in the existent bench in the library favored Ford Fulkerson method. * Dinics ``` > cargo bench --bench dinics running 5 tests test dinics_bench ... bench: 52,870.19 ns/iter (+/- 5,405.82) test dinics_bench_dense_middle ... bench: 680,920.00 ns/iter (+/- 120,617.64) test dinics_bench_dense_middle_varying_weights ... bench: 1,527,980.00 ns/iter (+/- 281,240.50) test dinics_bench_many_edges ... bench: 335,548.12 ns/iter (+/- 59,469.62) test dinics_bench_wide ... bench: 163,606.25 ns/iter (+/- 4,729.17) test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured; 0 filtered out; finished in 18.47s ``` * Ford Fulkerson ``` > cargo bench --bench ford_fulkerson running 5 tests test ford_fulkerson_bench ... bench: 15,360.68 ns/iter (+/- 3,189.80) test ford_fulkerson_bench_dense_middle ... bench: 1,129,970.00 ns/iter (+/- 194,473.25) test ford_fulkerson_bench_dense_middle_varying_weights ... bench: 14,432,700.00 ns/iter (+/- 1,127,474.00) test ford_fulkerson_bench_many_edges ... bench: 153,336.25 ns/iter (+/- 20,860.00) test ford_fulkerson_bench_wide ... bench: 3,733,340.00 ns/iter (+/- 957,471.00) test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured; 0 filtered out; finished in 15.93s``` ``` --------- Co-authored-by: Raoul Luqué <125205120+RaoulLuque@users.noreply.github.com> Co-authored-by: Paul Buehne <64769435+cactusdualcore@users.noreply.github.com> Co-authored-by: cactusdualcore <cactusdualcore@noreply.codeberg.org>
RaoulLuque
added a commit
to RaoulLuque/petgraph
that referenced
this pull request
Sep 21, 2025
See also petgraph#740 and petgraph#847 # Add Dinic's Maximum Flow Algorithm Computes the maximum flow of a weighted directed graph. Implementation inspired by existing [Ford Fulkerson](https://github.com/petgraph/petgraph/blob/9f778ec11b218ef6d1dfaaa51467b24c8c939fca/src/algo/maximum_flow/ford_fulkerson.rs) in Petgraph. Also, creates a `maximum_flow` submodule inside `algo` module to group flow network algorithms. References: * https://en.wikipedia.org/wiki/Dinic%27s_algorithm * https://cp-algorithms.com/graph/dinic.html I also added some more benches that build graphs where Dinics strongly outperforms Ford Fulkerson, as the graph built in the existent bench in the library favored Ford Fulkerson method. * Dinics ``` > cargo bench --bench dinics running 5 tests test dinics_bench ... bench: 52,870.19 ns/iter (+/- 5,405.82) test dinics_bench_dense_middle ... bench: 680,920.00 ns/iter (+/- 120,617.64) test dinics_bench_dense_middle_varying_weights ... bench: 1,527,980.00 ns/iter (+/- 281,240.50) test dinics_bench_many_edges ... bench: 335,548.12 ns/iter (+/- 59,469.62) test dinics_bench_wide ... bench: 163,606.25 ns/iter (+/- 4,729.17) test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured; 0 filtered out; finished in 18.47s ``` * Ford Fulkerson ``` > cargo bench --bench ford_fulkerson running 5 tests test ford_fulkerson_bench ... bench: 15,360.68 ns/iter (+/- 3,189.80) test ford_fulkerson_bench_dense_middle ... bench: 1,129,970.00 ns/iter (+/- 194,473.25) test ford_fulkerson_bench_dense_middle_varying_weights ... bench: 14,432,700.00 ns/iter (+/- 1,127,474.00) test ford_fulkerson_bench_many_edges ... bench: 153,336.25 ns/iter (+/- 20,860.00) test ford_fulkerson_bench_wide ... bench: 3,733,340.00 ns/iter (+/- 957,471.00) test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured; 0 filtered out; finished in 15.93s``` ``` --------- Co-authored-by: Raoul Luqué <125205120+RaoulLuque@users.noreply.github.com> Co-authored-by: Paul Buehne <64769435+cactusdualcore@users.noreply.github.com> Co-authored-by: cactusdualcore <cactusdualcore@noreply.codeberg.org>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Depends on #739
Add Min S-T Cut Algorithm
Computes the minimum cut of a weighted directed graph that separates the vertices
sourceandsinkin different partitions, using the max-flow min-cut theorem.Underneath, uses Dinic's algorithm to solve the maximum flow problem in the network and then builds the minimum cut from the last level graph built in Dinic's.
Returns the edges present in minimum cut and the computed min cut capacity (which is equivalent to the maximum flow in the network).