Crate mcmf

This crate is for solving instances of the minimum cost maximum flow problem. It uses the network simplex algorithm from the LEMON graph optimization library.

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

Structs

Capacity

Wrapper type representing the capacity of an edge in the graph.

Cost

Wrapper type representing the cost of an edge in the graph.

Flow

Represents flow in a solution to the minimum cost maximum flow problem.

GraphBuilder

Use this struct to build a graph, then call the mcmf() function to find its minimum cost maximum flow.

Path

Represents a path from the source to the sink in a solution to the minimum cost maximum flow problem.

Enums

Vertex

This class represents a vertex in a graph. It is parametrized by T so that users of the library can use the most convenient type for representing nodes in the graph.