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 GraphType<'a>>::Edge) -> Self::Flow;
    fn solve<Us>(
        &mut self, 
        src: <Self::Graph as GraphType<'a>>::Node, 
        snk: <Self::Graph as GraphType<'a>>::Node, 
        upper: Us
    )
    where
        Us: Fn(<Self::Graph as GraphType<'a>>::Edge) -> Self::Flow;
    fn mincut(&self) -> Vec<<Self::Graph as GraphType<'a>>::Node>;

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

Trait for max flow algorithms.

Associated Types

type Graph: IndexGraph<'a>

Type of the underlying graph.

type Flow: Num + Ord

Type of flows.

Loading content...

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 GraphType<'a>>::Edge) -> Self::Flow

The flow of an Edge.

fn solve<Us>(
    &mut self,
    src: <Self::Graph as GraphType<'a>>::Node,
    snk: <Self::Graph as GraphType<'a>>::Node,
    upper: Us
) where
    Us: Fn(<Self::Graph as GraphType<'a>>::Edge) -> 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 GraphType<'a>>::Node>

Return the mincut associated with the current flow.

Loading content...

Provided methods

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

The flow as vector.

Loading content...

Implementors

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

type Graph = G

type Flow = F

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

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

fn value(&self) -> F

fn flow(&self, e: G::Edge) -> F

fn solve<Us>(&mut self, src: G::Node, snk: G::Node, upper: Us) where
    Us: Fn(G::Edge) -> Self::Flow, 

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

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

type Graph = G

type Flow = F

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

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

fn value(&self) -> F

fn flow(&self, e: G::Edge) -> F

fn solve<Us>(&mut self, src: G::Node, snk: G::Node, upper: Us) where
    Us: Fn(G::Edge) -> Self::Flow, 

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

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

type Graph = G

type Flow = F

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

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

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

Return a reference to the underlying graph.

fn value(&self) -> F

Return the flow value.

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

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.

fn solve<Us>(&mut self, src: G::Node, snk: G::Node, upper: Us) where
    Us: Fn(G::Edge) -> Self::Flow, 

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

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

Return the minimal cut.

Loading content...