Skip to content

feat: add Min S-T Cut algorithm#847

Open
BryanCruz wants to merge 40 commits intopetgraph:masterfrom
BryanCruz:min-st-cut
Open

feat: add Min S-T Cut algorithm#847
BryanCruz wants to merge 40 commits intopetgraph:masterfrom
BryanCruz:min-st-cut

Conversation

@BryanCruz
Copy link
Contributor

@BryanCruz BryanCruz commented Jul 6, 2025

Depends on #739

Add Min S-T Cut Algorithm

Computes the minimum cut of a weighted directed graph that separates the vertices source and sink in 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).

  • Benches
> cargo bench --bench min_st_cut

running 5 tests
test min_st_cut_bench                              ... bench:     126,695.00 ns/iter (+/- 16,126.50)
test min_st_cut_bench_dense_middle                 ... bench:     754,312.47 ns/iter (+/- 132,334.77)
test min_st_cut_bench_dense_middle_varying_weights ... bench:   1,520,054.95 ns/iter (+/- 377,759.75)
test min_st_cut_bench_many_edges                   ... bench:     337,943.75 ns/iter (+/- 50,464.69)
test min_st_cut_bench_wide                         ... bench:     178,268.24 ns/iter (+/- 12,382.55)

test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured; 0 filtered out; finished in 15.92s

BryanCruz added 30 commits June 24, 2025 17:23
@BryanCruz
gdd Dinic's Maximum Flow Algorithm (#16)
53ed9a9
@BryanCruz
fix
b0cd4be
@BryanCruz
clippy
704cbe0
@BryanCruz
clippy tests
d15d4b3
@BryanCruz
fix no std
2e0a9b2
@BryanCruz
re-run ci
7213cbe
@BryanCruz
Revert "re-run ci"
749df39 
This reverts commit d3170dc.
@BryanCruz
fix mod
46accaa
@BryanCruz
add larger bench
06f4afe
@BryanCruz
refact dfs
b1071f3
@BryanCruz
checkpoint 1 - use neighbours pointers
25c31f0
@BryanCruz
refact build level
03dd3df
@BryanCruz
checkpoint 2: allowed edges
a5ec4de
@BryanCruz
simplify level graph
8d2a514
@BryanCruz
tmp
b282800
@BryanCruz
small optimization
16b3352
@BryanCruz
optimize visit
d280a71
@BryanCruz
feat: add more benches
6a976bb
@BryanCruz
refacts
87ceccb
@BryanCruz
min st cut
0eafcdd
@BryanCruz
test min_st_cut
2cd1b22
@BryanCruz
bench st cut
122cbd3
@BryanCruz
fix: re-use edges correctly in DFS searches
a9e77b3
@BryanCruz
nit
1bb6487
@BryanCruz
adjust min_st_cut benches
cbf565a
@BryanCruz
refacts
50db9d4
@BryanCruz
fix
7211b31
@BryanCruz
Merge remote-tracking branch 'original/master' into petgraph-maximum-…
ca6986e 
…flow
@BryanCruz
fix lint
1d53216
@BryanCruz
add docs in Petgraph's required format
eec07e0 
also rename `sink` to `destination` to make it compatible with
ford_fulkerson
@BryanCruz BryanCruz mentioned this pull request Jul 6, 2025
Merged
@starovoid starovoid added C-new-algorithm Category: A feature request for a new graph algorithm S-waiting-on-review Status: Awaiting review from the assignee but also other interested parties labels Jul 7, 2025
github-merge-queue bot pushed a commit that referenced this pull request Jul 27, 2025
@BryanCruz @RaoulLuque @cactusdualcore
feat: Add Dinic's Maximum Flow Algorithm (#739)
eaac05e 
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é <[email protected]>
Co-authored-by: Paul Buehne <[email protected]>
Co-authored-by: cactusdualcore <[email protected]>
RaoulLuque added a commit to RaoulLuque/petgraph that referenced this pull request Sep 21, 2025
@BryanCruz @RaoulLuque @cactusdualcore
feat: Add Dinic's Maximum Flow Algorithm (petgraph#739)
cf96114 
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é <[email protected]>
Co-authored-by: Paul Buehne <[email protected]>
Co-authored-by: cactusdualcore <[email protected]>
RaoulLuque added a commit to RaoulLuque/petgraph that referenced this pull request Sep 21, 2025
@BryanCruz @RaoulLuque @cactusdualcore
feat: Add Dinic's Maximum Flow Algorithm (petgraph#739)
5455093 
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é <[email protected]>
Co-authored-by: Paul Buehne <[email protected]>
Co-authored-by: cactusdualcore <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

C-new-algorithm Category: A feature request for a new graph algorithm S-waiting-on-review Status: Awaiting review from the assignee but also other interested parties

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@BryanCruz @starovoid