# GOAL.MaxMatching

**Repository Path**: suzhouxing/GOAL.MaxMatching

## Basic Information

- **Project Name**: GOAL.MaxMatching
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-09-27
- **Last Updated**: 2023-08-21

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# GOAL.MaxMatching

## Introduction

a C++ wrapper for efficient maximum matching solvers.


## Directory Structure

- **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.


## Instruction

- add the source files except `Main.cpp` under `MaxMatchingLib/` into your project.
- include the `MatchingSolver.h` in your code.


## Benchmark Results

### N=1000, M=1000, MaxCost=1000, x64

| MaxMatching test                                   | time      | obj     |
| -------------------------------------------------- | --------- | ------- |
|                              MaxMatchingByHarryZHR |     25 ms |  997823 |
|                              MaxMatchingByTopCoder |     42 ms |  997823 |
|                            MinMatchingBySamHocevar |   1172 ms |  997823 |
|                         MinMatchingByRobertPilgrim |  16534 ms |  997823 |
|                            MinMatchingByJohnWeaver |  17672 ms |  997823 |
|                                  MaxMatchingByDlib |     38 ms |  997823 |
|    MaxMatchingByLemonPerfectMatchingOnSmartBpGraph |   1062 ms |  997823 |
|                   MaxMatchingByLemonOnSmartBpGraph |   1056 ms |  997823 |
|     MaxMatchingByLemonPerfectMatchingOnFullBpGraph |    319 ms |  997823 |
|                    MaxMatchingByLemonOnFullBpGraph |    335 ms |  997823 |
|     MinMatchingByLemonNetworkSimplexOnSmartDigraph |    155 ms |  997823 |
|        MinMatchingByLemonCostScalingOnSmartDigraph |    386 ms |  997823 |
|    MinMatchingByLemonCapacityScalingOnSmartDigraph |    157 ms |  997823 |
|     MinMatchingByLemonCycleCancelingOnSmartDigraph |   4269 ms |  997823 |
|                                MaxMatchingByGurobi |   5655 ms |  997823 |

| MinMatching test                                   | time      | obj     |
| -------------------------------------------------- | --------- | ------- |
|                              MaxMatchingByHarryZHR |     25 ms |    1132 |
|                              MaxMatchingByTopCoder |     37 ms |    1132 |
|                            MinMatchingBySamHocevar |   1084 ms |    1132 |
|                         MinMatchingByRobertPilgrim |  17754 ms |    1132 |
|                            MinMatchingByJohnWeaver |  18405 ms |    1132 |
|                                  MaxMatchingByDlib |     35 ms |    1132 |
|    MaxMatchingByLemonPerfectMatchingOnSmartBpGraph |   1040 ms |    1132 |
|                   MaxMatchingByLemonOnSmartBpGraph |   1024 ms |    1132 |
|     MaxMatchingByLemonPerfectMatchingOnFullBpGraph |    324 ms |    1132 |
|                    MaxMatchingByLemonOnFullBpGraph |    330 ms |    1132 |
|     MinMatchingByLemonNetworkSimplexOnSmartDigraph |    166 ms |    1132 |
|        MinMatchingByLemonCostScalingOnSmartDigraph |    405 ms |    1132 |
|    MinMatchingByLemonCapacityScalingOnSmartDigraph |    139 ms |    1132 |
|     MinMatchingByLemonCycleCancelingOnSmartDigraph |   5028 ms |    1132 |
|                                MaxMatchingByGurobi |   5082 ms |    1132 |


## Reference

- https://www.topcoder.com/community/competitive-programming/tutorials/assignment-problem-and-hungarian-algorithm/
- https://github.com/maandree/hungarian-algorithm-n3
- http://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html
- https://github.com/saebyn/munkres-cpp
- http://dlib.net/optimization.html#max_cost_assignment
- http://lemon.cs.elte.hu/trac/lemon
- http://www.gurobi.com