#graph #flow #optimization

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

#878 in Algorithms

Download history 7/week @ 2021-06-02 11/week @ 2021-06-09 5/week @ 2021-06-16 6/week @ 2021-06-23 7/week @ 2021-06-30 6/week @ 2021-07-07 8/week @ 2021-07-14 5/week @ 2021-07-21 12/week @ 2021-07-28 12/week @ 2021-08-04 10/week @ 2021-08-11 3/week @ 2021-08-18 7/week @ 2021-08-25 1/week @ 2021-09-01 7/week @ 2021-09-08 4/week @ 2021-09-15

94 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