Trait rs_graph::maxflow::MaxFlow
[−]
[src]
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<'b>(
&mut self,
src: <Self::Graph as Graph<'a>>::Node,
snk: <Self::Graph as Graph<'a>>::Node,
upper: &EdgeSlice<'a, 'b, Self::Graph, Self::Flow>
); fn mincut(&self) -> Vec<<Self::Graph as Graph<'a>>::Node>; fn flow_vec(&self) -> EdgeVec<'a, Self::Graph, Self::Flow> { ... } }
Trait for max flow algorithms.
Associated Types
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<'b>(
&mut self,
src: <Self::Graph as Graph<'a>>::Node,
snk: <Self::Graph as Graph<'a>>::Node,
upper: &EdgeSlice<'a, 'b, Self::Graph, Self::Flow>
)
&mut self,
src: <Self::Graph as Graph<'a>>::Node,
snk: <Self::Graph as Graph<'a>>::Node,
upper: &EdgeSlice<'a, 'b, 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
Implementors
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 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 PushRelabel<'a, G, F> where
G: IndexNetwork<'a>,
F: NumAssign + Ord + Copy, type Graph = G; type Flow = F;