pub struct GraphBuilder<T: Clone + Ord> {
pub edge_list: Vec<(Vertex<T>, Vertex<T>, Capacity, Cost)>,
}
Expand description
Use this struct to build a graph, then call the mcmf()
function to find its minimum cost maximum flow.
§Example
use mcmf::{GraphBuilder, Vertex, Cost, Capacity};
let (cost, paths) = GraphBuilder::new()
.add_edge(Vertex::Source, "Vancouver", Capacity(2), Cost(0))
.add_edge("Vancouver", "Toronto", Capacity(2), Cost(100))
.add_edge("Toronto", "Halifax", Capacity(1), Cost(150))
.add_edge("Vancouver", "Halifax", Capacity(5), Cost(400))
.add_edge("Halifax", Vertex::Sink, Capacity(2), Cost(0))
.mcmf();
assert_eq!(cost, 650);
assert_eq!(cost, paths.iter().map(|path| path.cost()).sum());
assert_eq!(paths.len(), 2);
assert!(
paths[0].vertices() == vec![
&Vertex::Source,
&Vertex::Node("Vancouver"),
&Vertex::Node("Halifax"),
&Vertex::Sink]);
assert!(
paths[1].vertices() == vec![
&Vertex::Source,
&Vertex::Node("Vancouver"),
&Vertex::Node("Toronto"),
&Vertex::Node("Halifax"),
&Vertex::Sink]);
Fields§
§edge_list: Vec<(Vertex<T>, Vertex<T>, Capacity, Cost)>
Implementations§
Source§impl<T> GraphBuilder<T>
impl<T> GraphBuilder<T>
Sourcepub fn add_edge<A: Into<Vertex<T>>, B: Into<Vertex<T>>>(
&mut self,
a: A,
b: B,
capacity: Capacity,
cost: Cost,
) -> &mut Self
pub fn add_edge<A: Into<Vertex<T>>, B: Into<Vertex<T>>>( &mut self, a: A, b: B, capacity: Capacity, cost: Cost, ) -> &mut Self
Add an edge to the graph.
capacity
and cost
have wrapper types so that you can’t mix them up.
Panics if capacity
is negative.
Sourcepub fn mcmf(&self) -> (i32, Vec<Path<T>>)
pub fn mcmf(&self) -> (i32, Vec<Path<T>>)
Computes the minimum cost maximum flow.
Returns a tuple (total cost, list of paths). The paths are sorted in ascending order by length.
This gives incorrect results when the total cost or the total flow exceeds 2^(31)-1. It is the responsibility of the caller to ensure that the total cost doesn’t exceed 2^(31)-1.
Trait Implementations§
Auto Trait Implementations§
impl<T> Freeze for GraphBuilder<T>
impl<T> RefUnwindSafe for GraphBuilder<T>where
T: RefUnwindSafe,
impl<T> Send for GraphBuilder<T>where
T: Send,
impl<T> Sync for GraphBuilder<T>where
T: Sync,
impl<T> Unpin for GraphBuilder<T>where
T: Unpin,
impl<T> UnwindSafe for GraphBuilder<T>where
T: UnwindSafe,
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more