Struct GraphBuilder

Source
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>
where T: Clone + Ord,

Source

pub fn new() -> Self

Creates a new empty graph.

Source

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.

Source

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§

Source§

impl<T: Clone + Clone + Ord> Clone for GraphBuilder<T>

Source§

fn clone(&self) -> GraphBuilder<T>

Returns a copy of the value. Read more
1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more

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> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.