Python 3 implementation of the Hungarian Algorithm for the assignment problem.
Project description
Hungarian Algorithm
A Python 3 implementation of the Hungarian Algorithm (a.k.a. the Kuhn-Munkres algorithm), an O(n^3) solution for the assignment problem, or maximum-weighted bipartite matching problem.
Example
Suppose you're choosing 11 starting positions for a soccer team.
The 11 players submit their top 3 position choices, and it is your job to create the optimal team.
The situation can be modeled with a weighted bipartite graph:
Then, if you assign weight 3 to blue edges, weight 2 to red edges and weight 1 to green edges, your job is simply to find the matching that maximizes total weight. This is the assignment problem, for which the Hungarian Algorithm offers a solution.
Notice: although no one has chosen LB, the algorithm will still assign a player there. In fact, the first step of the algorithm is to create a complete bipartite graph (all possible edges exist), giving new edges weight 0.
Usage
Import
from algorithm import hungarian_algorithm
Required Input
Define your weighted bipartite graph in the following manner:
G = {
'Ann': {'RB': 3, 'CAM': 2, 'GK': 1},
'Ben': {'LW': 3, 'S': 2, 'CM': 1},
'Cal': {'CAM': 3, 'RW': 2, 'SWP': 1},
'Dan': {'S': 3, 'LW': 2, 'GK': 1},
'Ela': {'GK': 3, 'LW': 2, 'F': 1},
'Fae': {'CM': 3, 'GK': 2, 'CAM': 1},
'Gio': {'GK': 3, 'CM': 2, 'S': 1},
'Hol': {'CAM': 3, 'F': 2, 'SWP': 1},
'Ian': {'S': 3, 'RW': 2, 'RB': 1},
'Jon': {'F': 3, 'LW': 2, 'CB': 1},
'Kay': {'GK': 3, 'RW': 2, 'LW': 1, 'LB': 0}
}
thus defining a complete bipartite graph G = (L ∪ R, E) with:
- Vertex set L (Players) = {'Ann', 'Ben', 'Cal', 'Dan', 'Ela', 'Fae', 'Gio', 'Hol', 'Ian', 'Jon', 'Kay'}
- Vertex set R (Positions) = {'GK', 'LB', 'SWP', 'CB', 'RB', 'LW', 'CM', 'CAM', 'RW', 'F', 'S'}
- Edge set E = {e = (Player, Position) : for all Players, for all Positions}
- Weight function:
- w(Player, Position) = 3 for a first choice
- w(Player, Position) = 2 for a second choice
- w(Player, Position) = 1 for a third choice
- w(Player, Position) = 0 otherwise
Then pass the graph as an input:
hungarian_algorithm(G)
Output
Determine your desired output with an optional input. For an output listing Player - Position pairs in the maximum-weighted matching along with w(Player, Position), use the input 'list' (default):
hungarian_algorithm(G, 'list')
# -> [('Cal-CAM', 3), ('Jon-F', 3), ('Fae-CM', 3), ('Hol-SWP', 1), ('Dan-CB', 0), ('Ann-RB', 3),
# ('Gio-LB', 0), ('Ian-S', 3), ('Ela-GK', 3), ('Ben-LW', 3), ('Kay-RW', 2)]
For an output of the total weight of the maximum-weighted matching, use the input 'total':
hungarian_algorithm(G, 'total')
# -> 24
History
The algorithm was published by Harold Kuhn in 1955 paper The Hungarian Method for the Assignment Problem. Kuhn's work relied heavily on that of Hungarian mathematicians Dénes Kőnig and Jenő Egévary.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for hungarian_algorithm-0.1.5.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | af54e53208d103a09a1edbfd69c1962e9af1ba2f59dcaecd3e5d4a291afea72f |
|
MD5 | f03198cfb407580966b4b3cc9de284cc |
|
BLAKE2b-256 | 7ac91990d0d3da38a28b24bfc85252cbf06ead0bfbd3417bcd8227590ea5679d |
Hashes for hungarian_algorithm-0.1.5-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a31467d3fffbfb5864a8fb4fe59e9c9771e86b1f97e079b5fa5c94305b099af3 |
|
MD5 | 3ada72e3c6bcf208c90019347f2c33da |
|
BLAKE2b-256 | 2e86db3f0d16f73cc3c198947f4fe00854ee8c696ba8bb5b2f51fb57e226f545 |