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
173 downloads per month
Used in optimal-transport
440KB
3.5K
SLoC
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.
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]);