a C++ wrapper for efficient maximum matching solvers.
- MaxMatchingLib/ the C++ wrapper for TSM.
- MatchingSolver.h includes all implementations and provides common utilities.
- Main.cpp the sample code for invoking the library.
- MaxMatchingByXXX.cpp the refactored C++ versions of different algorithm implementations.
- Doc/ the relating papers.
- add the source files except
Main.cppunderMaxMatchingLib/into your project. - include the
MatchingSolver.hin your code.
| MaxMatching test | time | obj |
|---|---|---|
| MaxMatchingByTopCoder | 98 ms | 996824 |
| MinMatchingBySamHocevar | 1974 ms | 996824 |
| MinMatchingByRobertPilgrim | 20374 ms | 996824 |
| MinMatchingByJohnWeaver | 18072 ms | 996824 |
| MaxMatchingByDlib | 76 ms | 996824 |
| MaxMatchingByLemonPerfectMatchingOnSmartBpGraph | 1771 ms | 996824 |
| MaxMatchingByLemonOnSmartBpGraph | 1780 ms | 996824 |
| MaxMatchingByLemonPerfectMatchingOnFullBpGraph | 588 ms | 996824 |
| MaxMatchingByLemonOnFullBpGraph | 576 ms | 996824 |
| MinMatchingByLemonNetworkSimplexOnSmartDigraph | 194 ms | 996824 |
| MinMatchingByLemonCostScalingOnSmartDigraph | 750 ms | 996824 |
| MinMatchingByLemonCapacityScalingOnSmartDigraph | 252 ms | 996824 |
| MinMatchingByLemonCycleCancelingOnSmartDigraph | 7486 ms | 996824 |
| MinMatching test | time | obj |
|---|---|---|
| MaxMatchingByTopCoder | 61 ms | 1129 |
| MinMatchingBySamHocevar | 1931 ms | 1129 |
| MinMatchingByRobertPilgrim | 21314 ms | 1129 |
| MinMatchingByJohnWeaver | 18710 ms | 1129 |
| MaxMatchingByDlib | 69 ms | 1129 |
| MaxMatchingByLemonPerfectMatchingOnSmartBpGraph | 1729 ms | 1129 |
| MaxMatchingByLemonOnSmartBpGraph | 1701 ms | 1129 |
| MaxMatchingByLemonPerfectMatchingOnFullBpGraph | 599 ms | 1129 |
| MaxMatchingByLemonOnFullBpGraph | 568 ms | 1129 |
| MinMatchingByLemonNetworkSimplexOnSmartDigraph | 204 ms | 1129 |
| MinMatchingByLemonCostScalingOnSmartDigraph | 723 ms | 1129 |
| MinMatchingByLemonCapacityScalingOnSmartDigraph | 250 ms | 1129 |
| MinMatchingByLemonCycleCancelingOnSmartDigraph | 8881 ms | 1129 |
| MaxMatching test | time | obj |
|---|---|---|
| MaxMatchingByTopCoder | 73 ms | 996824 |
| MinMatchingBySamHocevar | 2018 ms | 996824 |
| MinMatchingByRobertPilgrim | 16534 ms | 996824 |
| MinMatchingByJohnWeaver | 17672 ms | 996824 |
| MaxMatchingByDlib | 58 ms | 996824 |
| MaxMatchingByLemonPerfectMatchingOnSmartBpGraph | 1751 ms | 996824 |
| MaxMatchingByLemonOnSmartBpGraph | 1741 ms | 996824 |
| MaxMatchingByLemonPerfectMatchingOnFullBpGraph | 555 ms | 996824 |
| MaxMatchingByLemonOnFullBpGraph | 526 ms | 996824 |
| MinMatchingByLemonNetworkSimplexOnSmartDigraph | 218 ms | 996824 |
| MinMatchingByLemonCostScalingOnSmartDigraph | 539 ms | 996824 |
| MinMatchingByLemonCapacityScalingOnSmartDigraph | 232 ms | 996824 |
| MinMatchingByLemonCycleCancelingOnSmartDigraph | 7368 ms | 996824 |
| MaxMatchingByGurobi | 7534 ms | 996824 |
| MinMatching test | time | obj |
|---|---|---|
| MaxMatchingByTopCoder | 53 ms | 1129 |
| MinMatchingBySamHocevar | 2420 ms | 1129 |
| MinMatchingByRobertPilgrim | 17754 ms | 1129 |
| MinMatchingByJohnWeaver | 18405 ms | 1129 |
| MaxMatchingByDlib | 60 ms | 1129 |
| MaxMatchingByLemonPerfectMatchingOnSmartBpGraph | 1720 ms | 1129 |
| MaxMatchingByLemonOnSmartBpGraph | 1689 ms | 1129 |
| MaxMatchingByLemonPerfectMatchingOnFullBpGraph | 564 ms | 1129 |
| MaxMatchingByLemonOnFullBpGraph | 598 ms | 1129 |
| MinMatchingByLemonNetworkSimplexOnSmartDigraph | 233 ms | 1129 |
| MinMatchingByLemonCostScalingOnSmartDigraph | 529 ms | 1129 |
| MinMatchingByLemonCapacityScalingOnSmartDigraph | 219 ms | 1129 |
| MinMatchingByLemonCycleCancelingOnSmartDigraph | 8044 ms | 1129 |
| MaxMatchingByGurobi | 6738 ms | 1129 |
- https://www.topcoder.com/community/competitive-programming/tutorials/assignment-problem-and-hungarian-algorithm/
- https://github.com/maandree/hungarian-algorithm-n3
- https://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html
- https://github.com/saebyn/munkres-cpp
- https://dlib.net/optimization.html#max_cost_assignment
- https://lemon.cs.elte.hu/trac/lemon
- https://www.gurobi.com