This repository is a fork of dilsonpereira/Minimum-Cost-Perfect-Matching The library is converted to a header only library.

Algorithms for Maximum Cardinality Matching and Minimum Cost Perfect Matching Problems in General Graphs

Dilson Lucas Pereira (dilsonpereira) implemented these algorithms during his PhD, in 2011, following the description in:

Gerards, A.M.H. (1995). Matching. In Ball, M., Magnanti, T., Monma, C., and Nemhauser, G., editors, Network Models, volume 7 of Handbooks in Operations Research and Management Science, chapter 3, pages 135-224. Elsevier.

See example.cc for examples of how to use the API.

Compilation with g++:

bash setup.sh

To use as a matching solver:

./bin/example -f <filename> <--minweight | --max>

--minweight for minimum weight perfect matching

--max for maximum cardinality matching

File format:

the first two lines give n (number of vertices) and m (number of edges), respectively, followed by m lines, each with a tuple (u, v [, c]) representing the edges. In each tuple, u and v are the endpoints (0-based indexing) of the edge and c is its cost. The cost is optional if --max is specified.

Example, input.txt:

10
16
0 1 10
0 2 4
1 2 3
1 5 2
1 6 2
2 3 1
2 4 2
3 4 5
4 6 4
4 7 1
4 8 3
5 6 1
6 7 2
7 8 3
7 9 2
8 9 1

./bin/example -f input.txt --minweight

Output:

Optimal matching cost: 14
Edges in the matching:
0 1
2 3
4 7
5 6
8 9

Feel free to contact Dilson Lucas Pereira (dilsonpereira) if you have any problem.