Struct DinicMaxFlow 

pub struct DinicMaxFlow { /* private fields */ }

Dinic’s maximum flow algorithm.

Builds a level graph with BFS and finds blocking flows with DFS. Time complexity: O(V² E) for general graphs, O(E √V) for unit-capacity.

Example

use scirs2_graph::flow::max_flow::DinicMaxFlow;

let mut d = DinicMaxFlow::new(4);
d.add_edge(0, 1, 10);
d.add_edge(0, 2, 10);
d.add_edge(1, 3, 10);
d.add_edge(2, 3, 10);
d.add_edge(1, 2, 1);
let flow = d.max_flow(0, 3);
assert_eq!(flow, 20);

Implementations

impl DinicMaxFlow

pub fn new(n: usize) -> Self

Create a new Dinic solver with n nodes (0-indexed).

pub fn add_edge(&mut self, u: usize, v: usize, cap: i64)

Add a directed edge from u to v with capacity cap. A reverse edge with capacity 0 is automatically added.

pub fn max_flow(&mut self, source: usize, sink: usize) -> i64

Compute max flow from source to sink. Returns 0 if source == sink or no path exists.

pub fn edges(&self) -> Vec<(usize, usize, i64, i64)>

Return the current flow on each edge (forward edges only). Each entry is (u, v, capacity, flow).

Trait Implementations

impl Clone for DinicMaxFlow

fn clone(&self) -> DinicMaxFlow

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for DinicMaxFlow

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.