``kap``: $k$-Assignment Problem Solver
======
[](https://github.com/inspiros/kap/actions) [](https://pypi.org/project/kap) [](https://pepy.tech/project/kap) [](https://github.com/inspiros/kap/blob/master/LICENSE.txt)
This project implements **Boštjan Gabrovšek**'s Multiple Hungarian Methods for solving the **$k$-Assignment Problem**
(or **$k$-Partite Graph Matching Problem**), described in [this paper](https://www.mdpi.com/2227-7390/8/11/2050).
## Background
### Problem Formulation
**$k$-Assignment (a.k.a. $k$-Partite Graph Matching) Problem** is the extension of **Linear Assignment
(Bipartite Graph Matching) Problem**.
It is also traditionally referred to as **Multidimensional Assignment Problem**.
<p align="center">
<img src="https://raw.githubusercontent.com/inspiros/kap/master/resources/tripartite_matching_example.png" width="300">
</p>
Formally, we seek a $k$-assignment of a given $k$-partite weighted graph $G = (V, E, \omega)$ with the minimum weight:
```math
\min{\sum\limits_{\mathcal{Q}}{\omega(\mathcal{Q})\ |\ \mathcal{Q}\text{ is a }k\text{-assignment in }G}}
```
where
```math
\omega(\mathcal{Q}) = \sum\limits_{e \in E(G[\mathcal{Q}])}{\omega(e)}
```
This repository provides the implementation of 6 algorithms proposed by Gabrovšek for solving this problem,
which is decomposed into small binary sub-problems and tackled with using the Hungarian procedure.
While this means we can generalize for an arbitrary number $k$ and use different algorithms other than Hungarian,
the methods might not be the most efficient for certain cases (e.g. $k = 3$ a.k.a. the **3-index Assignment Problem**).
For more technical details, please refer to the [paper](https://www.mdpi.com/2227-7390/8/11/2050)
or contact the authors, not me 😂.
### Context
I implemented this code for testing an idea in another project.
After that, I decided to publish the code so that someone facing a similar problem can use.
Further maintenance or performance tuning might be limited, but all contribution is welcome.
## Requirements
- **Python 3.7+**
- ``numpy``
- ``scipy`` or ``lap`` or ``lapjv`` or ``lapsolver`` or ``munkres``
_(depends on the backend to be used for solving Linear Assignment Problem)_
## Installation
Simply run the following command:
```
pip install kap
```
#### Notes
This is currently a pure Python project, but we may add Cython/C++ extension in the future.
## Quick Start
### Solving Linear Assignment Problem
For convenience, we provide ``kap.linear_assignment`` as a wrapper around backend functions.
The available backends are:
- ``scipy``: [``scipy.optimize.linear_sum_assignment``'s documentation](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html)
- ``lap``: https://github.com/gatagat/lap
- ``lapjv``: https://github.com/src-d/lapjv
- ``lapsolver``: https://github.com/cheind/py-lapsolver
- ``munkres``: https://github.com/bmc/munkres
Note that we currently do **NOT** support sparse matrix.
For a benchmark, please head to https://github.com/berhane/LAP-solvers.
The interface is unified as ``kap.linear_assignment`` returns a namedtuple of ``matches``,
``matching_costs`` of matched edges, and optionally a list of ``free``(or unmatched) vertices if called with
``return_free=True``.
```python
import numpy as np
from kap import linear_assignment
cost = np.array([
[9, 6, 4],
[4, 4, 6],
[3, 9, 2]
])
matching_result = linear_assignment(cost, return_free=True, backend="lap")
print("Result:", matching_result)
# Result: AssignmentResult(matches=array([[0, 2],
# [1, 1],
# [2, 0]], dtype=int64), matching_costs=array([4, 4, 3]), free=[])
print("Total cost:", sum(matching_result.matching_costs))
# Total cost: 11
```
### Solving $k$-Assignment Problem
``kap.k_assignment`` is the equivalence for $k$-Assignment Problem.
There are a few things to note about its parameters:
- ``cost_matrices``: Sequence of $n (n - 1) / 2$ 2D cost matrices of pairwise matching costs between $n$ partites
(might not be able to be represented as a 3D ``np.ndarray`` since partites can have different number of vertices)
ordered as in ``itertools.combination(n, 2)``. For example, $[C_{01}, C_{02}, C_{03}, C_{12}, C_{13}, C_{23}]$.
- ``algo``: This should be one of the six proposed algorithms, namely ``"Am", "Bm", "Cm", "Dm", "Em", "Fm"``.
$\text{C}_m$ is set to be the default as it usually performs as good as random approaches while having a
deterministic behavior.
It's return type shares the same structure as that of ``kap.linear_assignment`` but with some small differences:
- ``matches``: Each element is the list of indices of matched vertices. For example, ``[(0, 0), (1, 1), (2, 0)]``
indicates that node 0 of partite 0, node 1 of partite 1, and node 0 of partite 3 are matched together.
Note that it is **NOT** necessary for a match to contain at least one vertex from each partite (incomplete graph).
- ``matching_costs``: Each element is the sum of pairwise costs of all edges formed by the matched vertices.
The following code reproduce the example described in the paper.
```python
import numpy as np
from kap import k_assignment
costs = [
np.array([ # (0, 1)
[9, 6, 4],
[4, 4, 6],
[3, 9, 2]
]),
np.array([ # (0, 2)
[8, 2, 9],
[5, 0, 4],
[8, 7, 4]
]),
np.array([ # (1, 2)
[4, 0, 9],
[9, 9, 6],
[8, 9, 5]
]),
]
matching_result = k_assignment(costs, algo="Em", return_free=True, backend="lap")
print("Result:", matching_result)
# Result: AssignmentResult(matches=[[(0, 0), (1, 1), (2, 0)], [(0, 1), (1, 0), (2, 1)], [(0, 2), (1, 2), (2, 2)]], matching_costs=[23, 4, 11], free=[])
print("Total cost:", sum(matching_result.matching_costs))
# Total cost: 38
```
These code blocks are extracted from [examples](examples).
## License
MIT licensed. See [LICENSE.txt](LICENSE.txt).
Raw data
{
"_id": null,
"home_page": "https://github.com/inspiros/kap",
"name": "kap",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": "",
"keywords": "k-assignment,k-partite-matching,linear-assignment,bi-partite-matching,hungarian",
"author": "Hoang-Nhat Tran (inspiros)",
"author_email": "hnhat.tran@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/2d/fd/836e380b9d9673427702aea612a6f585e55130b5d260affbcf62a14d1838/kap-0.2.1.tar.gz",
"platform": null,
"description": "``kap``: $k$-Assignment Problem Solver\n======\n[](https://github.com/inspiros/kap/actions) [](https://pypi.org/project/kap) [](https://pepy.tech/project/kap) [](https://github.com/inspiros/kap/blob/master/LICENSE.txt)\n\nThis project implements **Bo\u0161tjan Gabrov\u0161ek**'s Multiple Hungarian Methods for solving the **$k$-Assignment Problem**\n(or **$k$-Partite Graph Matching Problem**), described in [this paper](https://www.mdpi.com/2227-7390/8/11/2050).\n\n## Background\n\n### Problem Formulation\n\n**$k$-Assignment (a.k.a. $k$-Partite Graph Matching) Problem** is the extension of **Linear Assignment\n(Bipartite Graph Matching) Problem**.\nIt is also traditionally referred to as **Multidimensional Assignment Problem**.\n\n<p align=\"center\">\n <img src=\"https://raw.githubusercontent.com/inspiros/kap/master/resources/tripartite_matching_example.png\" width=\"300\">\n</p>\n\nFormally, we seek a $k$-assignment of a given $k$-partite weighted graph $G = (V, E, \\omega)$ with the minimum weight:\n\n```math\n\\min{\\sum\\limits_{\\mathcal{Q}}{\\omega(\\mathcal{Q})\\ |\\ \\mathcal{Q}\\text{ is a }k\\text{-assignment in }G}}\n```\nwhere\n```math\n\\omega(\\mathcal{Q}) = \\sum\\limits_{e \\in E(G[\\mathcal{Q}])}{\\omega(e)}\n```\n\nThis repository provides the implementation of 6 algorithms proposed by Gabrov\u0161ek for solving this problem, \nwhich is decomposed into small binary sub-problems and tackled with using the Hungarian procedure.\nWhile this means we can generalize for an arbitrary number $k$ and use different algorithms other than Hungarian,\nthe methods might not be the most efficient for certain cases (e.g. $k = 3$ a.k.a. the **3-index Assignment Problem**).\n\nFor more technical details, please refer to the [paper](https://www.mdpi.com/2227-7390/8/11/2050)\nor contact the authors, not me \ud83d\ude02.\n\n### Context\n\nI implemented this code for testing an idea in another project.\nAfter that, I decided to publish the code so that someone facing a similar problem can use.\nFurther maintenance or performance tuning might be limited, but all contribution is welcome.\n\n## Requirements\n\n- **Python 3.7+**\n- ``numpy``\n- ``scipy`` or ``lap`` or ``lapjv`` or ``lapsolver`` or ``munkres``\n _(depends on the backend to be used for solving Linear Assignment Problem)_\n\n## Installation\n\nSimply run the following command:\n\n```\npip install kap\n```\n\n#### Notes\n\nThis is currently a pure Python project, but we may add Cython/C++ extension in the future.\n\n## Quick Start\n\n### Solving Linear Assignment Problem\n\nFor convenience, we provide ``kap.linear_assignment`` as a wrapper around backend functions.\nThe available backends are:\n- ``scipy``: [``scipy.optimize.linear_sum_assignment``'s documentation](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html)\n- ``lap``: https://github.com/gatagat/lap\n- ``lapjv``: https://github.com/src-d/lapjv\n- ``lapsolver``: https://github.com/cheind/py-lapsolver\n- ``munkres``: https://github.com/bmc/munkres\n\nNote that we currently do **NOT** support sparse matrix.\nFor a benchmark, please head to https://github.com/berhane/LAP-solvers.\n\nThe interface is unified as ``kap.linear_assignment`` returns a namedtuple of ``matches``,\n``matching_costs`` of matched edges, and optionally a list of ``free``(or unmatched) vertices if called with\n``return_free=True``.\n\n```python\nimport numpy as np\n\nfrom kap import linear_assignment\n\ncost = np.array([\n [9, 6, 4],\n [4, 4, 6],\n [3, 9, 2]\n])\nmatching_result = linear_assignment(cost, return_free=True, backend=\"lap\")\nprint(\"Result:\", matching_result)\n# Result: AssignmentResult(matches=array([[0, 2],\n# [1, 1],\n# [2, 0]], dtype=int64), matching_costs=array([4, 4, 3]), free=[])\nprint(\"Total cost:\", sum(matching_result.matching_costs))\n# Total cost: 11\n```\n\n### Solving $k$-Assignment Problem\n\n``kap.k_assignment`` is the equivalence for $k$-Assignment Problem.\nThere are a few things to note about its parameters:\n- ``cost_matrices``: Sequence of $n (n - 1) / 2$ 2D cost matrices of pairwise matching costs between $n$ partites\n (might not be able to be represented as a 3D ``np.ndarray`` since partites can have different number of vertices)\n ordered as in ``itertools.combination(n, 2)``. For example, $[C_{01}, C_{02}, C_{03}, C_{12}, C_{13}, C_{23}]$.\n- ``algo``: This should be one of the six proposed algorithms, namely ``\"Am\", \"Bm\", \"Cm\", \"Dm\", \"Em\", \"Fm\"``.\n $\\text{C}_m$ is set to be the default as it usually performs as good as random approaches while having a\n deterministic behavior.\n\nIt's return type shares the same structure as that of ``kap.linear_assignment`` but with some small differences:\n- ``matches``: Each element is the list of indices of matched vertices. For example, ``[(0, 0), (1, 1), (2, 0)]``\n indicates that node 0 of partite 0, node 1 of partite 1, and node 0 of partite 3 are matched together.\n Note that it is **NOT** necessary for a match to contain at least one vertex from each partite (incomplete graph).\n- ``matching_costs``: Each element is the sum of pairwise costs of all edges formed by the matched vertices.\n\nThe following code reproduce the example described in the paper.\n\n```python\nimport numpy as np\n\nfrom kap import k_assignment\n\ncosts = [\n np.array([ # (0, 1)\n [9, 6, 4],\n [4, 4, 6],\n [3, 9, 2]\n ]),\n np.array([ # (0, 2)\n [8, 2, 9],\n [5, 0, 4],\n [8, 7, 4]\n ]),\n np.array([ # (1, 2)\n [4, 0, 9],\n [9, 9, 6],\n [8, 9, 5]\n ]),\n]\nmatching_result = k_assignment(costs, algo=\"Em\", return_free=True, backend=\"lap\")\nprint(\"Result:\", matching_result)\n# Result: AssignmentResult(matches=[[(0, 0), (1, 1), (2, 0)], [(0, 1), (1, 0), (2, 1)], [(0, 2), (1, 2), (2, 2)]], matching_costs=[23, 4, 11], free=[])\nprint(\"Total cost:\", sum(matching_result.matching_costs))\n# Total cost: 38\n```\n\nThese code blocks are extracted from [examples](examples).\n\n## License\n\nMIT licensed. See [LICENSE.txt](LICENSE.txt).\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Gabrov\u0161ek's Multiple Hungarian method for solving k-Assignment Problem.",
"version": "0.2.1",
"project_urls": {
"Homepage": "https://github.com/inspiros/kap",
"Source": "https://github.com/inspiros/kap"
},
"split_keywords": [
"k-assignment",
"k-partite-matching",
"linear-assignment",
"bi-partite-matching",
"hungarian"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "564cbf0c9e89a4bd09c70d7621cd05ef33ee8521b9f73d1158425c5c30f516ae",
"md5": "4b26463c0ddfa18810398922949a155a",
"sha256": "f13233f1a72e0cd54b5462ad53117dc59073e8ee2ad4288ab0de2c536daba4dc"
},
"downloads": -1,
"filename": "kap-0.2.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "4b26463c0ddfa18810398922949a155a",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.7",
"size": 11526,
"upload_time": "2024-01-02T00:36:41",
"upload_time_iso_8601": "2024-01-02T00:36:41.416141Z",
"url": "https://files.pythonhosted.org/packages/56/4c/bf0c9e89a4bd09c70d7621cd05ef33ee8521b9f73d1158425c5c30f516ae/kap-0.2.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "2dfd836e380b9d9673427702aea612a6f585e55130b5d260affbcf62a14d1838",
"md5": "984d4421790c7dc60038a6f898465e43",
"sha256": "20ae812a7a6234ef014e0b80791dff5c983f7fb4a7017f2116e5cf7f00aaf308"
},
"downloads": -1,
"filename": "kap-0.2.1.tar.gz",
"has_sig": false,
"md5_digest": "984d4421790c7dc60038a6f898465e43",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 13903,
"upload_time": "2024-01-02T00:36:42",
"upload_time_iso_8601": "2024-01-02T00:36:42.998819Z",
"url": "https://files.pythonhosted.org/packages/2d/fd/836e380b9d9673427702aea612a6f585e55130b5d260affbcf62a14d1838/kap-0.2.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-01-02 00:36:42",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "inspiros",
"github_project": "kap",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"requirements": [
{
"name": "numpy",
"specs": []
}
],
"lcname": "kap"
}
JSON
