Trait rs_graph::maxflow::MaxFlow

pub trait MaxFlow<'a> {
    type Graph: IndexGraph<'a>;
    type Flow: Num + Ord;

    fn new(g: &'a Self::Graph) -> Self;
    fn as_graph(&self) -> &'a Self::Graph;
    fn value(&self) -> Self::Flow;
    fn flow(&self, a: <Self::Graph as Graph<'a>>::Edge) -> Self::Flow;
    fn solve<Us>(
        &mut self,
        src: <Self::Graph as Graph<'a>>::Node,
        snk: <Self::Graph as Graph<'a>>::Node,
        upper: Us
    )
    where
        Us: EdgeMap<'a, Self::Graph, Self::Flow>;
    fn mincut(&self) -> Vec<<Self::Graph as Graph<'a>>::Node>;

    fn flow_vec(&self) -> IndexEdgeVec<'a, Self::Graph, Self::Flow> { ... }
}

Trait for max flow algorithms.

Required Associated Types

type Graph: IndexGraph<'a>

Type of the underlying graph.

type Flow: Num + Ord

Type of flows.

Required Methods

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

Create a new maxflow algorithm instance for a graph.

fn as_graph(&self) -> &'a Self::Graph

Return the underlying graph.

fn value(&self) -> Self::Flow

Return the value of the latest computed maximum flow.

fn flow(&self, a: <Self::Graph as Graph<'a>>::Edge) -> Self::Flow

The flow of an Edge.

fn solve<Us>(
    &mut self,
    src: <Self::Graph as Graph<'a>>::Node,
    snk: <Self::Graph as Graph<'a>>::Node,
    upper: Us
)where
    Us: EdgeMap<'a, Self::Graph, Self::Flow>,

Solve the maxflow problem.

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

fn mincut(&self) -> Vec<<Self::Graph as Graph<'a>>::Node>

Return the mincut associated with the current flow.

Provided Methods

fn flow_vec(&self) -> IndexEdgeVec<'a, Self::Graph, Self::Flow>

The flow as vector.

Implementors

impl<'a, G, F> MaxFlow<'a> for Dinic<'a, G, F>where
    G: IndexNetwork<'a>,
    F: NumAssign + Ord + Copy,

type Graph = G

type Flow = F

impl<'a, G, F> MaxFlow<'a> for EdmondsKarp<'a, G, F>where
    G: IndexNetwork<'a>,
    F: NumAssign + Ord + Copy,

type Graph = G

type Flow = F

impl<'a, G, F> MaxFlow<'a> for PushRelabel<'a, G, F>where
    G: IndexNetwork<'a>,
    F: NumAssign + Ord + Copy,

type Graph = G

type Flow = F