Trait pathfinding::directed::edmonds_karp::EdmondsKarp

pub trait EdmondsKarp<C: Copy + Zero + Signed + Ord + Bounded> {
    fn new(size: usize, source: usize, sink: usize) -> Self
    where
        Self: Sized;
    fn from_matrix(source: usize, sink: usize, capacities: Matrix<C>) -> Self
    where
        Self: Sized;
    fn common(&self) -> &Common<C>;
    fn common_mut(&mut self) -> &mut Common<C>;
    fn residual_successors(&self, from: usize) -> Vec<(usize, C)>;
    fn residual_capacity(&self, from: usize, to: usize) -> C;
    fn flow(&self, from: usize, to: usize) -> C;
    fn flows_from(&self, from: usize) -> Vec<usize>;
    fn flows(&self) -> Vec<((usize, usize), C)>;
    fn add_flow(&mut self, from: usize, to: usize, capacity: C);
    fn add_residual_capacity(&mut self, from: usize, to: usize, capacity: C);

    fn from_vec(source: usize, sink: usize, capacities: Vec<C>) -> Self
    where
        Self: Sized,
    { ... }
    fn size(&self) -> usize { ... }
    fn source(&self) -> usize { ... }
    fn sink(&self) -> usize { ... }
    fn set_capacity(&mut self, from: usize, to: usize, capacity: C) { ... }
    fn total_capacity(&self) -> C { ... }
    fn set_total_capacity(&mut self, capacity: C) { ... }
    fn omit_details(&mut self) { ... }
    fn has_details(&self) -> bool { ... }
    fn augment(&mut self) -> EKFlows<usize, C> { ... }
}

Representation of capacity and flow data.

Required Methods

fn new(size: usize, source: usize, sink: usize) -> Selfwhere
    Self: Sized,

Create a new empty structure.

Panics

This function panics when source or sink is greater or equal than size.

fn from_matrix(source: usize, sink: usize, capacities: Matrix<C>) -> Selfwhere
    Self: Sized,

Create a new populated structure.

Panics

This function panics when source or sink is greater or equal than the number of rows in the capacities matrix, or it the matrix is not a square one.

fn common(&self) -> &Common<C>

Common data.

fn common_mut(&mut self) -> &mut Common<C>

Mutable common data.

fn residual_successors(&self, from: usize) -> Vec<(usize, C)>

List of successors with positive residual capacity and this capacity.

fn residual_capacity(&self, from: usize, to: usize) -> C

Residual capacity between two nodes.

fn flow(&self, from: usize, to: usize) -> C

Flow between two nodes.

fn flows_from(&self, from: usize) -> Vec<usize>

All positive flows starting from a node.

fn flows(&self) -> Vec<((usize, usize), C)>

All flows between nodes.

fn add_flow(&mut self, from: usize, to: usize, capacity: C)

Add a given flow between two nodes. This should not be used directly.

fn add_residual_capacity(&mut self, from: usize, to: usize, capacity: C)

Add some residual capacity.

Provided Methods

fn from_vec(source: usize, sink: usize, capacities: Vec<C>) -> Selfwhere
    Self: Sized,

Create a new populated structure.

Panics

This function panics when source or sink is greater or equal than the number of rows in the square matrix created from the capacities vector.

fn size(&self) -> usize

Number of nodes.

fn source(&self) -> usize

Source.

fn sink(&self) -> usize

Sink.

fn set_capacity(&mut self, from: usize, to: usize, capacity: C)

Set capacity between two nodes.

fn total_capacity(&self) -> C

Get total capacity.

fn set_total_capacity(&mut self, capacity: C)

Set total capacity.

fn omit_details(&mut self)

Do not request the detailed flows and cuts as a result. The returned flows and cuts will be empty vectors.

fn has_details(&self) -> bool

Are detailed flows and cuts requested?

fn augment(&mut self) -> EKFlows<usize, C>

Compute the maximum flow and minimum cut.

Implementors

impl<C: Copy + Zero + Signed + Eq + Ord + Bounded> EdmondsKarp<C> for SparseCapacity<C>

impl<C: Copy + Zero + Signed + Ord + Bounded> EdmondsKarp<C> for DenseCapacity<C>