Struct rs_graph::maxflow::dinic::Dinic

pub struct Dinic<'a, G, F>where
    G: IndexDigraph,{ /* private fields */ }

The dinic max-flow algorithm.

Implementations

impl<'a, G, F> Dinic<'a, G, F>where G: IndexDigraph, F: NumAssign + Ord + Copy,

pub fn new(g: &'a G) -> Self

Create a new Dinic algorithm instance for a graph.

pub fn as_graph(&self) -> &'a G

Return the underlying graph.

pub fn value(&self) -> F

Return the value of the latest computed maximum flow.

pub fn flow(&self, e: G::Edge<'_>) -> F

Return the flow value on edge e

pub fn flow_iter<'b>(&'b self) -> impl Iterator<Item = (G::Edge<'a>, F)> + 'b

Return an iterator over all (edge, flow) pairs.

pub fn solve<Us>(&mut self, src: G::Node<'_>, snk: G::Node<'_>, upper: Us)where Us: Fn(G::Edge<'a>) -> F,

Solve the maxflow problem.

The method solved the max flow problem from the source node src to the sink node snk with the given upper bounds on the edges.

pub fn mincut(&self) -> Vec<G::Node<'a>>

Return the minimal cut associated with the last maximum flow.