Struct GraphBuilder

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)>

Implementations

impl<T> GraphBuilder<T>

where T: Clone + Ord,

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

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>>)

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>

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

Returns a copy of the value.

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

Performs copy-assignment from source.