#flow #graph #optimization #min-max #networking

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

#17 in #min-max

Download history 84/week @ 2024-05-20 51/week @ 2024-05-27 130/week @ 2024-06-03 72/week @ 2024-06-10 58/week @ 2024-06-17 54/week @ 2024-06-24 27/week @ 2024-07-01 32/week @ 2024-07-08 122/week @ 2024-07-15 193/week @ 2024-07-22 121/week @ 2024-07-29 184/week @ 2024-08-05 24/week @ 2024-08-12 48/week @ 2024-08-19 27/week @ 2024-08-26 54/week @ 2024-09-02

173 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