feat: Add Dinic's Maximum Flow Algorithm #739

BryanCruz · 2025-02-17T04:09:07Z

Add Dinic's Maximum Flow Algorithm

Computes the maximum flow of a weighted directed graph.

Implementation inspired by existing Ford Fulkerson in Petgraph.

Also, creates a maximum_flow submodule inside algo module to group flow network algorithms.

References:

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```

RaoulLuque · 2025-05-17T21:05:23Z

As mentioned in PR 740, by @starovoid, the algorithm does not seem to be improving upon the existing implementation when running the benchmarks. Indeed it seems to be performing worse.

This may be because the graphs from the benchmark have the same number of nodes as edges. However, in such a setting, Ford Fulkerson and Dinics should actually perform similarly. The results on my PC are however as follows:

dinics_bench            ... bench:      28,915.92 ns/iter (+/- 2,343.77)
ford_fulkerson_bench            ... bench:      17,511.19 ns/iter (+/- 1,822.12)

Which shows the decrease in performance. I also added a similar benchmark for both algorithms for an increased number of edges, where on can observe that this implementation of Dinic performs similarly poor. The bench setup is as follows:

#[bench]
fn dinics_bench_many_edges(bench: &mut Bencher) {
    static NODE_COUNT: usize = 1_001;
    let mut g: Graph<usize, usize> = Graph::new();
    let nodes: Vec<NodeIndex<_>> = (0..NODE_COUNT).map(|i| g.add_node(i)).collect();
    for j in [1, 2, 4, 5, 10, 20, 25, 50] {
        for i in 0..(NODE_COUNT - 1) / j  {
            g.add_edge(nodes[i], nodes[(i + 1) * j], 1);
        }
    }
    bench.iter(|| {
        let _flow = dinics(
            &g,
            NodeIndex::from(0),
            NodeIndex::from(g.node_count() as u32 - 1),
        );
    });
}

And the results are:

dinics_bench_many_edges ... bench:     355,747.67 ns/iter (+/- 14,674.08)
ford_fulkerson_bench_many_edges ... bench:     205,071.71 ns/iter (+/- 3,839.07)

This reverts commit d3170dc.

BryanCruz · 2025-06-26T18:06:00Z

Hi @RaoulLuque , thanks for pointing out the benchmark and for providing a larger bench test.

I reimplemented some parts of the algorithm and got it to work a lot better.

The Dinics and Ford Fulkerson benches that were being compared contained graph instances that favored a Ford Fulkerson method, so I added some others that favors Dinics. I added the benchmark results in the PR description.

I'll also check the Maximum Bipartite Matching PR soon.

RaoulLuque · 2025-06-26T20:23:33Z

Hi, thanks for reviewing the code and improving it :) Those results look really promising !

Ah, I didn't know that they were more favorable for Ford Fulkerson, I'll look into that interesting. Thanks for pointing that out 😁

I'll have a look at the new code prob next week if that's okay, because I currently don't have a lot of time unfortunately :)

(If someone else wants to have a look, that is also great of course 😁)

RaoulLuque · 2025-06-26T20:26:36Z

(one thing I can already say tho is that a docstring in the algo docs format should be added :) )

RaoulLuque · 2025-07-07T09:04:15Z

Sry for the additional comment, but since you seem to be quite knowledgable when it comes to the different use-cases of Dinics/Ford Fulkerson (Edmonds Karp), I think it would be a good idea to document when to use which function. We could use the maximum_flow/mod.rs for this and add a comment there. In the ford_fulkerson and dinics docstrings we could then refer to the mod.rs docs for when to use this or other maximum flow functions :)

(You can use cargo doc --open to compile and open the docs in your browser to see how they would look like and if links etc. work ^^)

BryanCruz · 2025-07-19T22:00:32Z

I think it would be a good idea to document when to use which function. We could use the maximum_flow/mod.rs for this and add a comment there. In the ford_fulkerson and dinics docstrings we could then refer to the mod.rs docs for when to use this or other maximum flow functions :)

good idea, added in latest commit

RaoulLuque · 2025-07-26T15:09:59Z

Okay, so if you adjust the docstring of dinics to document the possibility to panic as stated in #739 (comment), I think this Pr would be ready to merge, thanks a lot again 🌟

Just one more comment I have, just below. Note that you can also accept suggestions right here on GitHub, this way the reviewers will be credited in Git for their suggestions :)

src/algo/maximum_flow/ford_fulkerson.rs

Co-authored-by: Raoul Luqué <125205120+RaoulLuque@users.noreply.github.com>

…etgraph#849) The function 'zip' was introduced in petgraph#747 as a part of adding `no_std` support. However, there is already such a function in `core::iter`. The MSRV stated in the description of petgraph#747 was 1.64 at minimum, but the function in `core` is stable since Rust 1.59. Thus, it is an unnecessary duplication and can be removed without consequences.  Co-authored-by: cactusdualcore <cactusdualcore@noreply.codeberg.org>

src/algo/maximum_flow/dinics.rs

RaoulLuque · 2025-07-27T13:09:22Z

Looks great, thanks for all your patience with my review ☺️ Just these two small language nitpicks, after which I will merge the PR 👍

Co-authored-by: Raoul Luqué <125205120+RaoulLuque@users.noreply.github.com>

BryanCruz · 2025-07-27T14:33:30Z

Looks great, thanks for all your patience with my review ☺️ Just these two small language nitpicks, after which I will merge the PR 👍

thanks ☺️ , commited the latest suggestions

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>

## 🤖 New release * `petgraph`: 0.8.2 -> 0.8.3 (✓ API compatible changes) <details><summary>Changelog</summary> <blockquote> ## [0.8.3](https://github.com/petgraph/petgraph/compare/petgraph@v0.8.2...petgraph@v0.8.3) - 2025-09-28 ### Bug Fixes - Infinite `subgraph_isomorphisms_iter` for empty isomorphisms ([#780](#780)) - Algos don't work on `UndirectedAdaptor` ([#870](#870)) ([#871](#871)) - use a queue for SPFA ([#893](#893)) - `StableGraph::reverse` breaks free lists ([#890](#890)) ### Documentation - Fix examples link in README and unify typesetting of one word ([#823](#823)) - Add link to multigraph definition to isomorphism algos ([#824](#824)) - Fix auxiliary space (and time) complexity of bron-kerbosch ([#825](#825)) - Fix Typo in Operator Module Documentation ([#831](#831)) - Sync the crate feature flags in the README and docs ([#832](#832)) - Remove all \[Generic\] tags from algo docstrings ([#835](#835)) - Fix typos in comments ([#836](#836)) - Revamp CONTRIBUTING.md ([#833](#833)) - Update `GraphMap` link in README ([#857](#857)) - Add doc comment for `Dot::with_attr_getters` ([#850](#850)) - Specify iteration order for neighbors and edges and their variants ([#790](#790)) - Collection of Doc fixes ([#856](#856)) ### New Features - Add `into_nodes_edges_iters` to `StableGraph` ([#841](#841)) - Add methods to reserve & shrink `StableGraph` capacity ([#846](#846)) - Add Dinic's Maximum Flow Algorithm ([#739](#739)) - make Csr::from_sorted_edges generic over edge type and properly increase edge_count in Csr::from_sorted_edges ([#861](#861)) - Add `map_owned` and `filter_map_owned` for `Graph` and `StableGraph` ([#863](#863)) - Add dijkstra::with_dynamic_goal ([#855](#855)) - Fix self-loop bug in all_simple_paths and enable multiple targets ([#865](#865)) - mark petgraph::dot::Dot::graph_fmt as public ([#866](#866)) - Add bidirectional Dijkstra algorithm ([#782](#782)) ### Performance - Make A* tie break on lower h-values ([#882](#882)) ### Refactor - add examples for scc algorithms and reorganize into dedicated module ([#830](#830)) - Remove unnecessary trait bounds from impls/methods ([#828](#828)) - replace uses of 'crate::util::zip' with 'core::iter::zip' ([#849](#849)) - Fix clippy (and other) lints ([#851](#851)) - Cleanup repo ([#854](#854)) - replace crate::util::enumerate with Iterator::enumerate ([#881](#881)) ### Testing - Add dependency list for 'quickcheck' feature ([#822](#822)) - Fix feature cfg capitalization in doctest ([#852](#852)) </blockquote> </details> --- This PR was generated with [release-plz](https://github.com/release-plz/release-plz/). --------- Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com> Co-authored-by: Egor Starovoitov <52821033+starovoid@users.noreply.github.com>

BryanCruz marked this pull request as ready for review February 17, 2025 06:20

BryanCruz mentioned this pull request Feb 17, 2025

feat: Add Maximum Bipartite Matching Algorithm #740

Open

BryanCruz changed the title ~~Add Dinic's Maximum Flow Algorithm~~ feat: Add Dinic's Maximum Flow Algorithm Apr 13, 2025

BryanCruz added 19 commits June 24, 2025 17:23

gdd Dinic's Maximum Flow Algorithm (#16)

53ed9a9

fix

b0cd4be

clippy

704cbe0

clippy tests

d15d4b3

fix no std

2e0a9b2

re-run ci

7213cbe

Revert "re-run ci"

749df39

This reverts commit d3170dc.

fix mod

46accaa

add larger bench

06f4afe

refact dfs

b1071f3

checkpoint 1 - use neighbours pointers

25c31f0

refact build level

03dd3df

checkpoint 2: allowed edges

a5ec4de

simplify level graph

8d2a514

tmp

b282800

small optimization

16b3352

optimize visit

d280a71

feat: add more benches

6a976bb

refacts

87ceccb

BryanCruz force-pushed the petgraph-maximum-flow branch from 6643b23 to 87ceccb Compare June 26, 2025 17:55

BryanCruz added 3 commits June 30, 2025 23:10

min st cut

0eafcdd

test min_st_cut

2cd1b22

bench st cut

122cbd3

remove min_st_cut

85b012d

BryanCruz changed the title ~~feat: Add Dinic's Maximum Flow Algorithm and Min S-T Cut algorithm~~ feat: Add Dinic's Maximum Flow Algorithm Jul 6, 2025

BryanCruz mentioned this pull request Jul 6, 2025

feat: add Min S-T Cut algorithm #847

Open

Merge branch 'master-original' into petgraph-maximum-flow

0169019

BryanCruz added 2 commits July 19, 2025 18:23

gerge branch 'master-original' into petgraph-maximum-flow

18e1926

docs for max flow mod

0bcd203

RaoulLuque reviewed Jul 26, 2025

View reviewed changes

src/algo/maximum_flow/ford_fulkerson.rs Show resolved Hide resolved

BryanCruz and others added 4 commits July 26, 2025 17:37

Update src/algo/maximum_flow/ford_fulkerson.rs

67384b1

Co-authored-by: Raoul Luqué <125205120+RaoulLuque@users.noreply.github.com>

docs about PartialOrd

e6f53dc

Merge branch 'master-original' into petgraph-maximum-flow

8e85856

RaoulLuque reviewed Jul 27, 2025

View reviewed changes

src/algo/maximum_flow/dinics.rs Outdated Show resolved Hide resolved

RaoulLuque reviewed Jul 27, 2025

View reviewed changes

src/algo/maximum_flow/dinics.rs Outdated Show resolved Hide resolved

BryanCruz and others added 2 commits July 27, 2025 11:30

Update src/algo/maximum_flow/dinics.rs

b0a680d

Co-authored-by: Raoul Luqué <125205120+RaoulLuque@users.noreply.github.com>

Update src/algo/maximum_flow/dinics.rs

a8b97df

Co-authored-by: Raoul Luqué <125205120+RaoulLuque@users.noreply.github.com>

RaoulLuque added this pull request to the merge queue Jul 27, 2025

Merged via the queue into petgraph:master with commit eaac05e Jul 27, 2025
11 checks passed

github-actions bot mentioned this pull request Jul 27, 2025

chore: release v0.8.3 #826

Merged

RaoulLuque added this to the 0.8.3 milestone Jul 27, 2025

RaoulLuque added C-new-algorithm Category: A feature request for a new graph algorithm A-crate Area: Petgraph crate functionality labels Jul 27, 2025

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

feat: Add Dinic's Maximum Flow Algorithm #739

feat: Add Dinic's Maximum Flow Algorithm #739

Uh oh!

BryanCruz commented Feb 17, 2025 •

edited

Loading

Uh oh!

RaoulLuque commented May 17, 2025 •

edited

Loading

Uh oh!

BryanCruz commented Jun 26, 2025

Uh oh!

RaoulLuque commented Jun 26, 2025

Uh oh!

RaoulLuque commented Jun 26, 2025

Uh oh!

RaoulLuque commented Jul 7, 2025 •

edited

Loading

Uh oh!

BryanCruz commented Jul 19, 2025

Uh oh!

RaoulLuque commented Jul 26, 2025

Uh oh!

Uh oh!

Uh oh!

Uh oh!

RaoulLuque commented Jul 27, 2025

Uh oh!

BryanCruz commented Jul 27, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

feat: Add Dinic's Maximum Flow Algorithm #739

feat: Add Dinic's Maximum Flow Algorithm #739

Uh oh!

Conversation

BryanCruz commented Feb 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Add Dinic's Maximum Flow Algorithm

Uh oh!

RaoulLuque commented May 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

BryanCruz commented Jun 26, 2025

Uh oh!

RaoulLuque commented Jun 26, 2025

Uh oh!

RaoulLuque commented Jun 26, 2025

Uh oh!

RaoulLuque commented Jul 7, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

BryanCruz commented Jul 19, 2025

Uh oh!

RaoulLuque commented Jul 26, 2025

Uh oh!

Uh oh!

Uh oh!

Uh oh!

RaoulLuque commented Jul 27, 2025

Uh oh!

BryanCruz commented Jul 27, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

BryanCruz commented Feb 17, 2025 •

edited

Loading

RaoulLuque commented May 17, 2025 •

edited

Loading

RaoulLuque commented Jul 7, 2025 •

edited

Loading