Struct mcmf::GraphBuilder [−][src]
pub struct GraphBuilder<T: Clone + Ord> { pub edge_list: Vec<(Vertex<T>, Vertex<T>, Capacity, Cost)>, }
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)>
Methods
impl<T> GraphBuilder<T> where
T: Clone + Ord,
[src]
impl<T> GraphBuilder<T> where
T: Clone + Ord,
pub fn new() -> Self
[src]
pub fn new() -> Self
Creates a new empty graph.
pub fn add_edge<A: Into<Vertex<T>>, B: Into<Vertex<T>>>(
&mut self,
a: A,
b: B,
capacity: Capacity,
cost: Cost
) -> &mut Self
[src]
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.
pub fn mcmf(&self) -> (i32, Vec<Path<T>>)
[src]
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
impl<T: Clone + Clone + Ord> Clone for GraphBuilder<T>
[src]
impl<T: Clone + Clone + Ord> Clone for GraphBuilder<T>
fn clone(&self) -> GraphBuilder<T>
[src]
fn clone(&self) -> GraphBuilder<T>
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
fn clone_from(&mut self, source: &Self)
1.0.0
[src]Performs copy-assignment from source
. Read more
Auto Trait Implementations
impl<T> Send for GraphBuilder<T> where
T: Send,
impl<T> Send for GraphBuilder<T> where
T: Send,
impl<T> Sync for GraphBuilder<T> where
T: Sync,
impl<T> Sync for GraphBuilder<T> where
T: Sync,