[−][src]Trait rs_graph::maxflow::MaxFlow
Trait for max flow algorithms.
Associated Types
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,
&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.
Provided methods
Loading content...Implementors
impl<'a, G, F> MaxFlow<'a> for Dinic<'a, G, F> where
G: IndexDigraph<'a>,
F: NumAssign + Ord + Copy,
[src]
G: IndexDigraph<'a>,
F: NumAssign + Ord + Copy,
type Graph = G
type Flow = F
fn new(g: &'a G) -> Self
[src]
fn as_graph(&self) -> &'a Self::Graph
[src]
fn value(&self) -> F
[src]
fn flow(&self, e: G::Edge) -> F
[src]
fn solve<Us>(&mut self, src: G::Node, snk: G::Node, upper: Us) where
Us: Fn(G::Edge) -> Self::Flow,
[src]
Us: Fn(G::Edge) -> Self::Flow,
fn mincut(&self) -> Vec<G::Node>
[src]
impl<'a, G, F> MaxFlow<'a> for EdmondsKarp<'a, G, F> where
'a: 'a,
G: IndexDigraph<'a>,
F: NumAssign + Ord + Copy,
[src]
'a: 'a,
G: IndexDigraph<'a>,
F: NumAssign + Ord + Copy,
type Graph = G
type Flow = F
fn new(g: &'a G) -> Self
[src]
fn as_graph(&self) -> &'a Self::Graph
[src]
fn value(&self) -> F
[src]
fn flow(&self, e: G::Edge) -> F
[src]
fn solve<Us>(&mut self, src: G::Node, snk: G::Node, upper: Us) where
Us: Fn(G::Edge) -> Self::Flow,
[src]
Us: Fn(G::Edge) -> Self::Flow,
fn mincut(&self) -> Vec<G::Node>
[src]
impl<'a, G, F> MaxFlow<'a> for PushRelabel<'a, G, F> where
G: IndexDigraph<'a>,
F: NumAssign + Ord + Copy,
[src]
G: IndexDigraph<'a>,
F: NumAssign + Ord + Copy,
type Graph = G
type Flow = F
fn new(g: &'a G) -> Self
[src]
Return a new push-relabel algorithm data structure for the digraph g
.
fn as_graph(&self) -> &'a Self::Graph
[src]
Return a reference to the underlying graph.
fn value(&self) -> F
[src]
Return the flow value.
The function returns 0 if the flow has not been computed, yet.
fn flow(&self, e: G::Edge) -> F
[src]
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,
[src]
Us: Fn(G::Edge) -> Self::Flow,
Run the push-relabel algorithm from some source to some sink node.
fn mincut(&self) -> Vec<G::Node>
[src]
Return the minimal cut.