| Copyright | (c) Masahiro Sakai 2016 |
|---|---|
| License | BSD-style |
| Maintainer | masahiro.sakai@gmail.com |
| Stability | experimental |
| Portability | non-portable (ScopedTypeVariables, BangPatterns) |
| Safe Haskell | Safe |
| Language | Haskell2010 |
ToySolver.Combinatorial.BipartiteMatching
Contents
Description
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 #
Arguments
| :: 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 #
Arguments
| :: 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 #
Arguments
| :: 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 #
Arguments
| :: 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 #
Arguments
| :: 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 #
Arguments
| :: 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 #
Arguments
| :: IntSet | vertex set A |
| -> IntSet | vertex set B |
| -> [(Int, Int)] | edges E⊆A×B |
| -> Maybe (Set (Int, Int)) |
Minimum cardinality edge cover of bipartite graph (A+B, E).