Struct rs_graph::maxflow::pushrelabel::PushRelabel

pub struct PushRelabel<'a, G, F>where
    G: 'a + IndexDigraph,{
    pub cnt_relabel: usize,
    pub use_global_relabelling: bool,
    /* private fields */
}

The push-relabel algorithm.

This struct contains all algorithmic working data.

Fields

cnt_relabel: usize

The number of relabel operations performed during the algorithm.

use_global_relabelling: bool

Whether to use the global relabelling heuristic.

Implementations

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

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

Return a new push-relabel algorithm data structure for the digraph g.

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

Return a reference to the underlying graph.

pub fn value(&self) -> F

Return the flow value.

The function returns 0 if the flow has not been computed, yet.

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

Return the flow value over some edge.

The function returns 0 if the flow has not been computed, yet.

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,

Run the push-relabel algorithm from some source to some sink node.

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.