Struct PushRelabelMaxFlow 

pub struct PushRelabelMaxFlow { /* private fields */ }

Push-Relabel maximum flow algorithm with FIFO selection and highest-label strategy.

Time complexity: O(V² √E).

Example

use scirs2_graph::flow::max_flow::PushRelabelMaxFlow;

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

Implementations

impl PushRelabelMaxFlow

pub fn new(n: usize) -> Self

Create a new Push-Relabel solver with n nodes.

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

Add a directed edge from u to v with capacity cap.

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

Compute the maximum flow from source to sink.

Trait Implementations

impl Clone for PushRelabelMaxFlow

fn clone(&self) -> PushRelabelMaxFlow

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for PushRelabelMaxFlow

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

Formats the value using the given formatter.