# MatchMaker: A collection of algorithms for finding maximum transversals or maximum matchings in bipartite graphs.

This repository contains efficient implementations of a number of 
algorithms for the maximum cardinality matching in bipartite graphs.

The algorithms are described in the following three papers.

<pre>

@article{klmu:13m,
	Author = {Kaya, Kamer and Langguth, Johannes and Manne, Fredrik and U\c{c}ar, Bora},
	Journal = {Computers \& Operations Research},
	Number = {5},
	Pages = {1266--1275},
	Title = {Push-relabel based algorithms for the maximum transversal problem},
	Volume = {40},
	URL = {https://hal.inria.fr/hal-00763920},
	Year = {2013}
}

@article{duku:12m,
	Author = {Duff, Iain S. and Kaya, Kamer and U\c{c}ar, Bora},
	Journal = {{ACM} Transactions on Mathematical Software},
	Pages = {13:1--13:31},
	Title = {Design, implementation, and analysis of maximum transversal algorithms},
	Volume = {38},
	URL={https://hal.inria.fr/hal-00786548},
	Year = {2012}
}

@inproceedings{pauc:20,
               author = {Ioannis Panagiotas and Bora U{\c{c}}ar},
               booktitle = {28th Annual European Symposium on Algorithms, {ESA} 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference)},
               editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
               pages = {76:1--76:23},
               publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
               series = {LIPIcs},
               title = {Engineering Fast Almost Optimal Algorithms for Bipartite Graph Matching},
               volume = {173},
               year = {2020}
}

</pre>

## License
See the file LICENSE. The software is under CeCILL-B license, which is a BSD-like license.

## Contact
The e-mail addresses of the authors are:
kamer.kaya@sabanciuniv.edu, langguth@simula.no, ioannis.panagiotas@outlook.com, and bora.ucar@cnrs.fr.

## Build
The codes are written in C and are easily callable. 
We provide a julia interace and a mex interface for ease of use in Matlab.

## Usage and arguments
The julia file sampleUsemmaker.jl and the Matlab file mmaker.m contain
examples and help.

## Files
+ LICENSE: Describes the CeCILL-B license.
+ README.md: This file.
+ cheap.c: Implementations of 5 jump-start routines.
    - 0: No initialization
	- 1: Simple Greedy
	- 2: Karp-Sipser
	- 3: Random Karp-Sipser
	- 4: Minimum Degree (two-sided)
	- 5: Truncated random walk

+ matching.c: Implementations of 10 maximum transversal algorithms.
	- 0: No augmentation
	- 1: DFS based
	- 2: BFS based
	- 3: MC21 (DFS + lookahead)
	- 4: PF (Pothen and Fan's algorithm)
	- 5: PF+ (PF + fairness)
	- 6: HK (Hopcroft and Karp's algorithm)
	- 7: HK-DW (Duff-Wiberg implementation of HK)
	- 8: ABMP (Alt et al.'s algorithm)
	- 9: ABMP-BFS (ABMP + BFS)
	- 10: Push-Relabel + fairness

+ matchmaker.h: Defines constants for the project.

+ matlab/README.md: information on the matlab interface.
+ matlab/mmaker.c: Matlab (mex) interface for the algorithms. 
+ matlab/mmaker.m: for use in MATLAB, contains the help.

+ julia/README.md: information on the julia interface.
+ julia/mmaker.jl: the julia interface.
+ julia/mmaker_h.jl: wraps a call to the library.
+ julia/sampleUsemmaker.jl: sample use cases.

## Versions
This is version v1.0 (February 2022). 
It includes the initialization algorithm/heuristic 5 and moves files in suitable directories.
Version v0.9 (February 2022) included the julia interface.