#flow #graph #optimization #min-max

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.

3 stable releases

Uses old Rust 2015

2.0.0 Aug 30, 2018
1.1.0 Dec 12, 2017
1.0.0 Dec 12, 2017

#1589 in Algorithms

Download history 49/week @ 2023-11-27 87/week @ 2023-12-04 73/week @ 2023-12-11 41/week @ 2023-12-18 24/week @ 2024-01-08 15/week @ 2024-01-15 7/week @ 2024-01-22 47/week @ 2024-01-29 17/week @ 2024-02-05 72/week @ 2024-02-12 47/week @ 2024-02-19 48/week @ 2024-02-26 75/week @ 2024-03-04 49/week @ 2024-03-11

227 downloads per month
Used in optimal-transport

MIT license

440KB
3.5K SLoC

C++ 3.5K SLoC // 0.1% comments Rust 322 SLoC // 0.0% comments

mcmf

Version

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.

A number of problems are special cases of min cost max flow, including max flow, single-source shortest path, and maximum weighted matching on a bipartite graph.

As such, this crate can solve all of the above problems, though it may potentially be less efficient than a specialized algorithm.

See the documentation.

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

No runtime deps