Copyright | (c) Masahiro Sakai 2016 |
---|---|
License | BSD-style |
Maintainer | masahiro.sakai@gmail.com |
Stability | experimental |
Portability | non-portable |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
Extensions |
|
This module provides functions for computing several kind of bipartite matching.
Reference:
- Friedrich Eisenbrand. “Linear and Discrete Optimization”. https://www.coursera.org/course/linearopt
Synopsis
- maximumCardinalityMatching :: IntSet -> IntSet -> [(Int, Int)] -> IntMap Int
- maximumWeightMatching :: forall w. Real w => IntSet -> IntSet -> [(Int, Int, w)] -> (w, IntMap Int)
- maximumWeightMatchingComplete :: forall w. Real w => IntSet -> IntSet -> (Int -> Int -> w) -> (w, IntMap Int)
- maximumWeightPerfectMatching :: forall w. Real w => IntSet -> IntSet -> [(Int, Int, w)] -> Maybe (w, IntMap Int, (IntMap w, IntMap w))
- minimumWeightPerfectMatching :: forall w. Real w => IntSet -> IntSet -> [(Int, Int, w)] -> Maybe (w, IntMap Int, (IntMap w, IntMap w))
- maximumWeightPerfectMatchingComplete :: forall w. Real w => IntSet -> IntSet -> (Int -> Int -> w) -> (w, IntMap Int, (IntMap w, IntMap w))
- minimumWeightPerfectMatchingComplete :: forall w. Real w => IntSet -> IntSet -> (Int -> Int -> w) -> (w, IntMap Int, (IntMap w, IntMap w))
- minimumCardinalityEdgeCover :: IntSet -> IntSet -> [(Int, Int)] -> Maybe (Set (Int, Int))
- minimumWeightEdgeCover :: forall w. Real w => IntSet -> IntSet -> [(Int, Int, w)] -> Maybe (Set (Int, Int))
- minimumWeightEdgeCoverComplete :: forall w. Real w => IntSet -> IntSet -> (Int -> Int -> w) -> Maybe (Set (Int, Int))
Maximum cardinality bipartite matching
maximumCardinalityMatching Source #
Maximum cardinality matching on a bipartite graph (A+B, E).
Maximum weight bipartite matching
maximumWeightMatching Source #
:: forall w. Real w | |
=> IntSet | vertex set A |
-> IntSet | vertex set B |
-> [(Int, Int, w)] | edges E⊆A×B and their weights |
-> (w, IntMap Int) |
Maximum weight matching of a bipartite graph (A+B,E).
maximumWeightMatchingComplete Source #
:: forall w. Real w | |
=> IntSet | vertex set A |
-> IntSet | vertex set B |
-> (Int -> Int -> w) | weight of edges A×B |
-> (w, IntMap Int) |
Maximum weight matching of a complete bipartite graph (A+B,A×B).
Maximum/Minimum weight bipartite perfect matching
maximumWeightPerfectMatching Source #
:: forall w. Real w | |
=> IntSet | vertex set A |
-> IntSet | vertex set B |
-> [(Int, Int, w)] | edges E⊆A×B and their weights |
-> Maybe (w, IntMap Int, (IntMap w, IntMap w)) |
Maximum weight perfect matching of a complete bipartite graph (A+B,E).
If no such matching exist, it returns Nothing
.
minimumWeightPerfectMatching Source #
:: forall w. Real w | |
=> IntSet | vertex set A |
-> IntSet | vertex set B |
-> [(Int, Int, w)] | edges E⊆A×B and their weights |
-> Maybe (w, IntMap Int, (IntMap w, IntMap w)) |
Minimum weight perfect matching of a bipartite graph (A+B, E).
If no such matching exist, it returns Nothing
.
maximumWeightPerfectMatchingComplete Source #
:: forall w. Real w | |
=> IntSet | vertex set A |
-> IntSet | vertex set B |
-> (Int -> Int -> w) | weight of edges A×B |
-> (w, IntMap Int, (IntMap w, IntMap w)) |
Maximum weight perfect matching of a complete bipartite graph (A+B,A×B).
The two sets must be same size (|A| = |B|).
minimumWeightPerfectMatchingComplete Source #
:: forall w. Real w | |
=> IntSet | vertex set A |
-> IntSet | vertex set B |
-> (Int -> Int -> w) | weight of edges A×B |
-> (w, IntMap Int, (IntMap w, IntMap w)) |
Minimum weight perfect matching of a complete bipartite graph (A+B,A×B).
The two sets must be same size (|A| = |B|).
Misc
minimumCardinalityEdgeCover Source #
Minimum cardinality edge cover of bipartite graph (A+B, E).