benchaplin / hungarian-algorithm Goto Github PK
View Code? Open in Web Editor NEWPython 3 implementation of the Hungarian Algorithm
License: MIT License
Python 3 implementation of the Hungarian Algorithm
License: MIT License
Thank you for sharing the library, Could you help me fix the problem?
Traceback (most recent call last):
File "/home/wuhj/miniconda3/lib/python3.7/site-packages/hungarian_algorithm/algorithm.py", line 447, in find_matching
y = list(S_nbs - T)[0]
IndexError: list index out of range
Hi, thanks for releasing a good library.
I got an error with the graph below, can you help me?
G = {'p0': {'c0': 0.7542973970266263}, 'p2': {'c1': 0.49921363305452704}}
matching = algorithm.find_matching(G, matching_type="max", return_type="list")
The error was 'G is not bipartite', so that find_matching function always returns 'False'.
When fed an input grid where each tile is linked with it's neighbour the algorithm sometimes hangs and fails to determine an assignment. It does not consistently do this, but the odds of this happening appear higher when the graph is larger.
The following code starts hanging on my machine when n is between 4 and 8, (most often 4, but I've gotten as high as 8 by retrying).
from hungarian_algorithm import algorithm
import timeit
for n in range(2,20):
graph = {}
for i in range(n):
for j in range(n):
if (i+j)% 2 == 0:
links = {}
if i > 0:
links['node_{}_{}'.format(i-1, j)] = 1
if i < n-1:
links['node_{}_{}'.format(i+1, j)] = 1
if j > 0:
links['node_{}_{}'.format(i, j-1)] = 1
if j < n-1:
links['node_{}_{}'.format(i, j+1)] = 1
graph['node_{}_{}'.format(i, j)] = links
print(n, len(graph))
print(graph)
print(timeit.timeit(lambda: algorithm.find_matching(graph, matching_type = 'max', return_type = 'total'), number=1))
Sometimes it hangs indefinitely and sometimes it crashes with the same error as #5
Hi!
I was testing your code on randomly generated complete bipartite graphs and got the following error which seemed to be thrown by line 352 in algorithm.py.
AttributeError: 'bool' object has no attribute 'vertices'
After doing some debugging, this seems to be do to the fact that a bool
is put into the matching M
around lines 472-473.
I used the following code to generate the instance which causes the issue:
import random
from algorithm import *
# n is the number of vertices on each side
# returns a dict of dicts giving the neighborhoods of the LHS with their weights
# weights are integers chosen uniformly at random in [min_weight,max_weight]
def random_complete_bipartite(n,min_weight,max_weight):
# the vertex names are 0 -> n-1 for the LHS and n -> 2n-1 for the RHS
lhs = list(range(n))
rhs = list(range(n,2*n))
G = {}
for v in lhs:
G[v] = {}
for w in rhs:
# choose the weight randomly
weight = random.randrange(min_weight,max_weight+1)
G[v][w] = weight
return G
random.seed(500)
n = 50
min_w = 0
max_w = 100
G = random_complete_bipartite(n,min_w,max_w)
print(find_matching(G,matching_type='max', return_type='total')
Note that it seems to work fine on smaller examples with around 10-20 nodes. I discovered the issue when I started to increase the number of nodes. Let me know if you have any questions.
Thanks,
Thomas
PS: if there are any issues with random generation the test instance that I get from running the code above is here:
G = {0: {50: 59, 51: 67, 52: 74, 53: 59, 54: 32, 55: 81, 56: 96, 57: 89, 58: 48, 59: 27, 60: 13, 61: 43, 62: 73, 63: 94, 64: 11, 65: 2, 66: 25, 67: 42, 68: 29, 69: 50, 70: 37, 71: 6, 72: 96, 73: 8, 74: 41, 75: 57, 76: 79, 77: 39, 78: 47, 79: 17, 80: 62, 81: 14, 82: 24, 83: 47, 84: 68, 85: 20, 86: 47, 87: 46, 88: 42, 89: 56, 90: 23, 91: 67, 92: 10, 93: 77, 94: 0, 95: 18, 96: 98, 97: 59, 98: 63, 99: 92}, 1: {50: 23, 51: 98, 52: 76, 53: 61, 54: 84, 55: 57, 56: 70, 57: 50, 58: 22, 59: 82, 60: 73, 61: 69, 62: 57, 63: 96, 64: 35, 65: 67, 66: 94, 67: 35, 68: 82, 69: 86, 70: 78, 71: 77, 72: 7, 73: 60, 74: 100, 75: 44, 76: 34, 77: 99, 78: 43, 79: 45, 80: 90, 81: 7, 82: 13, 83: 44, 84: 90, 85: 71, 86: 33, 87: 77, 88: 59, 89: 23, 90: 68, 91: 42, 92: 89, 93: 53, 94: 5, 95: 74, 96: 46, 97: 34, 98: 2, 99: 4}, 2: {50: 3, 51: 3, 52: 3, 53: 22, 54: 83, 55: 50, 56: 77, 57: 9, 58: 89, 59: 60, 60: 30, 61: 30, 62: 89, 63: 34, 64: 78, 65: 49, 66: 36, 67: 60, 68: 59, 69: 22, 70: 74, 71: 63, 72: 70, 73: 0, 74: 0, 75: 18, 76: 83, 77: 10, 78: 79, 79: 64, 80: 96, 81: 61, 82: 14, 83: 43, 84: 43, 85: 53, 86: 90, 87: 18, 88: 37, 89: 47, 90: 1, 91: 73, 92: 82, 93: 51, 94: 61, 95: 24, 96: 88, 97: 91, 98: 6, 99: 71}, 3: {50: 95, 51: 4, 52: 65, 53: 72, 54: 69, 55: 0, 56: 100, 57: 42, 58: 92, 59: 46, 60: 45, 61: 37, 62: 49, 63: 0, 64: 7, 65: 91, 66: 79, 67: 62, 68: 54, 69: 97, 70: 79, 71: 63, 72: 71, 73: 74, 74: 79, 75: 23, 76: 85, 77: 29, 78: 44, 79: 2, 80: 34, 81: 10, 82: 11, 83: 92, 84: 6, 85: 46, 86: 62, 87: 92, 88: 89, 89: 98, 90: 7, 91: 43, 92: 27, 93: 27, 94: 81, 95: 66, 96: 22, 97: 49, 98: 95, 99: 5}, 4: {50: 35, 51: 44, 52: 43, 53: 0, 54: 83, 55: 31, 56: 33, 57: 21, 58: 13, 59: 65, 60: 63, 61: 96, 62: 71, 63: 62, 64: 87, 65: 67, 66: 52, 67: 56, 68: 76, 69: 6, 70: 77, 71: 87, 72: 47, 73: 18, 74: 40, 75: 59, 76: 11, 77: 48, 78: 33, 79: 73, 80: 25, 81: 68, 82: 5, 83: 76, 84: 53, 85: 47, 86: 62, 87: 42, 88: 46, 89: 46, 90: 44, 91: 21, 92: 45, 93: 9, 94: 70, 95: 81, 96: 50, 97: 16, 98: 75, 99: 76}, 5: {50: 75, 51: 1, 52: 71, 53: 89, 54: 61, 55: 15, 56: 63, 57: 75, 58: 87, 59: 97, 60: 18, 61: 52, 62: 19, 63: 29, 64: 11, 65: 30, 66: 71, 67: 99, 68: 4, 69: 24, 70: 84, 71: 2, 72: 29, 73: 39, 74: 62, 75: 72, 76: 53, 77: 95, 78: 30, 79: 85, 80: 73, 81: 8, 82: 35, 83: 94, 84: 6, 85: 45, 86: 24, 87: 53, 88: 11, 89: 5, 90: 16, 91: 4, 92: 81, 93: 42, 94: 30, 95: 7, 96: 96, 97: 85, 98: 77, 99: 93}, 6: {50: 2, 51: 97, 52: 10, 53: 42, 54: 63, 55: 65, 56: 67, 57: 32, 58: 41, 59: 77, 60: 5, 61: 43, 62: 65, 63: 40, 64: 42, 65: 23, 66: 65, 67: 94, 68: 97, 69: 68, 70: 93, 71: 81, 72: 43, 73: 85, 74: 2, 75: 44, 76: 67, 77: 81, 78: 37, 79: 61, 80: 30, 81: 98, 82: 3, 83: 17, 84: 79, 85: 46, 86: 28, 87: 45, 88: 57, 89: 46, 90: 60, 91: 94, 92: 10, 93: 70, 94: 15, 95: 67, 96: 18, 97: 93, 98: 34, 99: 34}, 7: {50: 14, 51: 80, 52: 5, 53: 98, 54: 94, 55: 13, 56: 21, 57: 85, 58: 66, 59: 16, 60: 14, 61: 40, 62: 97, 63: 43, 64: 26, 65: 33, 66: 67, 67: 97, 68: 27, 69: 58, 70: 85, 71: 46, 72: 64, 73: 28, 74: 61, 75: 67, 76: 99, 77: 33, 78: 38, 79: 42, 80: 4, 81: 75, 82: 48, 83: 1, 84: 39, 85: 50, 86: 81, 87: 38, 88: 31, 89: 74, 90: 100, 91: 81, 92: 91, 93: 52, 94: 34, 95: 44, 96: 50, 97: 87, 98: 36, 99: 95}, 8: {50: 89, 51: 75, 52: 61, 53: 18, 54: 19, 55: 60, 56: 51, 57: 58, 58: 92, 59: 66, 60: 57, 61: 96, 62: 86, 63: 21, 64: 35, 65: 57, 66: 52, 67: 46, 68: 10, 69: 95, 70: 16, 71: 88, 72: 45, 73: 23, 74: 64, 75: 100, 76: 28, 77: 82, 78: 33, 79: 87, 80: 82, 81: 13, 82: 83, 83: 91, 84: 88, 85: 76, 86: 45, 87: 9, 88: 68, 89: 81, 90: 28, 91: 94, 92: 55, 93: 73, 94: 21, 95: 29, 96: 32, 97: 2, 98: 50, 99: 71}, 9: {50: 53, 51: 52, 52: 44, 53: 46, 54: 4, 55: 30, 56: 11, 57: 30, 58: 79, 59: 83, 60: 41, 61: 84, 62: 11, 63: 35, 64: 78, 65: 94, 66: 21, 67: 66, 68: 3, 69: 12, 70: 69, 71: 12, 72: 54, 73: 0, 74: 46, 75: 49, 76: 5, 77: 87, 78: 90, 79: 38, 80: 82, 81: 93, 82: 56, 83: 93, 84: 82, 85: 65, 86: 90, 87: 22, 88: 26, 89: 48, 90: 97, 91: 6, 92: 5, 93: 61, 94: 16, 95: 95, 96: 69, 97: 66, 98: 4, 99: 11}, 10: {50: 26, 51: 65, 52: 67, 53: 50, 54: 43, 55: 74, 56: 98, 57: 16, 58: 96, 59: 22, 60: 71, 61: 33, 62: 6, 63: 14, 64: 77, 65: 14, 66: 61, 67: 21, 68: 12, 69: 65, 70: 29, 71: 5, 72: 53, 73: 53, 74: 82, 75: 17, 76: 22, 77: 69, 78: 61, 79: 85, 80: 23, 81: 68, 82: 85, 83: 33, 84: 92, 85: 47, 86: 10, 87: 72, 88: 3, 89: 98, 90: 21, 91: 91, 92: 37, 93: 34, 94: 89, 95: 64, 96: 91, 97: 89, 98: 26, 99: 100}, 11: {50: 41, 51: 77, 52: 30, 53: 89, 54: 58, 55: 76, 56: 29, 57: 75, 58: 89, 59: 49, 60: 42, 61: 17, 62: 8, 63: 69, 64: 41, 65: 90, 66: 11, 67: 22, 68: 76, 69: 44, 70: 78, 71: 67, 72: 88, 73: 50, 74: 96, 75: 86, 76: 70, 77: 8, 78: 4, 79: 52, 80: 25, 81: 51, 82: 43, 83: 96, 84: 45, 85: 50, 86: 48, 87: 24, 88: 71, 89: 96, 90: 59, 91: 62, 92: 14, 93: 31, 94: 38, 95: 17, 96: 94, 97: 96, 98: 87, 99: 93}, 12: {50: 52, 51: 15, 52: 83, 53: 93, 54: 77, 55: 46, 56: 44, 57: 2, 58: 92, 59: 37, 60: 53, 61: 29, 62: 60, 63: 71, 64: 98, 65: 51, 66: 39, 67: 24, 68: 76, 69: 38, 70: 77, 71: 3, 72: 65, 73: 45, 74: 86, 75: 62, 76: 63, 77: 50, 78: 86, 79: 82, 80: 20, 81: 95, 82: 3, 83: 94, 84: 83, 85: 65, 86: 95, 87: 65, 88: 93, 89: 49, 90: 58, 91: 19, 92: 74, 93: 41, 94: 52, 95: 12, 96: 50, 97: 73, 98: 46, 99: 58}, 13: {50: 82, 51: 38, 52: 78, 53: 87, 54: 97, 55: 66, 56: 0, 57: 12, 58: 24, 59: 97, 60: 40, 61: 82, 62: 55, 63: 13, 64: 16, 65: 44, 66: 8, 67: 40, 68: 0, 69: 80, 70: 83, 71: 4, 72: 24, 73: 4, 74: 63, 75: 18, 76: 51, 77: 24, 78: 11, 79: 7, 80: 78, 81: 17, 82: 76, 83: 53, 84: 71, 85: 38, 86: 22, 87: 6, 88: 27, 89: 82, 90: 11, 91: 68, 92: 82, 93: 74, 94: 30, 95: 40, 96: 24, 97: 31, 98: 18, 99: 13}, 14: {50: 18, 51: 8, 52: 40, 53: 28, 54: 51, 55: 79, 56: 69, 57: 88, 58: 48, 59: 46, 60: 36, 61: 32, 62: 12, 63: 91, 64: 58, 65: 38, 66: 29, 67: 11, 68: 92, 69: 98, 70: 35, 71: 8, 72: 67, 73: 27, 74: 75, 75: 47, 76: 2, 77: 26, 78: 52, 79: 1, 80: 26, 81: 79, 82: 63, 83: 78, 84: 84, 85: 41, 86: 30, 87: 35, 88: 66, 89: 95, 90: 75, 91: 34, 92: 6, 93: 96, 94: 42, 95: 68, 96: 41, 97: 50, 98: 8, 99: 86}, 15: {50: 15, 51: 26, 52: 89, 53: 51, 54: 0, 55: 31, 56: 25, 57: 62, 58: 18, 59: 34, 60: 61, 61: 30, 62: 24, 63: 37, 64: 29, 65: 6, 66: 56, 67: 74, 68: 65, 69: 51, 70: 70, 71: 52, 72: 91, 73: 41, 74: 56, 75: 20, 76: 98, 77: 7, 78: 20, 79: 38, 80: 37, 81: 65, 82: 11, 83: 58, 84: 35, 85: 67, 86: 66, 87: 89, 88: 77, 89: 60, 90: 88, 91: 46, 92: 25, 93: 73, 94: 92, 95: 59, 96: 97, 97: 62, 98: 58, 99: 15}, 16: {50: 75, 51: 40, 52: 43, 53: 53, 54: 26, 55: 82, 56: 10, 57: 51, 58: 52, 59: 10, 60: 21, 61: 71, 62: 47, 63: 85, 64: 2, 65: 65, 66: 49, 67: 36, 68: 53, 69: 86, 70: 88, 71: 89, 72: 91, 73: 13, 74: 57, 75: 16, 76: 97, 77: 35, 78: 79, 79: 15, 80: 69, 81: 73, 82: 19, 83: 65, 84: 95, 85: 30, 86: 39, 87: 71, 88: 97, 89: 13, 90: 54, 91: 98, 92: 48, 93: 4, 94: 63, 95: 76, 96: 75, 97: 85, 98: 95, 99: 47}, 17: {50: 57, 51: 45, 52: 34, 53: 31, 54: 88, 55: 68, 56: 48, 57: 50, 58: 74, 59: 94, 60: 71, 61: 29, 62: 57, 63: 44, 64: 73, 65: 44, 66: 63, 67: 64, 68: 32, 69: 55, 70: 17, 71: 28, 72: 21, 73: 40, 74: 25, 75: 38, 76: 45, 77: 16, 78: 78, 79: 65, 80: 90, 81: 81, 82: 14, 83: 70, 84: 98, 85: 28, 86: 90, 87: 40, 88: 78, 89: 50, 90: 74, 91: 9, 92: 57, 93: 79, 94: 68, 95: 77, 96: 47, 97: 14, 98: 33, 99: 28}, 18: {50: 91, 51: 30, 52: 19, 53: 56, 54: 25, 55: 34, 56: 77, 57: 41, 58: 44, 59: 80, 60: 6, 61: 59, 62: 55, 63: 54, 64: 5, 65: 48, 66: 60, 67: 45, 68: 42, 69: 89, 70: 41, 71: 47, 72: 63, 73: 72, 74: 17, 75: 91, 76: 22, 77: 57, 78: 42, 79: 54, 80: 50, 81: 47, 82: 51, 83: 3, 84: 29, 85: 2, 86: 53, 87: 31, 88: 33, 89: 23, 90: 10, 91: 77, 92: 75, 93: 97, 94: 69, 95: 14, 96: 66, 97: 97, 98: 74, 99: 59}, 19: {50: 6, 51: 48, 52: 37, 53: 76, 54: 62, 55: 57, 56: 98, 57: 45, 58: 50, 59: 29, 60: 60, 61: 83, 62: 88, 63: 20, 64: 87, 65: 96, 66: 15, 67: 2, 68: 58, 69: 73, 70: 60, 71: 5, 72: 38, 73: 68, 74: 18, 75: 64, 76: 12, 77: 75, 78: 23, 79: 25, 80: 34, 81: 28, 82: 81, 83: 63, 84: 2, 85: 3, 86: 51, 87: 11, 88: 42, 89: 15, 90: 32, 91: 72, 92: 98, 93: 61, 94: 84, 95: 45, 96: 35, 97: 57, 98: 23, 99: 73}, 20: {50: 37, 51: 38, 52: 78, 53: 15, 54: 29, 55: 18, 56: 28, 57: 69, 58: 86, 59: 5, 60: 82, 61: 49, 62: 11, 63: 22, 64: 48, 65: 60, 66: 97, 67: 81, 68: 79, 69: 85, 70: 40, 71: 11, 72: 48, 73: 43, 74: 82, 75: 92, 76: 54, 77: 0, 78: 68, 79: 51, 80: 57, 81: 47, 82: 74, 83: 38, 84: 23, 85: 6, 86: 86, 87: 36, 88: 8, 89: 78, 90: 43, 91: 13, 92: 95, 93: 52, 94: 38, 95: 72, 96: 86, 97: 12, 98: 89, 99: 61}, 21: {50: 18, 51: 30, 52: 7, 53: 69, 54: 17, 55: 35, 56: 27, 57: 34, 58: 10, 59: 80, 60: 5, 61: 74, 62: 12, 63: 60, 64: 30, 65: 11, 66: 26, 67: 51, 68: 63, 69: 6, 70: 84, 71: 85, 72: 6, 73: 28, 74: 34, 75: 10, 76: 19, 77: 20, 78: 82, 79: 99, 80: 54, 81: 76, 82: 61, 83: 68, 84: 82, 85: 3, 86: 43, 87: 71, 88: 60, 89: 80, 90: 48, 91: 88, 92: 48, 93: 61, 94: 11, 95: 78, 96: 44, 97: 57, 98: 19, 99: 12}, 22: {50: 0, 51: 56, 52: 92, 53: 58, 54: 22, 55: 14, 56: 18, 57: 31, 58: 39, 59: 37, 60: 44, 61: 30, 62: 33, 63: 43, 64: 98, 65: 23, 66: 73, 67: 30, 68: 34, 69: 84, 70: 5, 71: 81, 72: 44, 73: 69, 74: 59, 75: 83, 76: 66, 77: 93, 78: 84, 79: 5, 80: 28, 81: 20, 82: 59, 83: 30, 84: 86, 85: 67, 86: 24, 87: 60, 88: 42, 89: 41, 90: 5, 91: 72, 92: 53, 93: 98, 94: 62, 95: 55, 96: 57, 97: 54, 98: 52, 99: 56}, 23: {50: 46, 51: 37, 52: 78, 53: 65, 54: 80, 55: 66, 56: 32, 57: 39, 58: 94, 59: 96, 60: 65, 61: 38, 62: 24, 63: 25, 64: 48, 65: 64, 66: 15, 67: 32, 68: 30, 69: 46, 70: 11, 71: 37, 72: 9, 73: 18, 74: 36, 75: 19, 76: 41, 77: 80, 78: 42, 79: 84, 80: 45, 81: 97, 82: 62, 83: 33, 84: 28, 85: 31, 86: 64, 87: 44, 88: 23, 89: 65, 90: 32, 91: 91, 92: 51, 93: 71, 94: 78, 95: 85, 96: 14, 97: 15, 98: 59, 99: 82}, 24: {50: 28, 51: 94, 52: 83, 53: 89, 54: 95, 55: 34, 56: 46, 57: 9, 58: 41, 59: 39, 60: 15, 61: 22, 62: 69, 63: 74, 64: 53, 65: 65, 66: 79, 67: 81, 68: 66, 69: 87, 70: 76, 71: 16, 72: 94, 73: 68, 74: 24, 75: 58, 76: 72, 77: 98, 78: 50, 79: 23, 80: 44, 81: 62, 82: 37, 83: 50, 84: 90, 85: 16, 86: 32, 87: 85, 88: 59, 89: 49, 90: 98, 91: 96, 92: 82, 93: 35, 94: 65, 95: 25, 96: 44, 97: 28, 98: 63, 99: 82}, 25: {50: 66, 51: 83, 52: 99, 53: 95, 54: 72, 55: 41, 56: 50, 57: 62, 58: 14, 59: 0, 60: 2, 61: 72, 62: 66, 63: 40, 64: 99, 65: 29, 66: 87, 67: 99, 68: 28, 69: 78, 70: 6, 71: 72, 72: 11, 73: 35, 74: 38, 75: 38, 76: 35, 77: 95, 78: 74, 79: 36, 80: 39, 81: 10, 82: 15, 83: 98, 84: 58, 85: 84, 86: 88, 87: 26, 88: 39, 89: 93, 90: 81, 91: 77, 92: 21, 93: 69, 94: 93, 95: 69, 96: 46, 97: 59, 98: 36, 99: 71}, 26: {50: 11, 51: 81, 52: 45, 53: 12, 54: 49, 55: 53, 56: 48, 57: 38, 58: 1, 59: 28, 60: 72, 61: 22, 62: 4, 63: 83, 64: 36, 65: 23, 66: 75, 67: 35, 68: 18, 69: 77, 70: 74, 71: 81, 72: 18, 73: 91, 74: 50, 75: 76, 76: 57, 77: 20, 78: 91, 79: 77, 80: 54, 81: 56, 82: 92, 83: 21, 84: 17, 85: 72, 86: 34, 87: 97, 88: 10, 89: 44, 90: 23, 91: 35, 92: 1, 93: 38, 94: 79, 95: 56, 96: 6, 97: 29, 98: 55, 99: 80}, 27: {50: 31, 51: 44, 52: 75, 53: 48, 54: 82, 55: 91, 56: 47, 57: 67, 58: 3, 59: 14, 60: 88, 61: 44, 62: 59, 63: 9, 64: 71, 65: 81, 66: 86, 67: 63, 68: 22, 69: 3, 70: 80, 71: 26, 72: 86, 73: 56, 74: 43, 75: 76, 76: 51, 77: 1, 78: 1, 79: 32, 80: 18, 81: 26, 82: 42, 83: 86, 84: 77, 85: 50, 86: 88, 87: 86, 88: 59, 89: 26, 90: 83, 91: 88, 92: 75, 93: 58, 94: 55, 95: 14, 96: 21, 97: 56, 98: 34, 99: 45}, 28: {50: 60, 51: 80, 52: 16, 53: 83, 54: 28, 55: 49, 56: 46, 57: 13, 58: 38, 59: 85, 60: 42, 61: 47, 62: 91, 63: 82, 64: 3, 65: 17, 66: 27, 67: 86, 68: 42, 69: 55, 70: 81, 71: 57, 72: 7, 73: 53, 74: 82, 75: 90, 76: 14, 77: 70, 78: 85, 79: 51, 80: 37, 81: 13, 82: 12, 83: 72, 84: 79, 85: 43, 86: 49, 87: 78, 88: 24, 89: 74, 90: 48, 91: 97, 92: 44, 93: 55, 94: 24, 95: 100, 96: 30, 97: 13, 98: 13, 99: 24}, 29: {50: 64, 51: 36, 52: 12, 53: 9, 54: 100, 55: 11, 56: 73, 57: 69, 58: 4, 59: 73, 60: 78, 61: 54, 62: 26, 63: 7, 64: 68, 65: 96, 66: 19, 67: 46, 68: 21, 69: 35, 70: 28, 71: 98, 72: 74, 73: 39, 74: 42, 75: 66, 76: 4, 77: 1, 78: 98, 79: 39, 80: 52, 81: 80, 82: 65, 83: 77, 84: 3, 85: 60, 86: 86, 87: 8, 88: 66, 89: 23, 90: 12, 91: 68, 92: 69, 93: 37, 94: 25, 95: 77, 96: 77, 97: 91, 98: 12, 99: 83}, 30: {50: 72, 51: 99, 52: 9, 53: 66, 54: 99, 55: 74, 56: 52, 57: 19, 58: 9, 59: 79, 60: 79, 61: 54, 62: 61, 63: 63, 64: 18, 65: 78, 66: 8, 67: 62, 68: 80, 69: 2, 70: 93, 71: 92, 72: 92, 73: 72, 74: 34, 75: 42, 76: 39, 77: 39, 78: 94, 79: 32, 80: 52, 81: 70, 82: 54, 83: 67, 84: 53, 85: 10, 86: 1, 87: 48, 88: 61, 89: 99, 90: 79, 91: 92, 92: 78, 93: 44, 94: 52, 95: 19, 96: 73, 97: 72, 98: 83, 99: 19}, 31: {50: 5, 51: 16, 52: 64, 53: 77, 54: 42, 55: 86, 56: 95, 57: 39, 58: 51, 59: 80, 60: 22, 61: 98, 62: 73, 63: 35, 64: 40, 65: 74, 66: 93, 67: 39, 68: 47, 69: 19, 70: 75, 71: 98, 72: 39, 73: 89, 74: 20, 75: 37, 76: 37, 77: 96, 78: 85, 79: 50, 80: 57, 81: 47, 82: 3, 83: 44, 84: 13, 85: 43, 86: 71, 87: 44, 88: 47, 89: 78, 90: 84, 91: 60, 92: 34, 93: 22, 94: 44, 95: 67, 96: 72, 97: 4, 98: 90, 99: 14}, 32: {50: 44, 51: 65, 52: 70, 53: 1, 54: 98, 55: 25, 56: 68, 57: 34, 58: 91, 59: 41, 60: 3, 61: 61, 62: 64, 63: 25, 64: 39, 65: 95, 66: 74, 67: 54, 68: 57, 69: 77, 70: 13, 71: 96, 72: 54, 73: 13, 74: 20, 75: 70, 76: 27, 77: 72, 78: 14, 79: 10, 80: 99, 81: 60, 82: 47, 83: 93, 84: 96, 85: 19, 86: 23, 87: 65, 88: 85, 89: 66, 90: 68, 91: 39, 92: 27, 93: 44, 94: 35, 95: 76, 96: 34, 97: 98, 98: 69, 99: 26}, 33: {50: 94, 51: 85, 52: 58, 53: 86, 54: 69, 55: 28, 56: 51, 57: 95, 58: 66, 59: 79, 60: 81, 61: 35, 62: 79, 63: 43, 64: 91, 65: 64, 66: 37, 67: 75, 68: 63, 69: 39, 70: 94, 71: 67, 72: 3, 73: 97, 74: 97, 75: 43, 76: 78, 77: 42, 78: 86, 79: 97, 80: 49, 81: 100, 82: 84, 83: 83, 84: 66, 85: 74, 86: 54, 87: 72, 88: 93, 89: 76, 90: 76, 91: 82, 92: 55, 93: 54, 94: 23, 95: 76, 96: 3, 97: 88, 98: 1, 99: 26}, 34: {50: 67, 51: 70, 52: 10, 53: 12, 54: 77, 55: 1, 56: 18, 57: 47, 58: 96, 59: 29, 60: 89, 61: 33, 62: 0, 63: 78, 64: 69, 65: 15, 66: 2, 67: 68, 68: 93, 69: 11, 70: 36, 71: 62, 72: 26, 73: 9, 74: 57, 75: 15, 76: 14, 77: 28, 78: 67, 79: 20, 80: 30, 81: 28, 82: 11, 83: 48, 84: 91, 85: 7, 86: 68, 87: 85, 88: 39, 89: 73, 90: 7, 91: 24, 92: 93, 93: 68, 94: 41, 95: 8, 96: 29, 97: 48, 98: 22, 99: 28}, 35: {50: 3, 51: 96, 52: 78, 53: 91, 54: 13, 55: 86, 56: 29, 57: 62, 58: 95, 59: 15, 60: 73, 61: 36, 62: 42, 63: 0, 64: 58, 65: 58, 66: 20, 67: 2, 68: 39, 69: 14, 70: 53, 71: 100, 72: 99, 73: 94, 74: 74, 75: 34, 76: 100, 77: 11, 78: 2, 79: 55, 80: 74, 81: 70, 82: 53, 83: 6, 84: 100, 85: 28, 86: 54, 87: 63, 88: 16, 89: 10, 90: 4, 91: 19, 92: 4, 93: 74, 94: 4, 95: 72, 96: 91, 97: 16, 98: 66, 99: 51}, 36: {50: 58, 51: 91, 52: 90, 53: 52, 54: 74, 55: 85, 56: 6, 57: 91, 58: 44, 59: 51, 60: 38, 61: 10, 62: 34, 63: 41, 64: 85, 65: 41, 66: 68, 67: 2, 68: 31, 69: 80, 70: 86, 71: 27, 72: 14, 73: 37, 74: 12, 75: 98, 76: 69, 77: 38, 78: 20, 79: 90, 80: 13, 81: 7, 82: 66, 83: 33, 84: 90, 85: 4, 86: 28, 87: 7, 88: 14, 89: 63, 90: 35, 91: 69, 92: 68, 93: 63, 94: 21, 95: 24, 96: 4, 97: 48, 98: 23, 99: 7}, 37: {50: 36, 51: 18, 52: 16, 53: 23, 54: 67, 55: 30, 56: 25, 57: 70, 58: 2, 59: 31, 60: 44, 61: 18, 62: 59, 63: 41, 64: 55, 65: 71, 66: 34, 67: 77, 68: 34, 69: 50, 70: 86, 71: 37, 72: 65, 73: 23, 74: 3, 75: 54, 76: 57, 77: 56, 78: 25, 79: 35, 80: 32, 81: 5, 82: 62, 83: 11, 84: 40, 85: 42, 86: 71, 87: 20, 88: 32, 89: 68, 90: 87, 91: 83, 92: 16, 93: 6, 94: 15, 95: 78, 96: 84, 97: 85, 98: 19, 99: 77}, 38: {50: 44, 51: 73, 52: 78, 53: 13, 54: 57, 55: 11, 56: 96, 57: 40, 58: 93, 59: 22, 60: 36, 61: 48, 62: 19, 63: 86, 64: 56, 65: 77, 66: 93, 67: 79, 68: 48, 69: 13, 70: 100, 71: 40, 72: 51, 73: 30, 74: 63, 75: 39, 76: 92, 77: 16, 78: 91, 79: 90, 80: 38, 81: 69, 82: 6, 83: 72, 84: 66, 85: 100, 86: 93, 87: 63, 88: 95, 89: 72, 90: 93, 91: 10, 92: 98, 93: 80, 94: 96, 95: 34, 96: 78, 97: 29, 98: 33, 99: 8}, 39: {50: 77, 51: 100, 52: 94, 53: 100, 54: 89, 55: 70, 56: 62, 57: 41, 58: 12, 59: 25, 60: 13, 61: 48, 62: 6, 63: 62, 64: 25, 65: 98, 66: 2, 67: 55, 68: 12, 69: 37, 70: 49, 71: 85, 72: 58, 73: 23, 74: 21, 75: 64, 76: 96, 77: 58, 78: 57, 79: 4, 80: 91, 81: 76, 82: 11, 83: 48, 84: 8, 85: 32, 86: 48, 87: 80, 88: 53, 89: 98, 90: 7, 91: 51, 92: 96, 93: 98, 94: 7, 95: 77, 96: 98, 97: 50, 98: 6, 99: 63}, 40: {50: 96, 51: 55, 52: 38, 53: 99, 54: 92, 55: 2, 56: 12, 57: 57, 58: 93, 59: 52, 60: 16, 61: 68, 62: 85, 63: 67, 64: 42, 65: 12, 66: 95, 67: 87, 68: 0, 69: 71, 70: 0, 71: 72, 72: 54, 73: 58, 74: 52, 75: 69, 76: 76, 77: 16, 78: 76, 79: 95, 80: 24, 81: 91, 82: 42, 83: 92, 84: 52, 85: 13, 86: 66, 87: 72, 88: 34, 89: 29, 90: 57, 91: 42, 92: 100, 93: 83, 94: 34, 95: 30, 96: 53, 97: 32, 98: 76, 99: 88}, 41: {50: 100, 51: 22, 52: 37, 53: 33, 54: 15, 55: 91, 56: 41, 57: 55, 58: 72, 59: 65, 60: 29, 61: 47, 62: 60, 63: 92, 64: 65, 65: 35, 66: 29, 67: 100, 68: 41, 69: 71, 70: 16, 71: 13, 72: 23, 73: 28, 74: 23, 75: 14, 76: 42, 77: 32, 78: 10, 79: 93, 80: 27, 81: 11, 82: 37, 83: 68, 84: 82, 85: 59, 86: 68, 87: 85, 88: 69, 89: 51, 90: 21, 91: 63, 92: 29, 93: 38, 94: 25, 95: 20, 96: 4, 97: 75, 98: 84, 99: 33}, 42: {50: 74, 51: 42, 52: 96, 53: 53, 54: 28, 55: 4, 56: 50, 57: 66, 58: 75, 59: 26, 60: 87, 61: 4, 62: 82, 63: 70, 64: 8, 65: 47, 66: 59, 67: 74, 68: 26, 69: 76, 70: 50, 71: 48, 72: 6, 73: 18, 74: 60, 75: 30, 76: 37, 77: 64, 78: 76, 79: 53, 80: 31, 81: 71, 82: 15, 83: 13, 84: 67, 85: 50, 86: 92, 87: 29, 88: 32, 89: 47, 90: 51, 91: 24, 92: 93, 93: 35, 94: 49, 95: 59, 96: 74, 97: 67, 98: 18, 99: 36}, 43: {50: 17, 51: 0, 52: 31, 53: 63, 54: 70, 55: 47, 56: 74, 57: 74, 58: 97, 59: 53, 60: 89, 61: 52, 62: 12, 63: 31, 64: 63, 65: 86, 66: 21, 67: 98, 68: 2, 69: 20, 70: 60, 71: 25, 72: 92, 73: 5, 74: 81, 75: 74, 76: 76, 77: 68, 78: 85, 79: 86, 80: 25, 81: 78, 82: 65, 83: 13, 84: 35, 85: 31, 86: 24, 87: 11, 88: 96, 89: 32, 90: 85, 91: 6, 92: 32, 93: 13, 94: 31, 95: 32, 96: 92, 97: 81, 98: 44, 99: 81}, 44: {50: 98, 51: 19, 52: 72, 53: 32, 54: 57, 55: 86, 56: 19, 57: 5, 58: 38, 59: 49, 60: 27, 61: 50, 62: 32, 63: 56, 64: 49, 65: 37, 66: 71, 67: 45, 68: 24, 69: 84, 70: 26, 71: 30, 72: 32, 73: 45, 74: 45, 75: 0, 76: 27, 77: 58, 78: 18, 79: 18, 80: 50, 81: 46, 82: 50, 83: 63, 84: 46, 85: 3, 86: 82, 87: 5, 88: 1, 89: 40, 90: 53, 91: 57, 92: 5, 93: 2, 94: 98, 95: 50, 96: 81, 97: 43, 98: 11, 99: 78}, 45: {50: 19, 51: 81, 52: 18, 53: 10, 54: 57, 55: 53, 56: 80, 57: 71, 58: 3, 59: 92, 60: 93, 61: 77, 62: 87, 63: 20, 64: 77, 65: 33, 66: 58, 67: 1, 68: 25, 69: 91, 70: 7, 71: 44, 72: 6, 73: 0, 74: 20, 75: 78, 76: 79, 77: 88, 78: 15, 79: 1, 80: 32, 81: 2, 82: 98, 83: 73, 84: 83, 85: 0, 86: 56, 87: 14, 88: 14, 89: 66, 90: 76, 91: 18, 92: 60, 93: 1, 94: 62, 95: 77, 96: 88, 97: 59, 98: 16, 99: 48}, 46: {50: 35, 51: 58, 52: 30, 53: 46, 54: 38, 55: 76, 56: 33, 57: 31, 58: 11, 59: 87, 60: 65, 61: 51, 62: 1, 63: 20, 64: 84, 65: 80, 66: 70, 67: 21, 68: 93, 69: 45, 70: 83, 71: 52, 72: 28, 73: 74, 74: 28, 75: 37, 76: 93, 77: 90, 78: 43, 79: 71, 80: 74, 81: 33, 82: 60, 83: 56, 84: 67, 85: 55, 86: 82, 87: 49, 88: 29, 89: 97, 90: 67, 91: 73, 92: 2, 93: 39, 94: 58, 95: 35, 96: 40, 97: 17, 98: 9, 99: 54}, 47: {50: 59, 51: 69, 52: 40, 53: 91, 54: 29, 55: 95, 56: 93, 57: 5, 58: 31, 59: 52, 60: 31, 61: 78, 62: 10, 63: 13, 64: 65, 65: 38, 66: 37, 67: 41, 68: 95, 69: 23, 70: 58, 71: 26, 72: 41, 73: 75, 74: 27, 75: 16, 76: 28, 77: 76, 78: 63, 79: 70, 80: 5, 81: 42, 82: 16, 83: 50, 84: 8, 85: 0, 86: 10, 87: 63, 88: 39, 89: 7, 90: 42, 91: 66, 92: 98, 93: 6, 94: 51, 95: 69, 96: 47, 97: 77, 98: 83, 99: 76}, 48: {50: 66, 51: 46, 52: 13, 53: 49, 54: 45, 55: 100, 56: 21, 57: 77, 58: 4, 59: 88, 60: 62, 61: 93, 62: 97, 63: 95, 64: 67, 65: 99, 66: 77, 67: 97, 68: 19, 69: 98, 70: 83, 71: 12, 72: 85, 73: 3, 74: 60, 75: 47, 76: 66, 77: 22, 78: 67, 79: 98, 80: 20, 81: 15, 82: 3, 83: 35, 84: 97, 85: 66, 86: 39, 87: 6, 88: 44, 89: 15, 90: 20, 91: 87, 92: 39, 93: 27, 94: 43, 95: 7, 96: 94, 97: 82, 98: 56, 99: 96}, 49: {50: 40, 51: 5, 52: 80, 53: 4, 54: 6, 55: 9, 56: 50, 57: 49, 58: 39, 59: 29, 60: 52, 61: 74, 62: 22, 63: 38, 64: 15, 65: 38, 66: 33, 67: 32, 68: 6, 69: 55, 70: 100, 71: 100, 72: 13, 73: 55, 74: 22, 75: 23, 76: 61, 77: 63, 78: 62, 79: 67, 80: 65, 81: 94, 82: 47, 83: 82, 84: 24, 85: 68, 86: 86, 87: 61, 88: 85, 89: 59, 90: 65, 91: 100, 92: 8, 93: 18, 94: 21, 95: 70, 96: 76, 97: 99, 98: 60, 99: 3}} ```
First, thank you for this library
when i run the find_matching method with the following bipartite graph it returns a value of False. Is there something wrong with the dictionary I'm using or something written into the algorithm that would make it return this value? Thank you
{'0': {'0': 0.0, '1': 51.61395, '2': 127.12199, '3': 364.85751, '4': 451.00998, '5': 516.0, '6': 572.00087, '7': 668.71892, '8': 768.21091, '9': 813.13836, '10': 838.46765, '11': 600.14082, '12': 905.92825, '13': 185.06485, '14': 240.86926, '15': 707.59452, '16': 110.05908, '17': 473.51135, '18': 83.81527, '19': 312.00641},
'1': {'0': 64.19502, '1': 33.30165, '2': 64.2573, '3': 300.66593, '4': 387.00517, '5': 452.02765, '6': 508.03543, '7': 604.55934, '8': 704.12002, '9': 749.06675, '10': 774.34166, '11': 536.0597, '12': 841.77016, '13': 122.06556, '14': 177.12425, '15': 643.44774, '16': 57.42822, '17': 409.35315, '18': 44.18144, '19': 248.01814},
'2': {'0': 143.03147, '1': 104.54664, '2': 31.40064, '3': 222.09232, '4': 308.0, '5': 373.01206, '6': 429.01865, '7': 525.74614, '8': 625.17997, '9': 670.10745, '10': 695.44949, '11': 457.1094, '12': 762.94692, '13': 54.48853, '14': 102.15674, '15': 564.59897, '16': 67.20863, '17': 330.54652, '18': 87.98295, '19': 169.00296},
'3': {'0': 393.0, '1': 352.27972, '2': 270.45332, '3': 38.28838, '4': 58.07753, '5': 123.0, '6': 179.00279, '7': 276.74176, '8': 375.43175, '9': 420.26777, '10': 445.88003, '11': 207.40781, '12': 513.63898, '13': 217.29703, '14': 161.8178, '15': 315.33633, '16': 300.53286, '17': 82.96987, '18': 328.67309, '19': 81.02469},
'4': {'0': 486.01646, '1': 445.2999, '2': 363.41161, '3': 125.39936, '4': 35.69314, '5': 30.26549, '6': 86.05231, '7': 185.33483, '8': 282.85685, '9': 327.55152, '10': 353.45155, '11': 115.26057, '12': 421.40954, '13': 309.58844, '14': 253.39692, '15': 223.45022, '16': 393.01018, '17': 29.06888, '18': 421.34665, '19': 174.10342},
'5': {'0': 516.0, '1': 474.94842, '2': 392.99873, '3': 154.0422, '4': 65.06919, '5': 0.0, '6': 56.00893, '7': 155.12898, '8': 252.64204, '9': 297.37855, '10': 323.2151, '11': 85.0, '12': 391.1547, '13': 338.74031, '14': 282.29417, '15': 193.18903, '16': 422.2144, '17': 48.30114, '18': 450.67172, '19': 204.0098},
'6': {'0': 572.00087, '1': 530.90583, '2': 448.93763, '3': 209.6187, '4': 121.0661, '5': 56.00893, '6': 0.0, '7': 101.19289, '8': 196.91876, '9': 241.53054, '10': 267.57616, '11': 31.30495, '12': 335.6382, '13': 394.46166, '14': 337.8772, '15': 138.29317, '16': 477.9477, '17': 101.63661, '18': 506.47409, '19': 260.01731},
'7': {'0': 689.01161, '1': 647.5222, '2': 565.5095, '3': 325.67775, '4': 238.0021, '5': 173.04624, '6': 117.10679, '7': 34.20526, '8': 80.23092, '9': 124.48695, '10': 150.92051, '11': 89.4539, '12': 219.14607, '13': 510.49192, '14': 453.6794, '15': 30.80584, '16': 593.94276, '17': 216.7487, '18': 622.6283, '19': 377.00531},
'8': {'0': 791.01011, '1': 749.7713, '2': 667.76717, '3': 427.98364, '4': 340.07205, '5': 275.02909, '6': 219.02055, '7': 127.88276, '8': 31.82766, '9': 29.06888, '10': 56.85948, '11': 191.75505, '12': 122.56019, '13': 612.80503, '14': 555.99011, '15': 90.24965, '16': 696.2557, '17': 319.06112, '18': 724.94, '19': 479.03758},
'9': {'0': 835.00958, '1': 793.72854, '2': 711.71975, '3': 471.89194, '4': 384.0638, '5': 319.02508, '6': 263.01711, '7': 170.62825, '8': 70.5195, '9': 29.06888, '10': 32.14032, '11': 235.61409, '12': 83.21658, '13': 656.68409, '14': 599.84415, '15': 132.18548, '16': 740.12161, '17': 362.9325, '18': 768.82898, '19': 523.03442},
'10': {'0': 860.00233, '1': 818.47908, '2': 736.4591, '3': 496.53298, '4': 409.00122, '5': 344.00581, '6': 288.01562, '7': 194.17775, '8': 93.38094, '9': 48.76474, '10': 34.05877, '11': 260.23259, '12': 59.5483, '13': 681.23491, '14': 624.34766, '15': 155.36409, '16': 764.63651, '17': 387.51645, '18': 793.39335, '19': 548.0},
'11': {'0': 600.14082, '1': 558.2589, '2': 476.23629, '3': 236.30489, '4': 149.33519, '5': 85.0, '6': 31.30495, '7': 70.34202, '8': 168.07439, '9': 213.00939, '10': 238.47222, '11': 0.0, '12': 306.28255, '13': 421.07007, '14': 364.23756, '15': 108.18965, '16': 504.50966, '17': 127.3185, '18': 533.21665, '19': 288.20999},
'12': {'0': 929.12109, '1': 887.12682, '2': 805.10496, '3': 565.08849, '4': 478.1506, '5': 413.27231, '6': 357.35836, '7': 261.48996, '8': 161.02795, '9': 116.0, '10': 91.92388, '11': 329.00608, '12': 35.38361, '13': 749.52318, '14': 692.56624, '15': 222.441, '16': 832.82231, '17': 456.05372, '18': 861.67105, '19': 617.13694},
'13': {'0': 200.99751, '1': 158.31614, '2': 76.41989, '3': 164.0762, '4': 251.57504, '5': 316.63228, '6': 372.59227, '7': 468.12926, '8': 568.00352, '9': 613.02039, '10': 638.05015, '11': 400.06125, '12': 705.3127, '13': 30.4795, '14': 43.56604, '15': 507.07988, '16': 107.85639, '17': 273.00733, '18': 135.14807, '19': 113.43721},
'14': {'0': 257.56164, '1': 215.39266, '2': 133.45411, '3': 107.29865, '4': 194.5045, '5': 259.55732, '6': 315.51387, '7': 411.23837, '8': 511.00098, '9': 556.0036, '10': 581.10412, '11': 343.02332, '12': 648.44429, '13': 81.27115, '14': 32.80244, '15': 450.15997, '16': 163.78339, '17': 216.05786, '18': 191.68985, '19': 57.00877},
'15': {'0': 707.59452, '1': 665.00075, '2': 583.00086, '3': 343.02332, '4': 257.31693, '5': 193.18903, '6': 138.29317, '7': 39.05125, '8': 61.98387, '9': 106.92053, '10': 131.00382, '11': 108.18965, '12': 198.3633, '13': 527.18593, '14': 470.20846, '15': 0.0, '16': 610.43345, '17': 234.10468, '18': 639.31291, '19': 395.92171},
'16': {'0': 119.85408, '1': 75.10659, '2': 7.28011, '3': 247.00202, '4': 334.79098, '5': 399.84622, '6': 455.80039, '7': 551.02269, '8': 651.04915, '9': 696.08692, '10': 721.00277, '11': 483.17492, '12': 788.14275, '13': 65.25335, '14': 121.19818, '15': 590.00763, '16': 32.80244, '17': 356.02247, '18': 54.12947, '19': 196.47137},
'17': {'0': 473.51135, '1': 431.07424, '2': 349.05157, '3': 109.04128, '4': 29.06888, '5': 48.30114, '6': 101.63661, '7': 195.20758, '8': 295.02712, '9': 340.07205, '10': 365.04931, '11': 127.3185, '12': 432.41762, '13': 293.7516, '14': 236.93248, '15': 234.10468, '16': 377.19491, '17': 0.0, '18': 405.899, '19': 162.23748},
'18': {'0': 90.24965, '1': 45.39824, '2': 37.21559, '3': 277.00181, '4': 364.60527, '5': 429.6708, '6': 485.6439, '7': 581.04217, '8': 681.02643, '9': 726.05578, '10': 751.01065, '11': 513.11792, '12': 818.17663, '13': 94.92102, '14': 151.19854, '15': 620.02016, '16': 29.73214, '17': 386.00518, '18': 31.40064, '19': 226.073},
'19': {'0': 336.25288, '1': 293.00171, '2': 211.00237, '3': 29.27456, '4': 118.87809, '5': 183.30848, '6': 238.89119, '7': 333.00601, '8': 433.1397, '9': 478.20498, '10': 503.00099, '11': 265.48258, '12': 570.1263, '13': 155.63097, '14': 98.99495, '15': 372.0, '16': 239.10876, '17': 138.17742, '18': 267.74802, '19': 35.4683}}
Hi!
I was testing your code on randomly generated complete bipartite graphs and got the following error which seemed to be thrown by line 352 in algorithm.py.
AttributeError: 'bool' object has no attribute 'vertices'
After doing some debugging, this seems to be do to the fact that a bool
is put into the matching M
around lines 472-473.
I used the following code to generate the instance which causes the issue:
import random
from algorithm import *
# n is the number of vertices on each side
# returns a dict of dicts giving the neighborhoods of the LHS with their weights
# weights are integers chosen uniformly at random in [min_weight,max_weight]
def random_complete_bipartite(n,min_weight,max_weight):
# the vertex names are 0 -> n-1 for the LHS and n -> 2n-1 for the RHS
lhs = list(range(n))
rhs = list(range(n,2*n))
G = {}
for v in lhs:
G[v] = {}
for w in rhs:
# choose the weight randomly
weight = random.randrange(min_weight,max_weight+1)
G[v][w] = weight
return G
random.seed(500)
n = 50
min_w = 0
max_w = 100
G = random_complete_bipartite(n,min_w,max_w)
print(find_matching(G,matching_type='max', return_type='total')
Note that it seems to work fine on smaller examples with around 10-20 nodes. I discovered the issue when I started to increase the number of nodes. Let me know if you have any questions.
Thanks,
Thomas
PS: if there are any issues with random generation the test instance that I get from running the code above is here:
G = {0: {50: 59, 51: 67, 52: 74, 53: 59, 54: 32, 55: 81, 56: 96, 57: 89, 58: 48, 59: 27, 60: 13, 61: 43, 62: 73, 63: 94, 64: 11, 65: 2, 66: 25, 67: 42, 68: 29, 69: 50, 70: 37, 71: 6, 72: 96, 73: 8, 74: 41, 75: 57, 76: 79, 77: 39, 78: 47, 79: 17, 80: 62, 81: 14, 82: 24, 83: 47, 84: 68, 85: 20, 86: 47, 87: 46, 88: 42, 89: 56, 90: 23, 91: 67, 92: 10, 93: 77, 94: 0, 95: 18, 96: 98, 97: 59, 98: 63, 99: 92}, 1: {50: 23, 51: 98, 52: 76, 53: 61, 54: 84, 55: 57, 56: 70, 57: 50, 58: 22, 59: 82, 60: 73, 61: 69, 62: 57, 63: 96, 64: 35, 65: 67, 66: 94, 67: 35, 68: 82, 69: 86, 70: 78, 71: 77, 72: 7, 73: 60, 74: 100, 75: 44, 76: 34, 77: 99, 78: 43, 79: 45, 80: 90, 81: 7, 82: 13, 83: 44, 84: 90, 85: 71, 86: 33, 87: 77, 88: 59, 89: 23, 90: 68, 91: 42, 92: 89, 93: 53, 94: 5, 95: 74, 96: 46, 97: 34, 98: 2, 99: 4}, 2: {50: 3, 51: 3, 52: 3, 53: 22, 54: 83, 55: 50, 56: 77, 57: 9, 58: 89, 59: 60, 60: 30, 61: 30, 62: 89, 63: 34, 64: 78, 65: 49, 66: 36, 67: 60, 68: 59, 69: 22, 70: 74, 71: 63, 72: 70, 73: 0, 74: 0, 75: 18, 76: 83, 77: 10, 78: 79, 79: 64, 80: 96, 81: 61, 82: 14, 83: 43, 84: 43, 85: 53, 86: 90, 87: 18, 88: 37, 89: 47, 90: 1, 91: 73, 92: 82, 93: 51, 94: 61, 95: 24, 96: 88, 97: 91, 98: 6, 99: 71}, 3: {50: 95, 51: 4, 52: 65, 53: 72, 54: 69, 55: 0, 56: 100, 57: 42, 58: 92, 59: 46, 60: 45, 61: 37, 62: 49, 63: 0, 64: 7, 65: 91, 66: 79, 67: 62, 68: 54, 69: 97, 70: 79, 71: 63, 72: 71, 73: 74, 74: 79, 75: 23, 76: 85, 77: 29, 78: 44, 79: 2, 80: 34, 81: 10, 82: 11, 83: 92, 84: 6, 85: 46, 86: 62, 87: 92, 88: 89, 89: 98, 90: 7, 91: 43, 92: 27, 93: 27, 94: 81, 95: 66, 96: 22, 97: 49, 98: 95, 99: 5}, 4: {50: 35, 51: 44, 52: 43, 53: 0, 54: 83, 55: 31, 56: 33, 57: 21, 58: 13, 59: 65, 60: 63, 61: 96, 62: 71, 63: 62, 64: 87, 65: 67, 66: 52, 67: 56, 68: 76, 69: 6, 70: 77, 71: 87, 72: 47, 73: 18, 74: 40, 75: 59, 76: 11, 77: 48, 78: 33, 79: 73, 80: 25, 81: 68, 82: 5, 83: 76, 84: 53, 85: 47, 86: 62, 87: 42, 88: 46, 89: 46, 90: 44, 91: 21, 92: 45, 93: 9, 94: 70, 95: 81, 96: 50, 97: 16, 98: 75, 99: 76}, 5: {50: 75, 51: 1, 52: 71, 53: 89, 54: 61, 55: 15, 56: 63, 57: 75, 58: 87, 59: 97, 60: 18, 61: 52, 62: 19, 63: 29, 64: 11, 65: 30, 66: 71, 67: 99, 68: 4, 69: 24, 70: 84, 71: 2, 72: 29, 73: 39, 74: 62, 75: 72, 76: 53, 77: 95, 78: 30, 79: 85, 80: 73, 81: 8, 82: 35, 83: 94, 84: 6, 85: 45, 86: 24, 87: 53, 88: 11, 89: 5, 90: 16, 91: 4, 92: 81, 93: 42, 94: 30, 95: 7, 96: 96, 97: 85, 98: 77, 99: 93}, 6: {50: 2, 51: 97, 52: 10, 53: 42, 54: 63, 55: 65, 56: 67, 57: 32, 58: 41, 59: 77, 60: 5, 61: 43, 62: 65, 63: 40, 64: 42, 65: 23, 66: 65, 67: 94, 68: 97, 69: 68, 70: 93, 71: 81, 72: 43, 73: 85, 74: 2, 75: 44, 76: 67, 77: 81, 78: 37, 79: 61, 80: 30, 81: 98, 82: 3, 83: 17, 84: 79, 85: 46, 86: 28, 87: 45, 88: 57, 89: 46, 90: 60, 91: 94, 92: 10, 93: 70, 94: 15, 95: 67, 96: 18, 97: 93, 98: 34, 99: 34}, 7: {50: 14, 51: 80, 52: 5, 53: 98, 54: 94, 55: 13, 56: 21, 57: 85, 58: 66, 59: 16, 60: 14, 61: 40, 62: 97, 63: 43, 64: 26, 65: 33, 66: 67, 67: 97, 68: 27, 69: 58, 70: 85, 71: 46, 72: 64, 73: 28, 74: 61, 75: 67, 76: 99, 77: 33, 78: 38, 79: 42, 80: 4, 81: 75, 82: 48, 83: 1, 84: 39, 85: 50, 86: 81, 87: 38, 88: 31, 89: 74, 90: 100, 91: 81, 92: 91, 93: 52, 94: 34, 95: 44, 96: 50, 97: 87, 98: 36, 99: 95}, 8: {50: 89, 51: 75, 52: 61, 53: 18, 54: 19, 55: 60, 56: 51, 57: 58, 58: 92, 59: 66, 60: 57, 61: 96, 62: 86, 63: 21, 64: 35, 65: 57, 66: 52, 67: 46, 68: 10, 69: 95, 70: 16, 71: 88, 72: 45, 73: 23, 74: 64, 75: 100, 76: 28, 77: 82, 78: 33, 79: 87, 80: 82, 81: 13, 82: 83, 83: 91, 84: 88, 85: 76, 86: 45, 87: 9, 88: 68, 89: 81, 90: 28, 91: 94, 92: 55, 93: 73, 94: 21, 95: 29, 96: 32, 97: 2, 98: 50, 99: 71}, 9: {50: 53, 51: 52, 52: 44, 53: 46, 54: 4, 55: 30, 56: 11, 57: 30, 58: 79, 59: 83, 60: 41, 61: 84, 62: 11, 63: 35, 64: 78, 65: 94, 66: 21, 67: 66, 68: 3, 69: 12, 70: 69, 71: 12, 72: 54, 73: 0, 74: 46, 75: 49, 76: 5, 77: 87, 78: 90, 79: 38, 80: 82, 81: 93, 82: 56, 83: 93, 84: 82, 85: 65, 86: 90, 87: 22, 88: 26, 89: 48, 90: 97, 91: 6, 92: 5, 93: 61, 94: 16, 95: 95, 96: 69, 97: 66, 98: 4, 99: 11}, 10: {50: 26, 51: 65, 52: 67, 53: 50, 54: 43, 55: 74, 56: 98, 57: 16, 58: 96, 59: 22, 60: 71, 61: 33, 62: 6, 63: 14, 64: 77, 65: 14, 66: 61, 67: 21, 68: 12, 69: 65, 70: 29, 71: 5, 72: 53, 73: 53, 74: 82, 75: 17, 76: 22, 77: 69, 78: 61, 79: 85, 80: 23, 81: 68, 82: 85, 83: 33, 84: 92, 85: 47, 86: 10, 87: 72, 88: 3, 89: 98, 90: 21, 91: 91, 92: 37, 93: 34, 94: 89, 95: 64, 96: 91, 97: 89, 98: 26, 99: 100}, 11: {50: 41, 51: 77, 52: 30, 53: 89, 54: 58, 55: 76, 56: 29, 57: 75, 58: 89, 59: 49, 60: 42, 61: 17, 62: 8, 63: 69, 64: 41, 65: 90, 66: 11, 67: 22, 68: 76, 69: 44, 70: 78, 71: 67, 72: 88, 73: 50, 74: 96, 75: 86, 76: 70, 77: 8, 78: 4, 79: 52, 80: 25, 81: 51, 82: 43, 83: 96, 84: 45, 85: 50, 86: 48, 87: 24, 88: 71, 89: 96, 90: 59, 91: 62, 92: 14, 93: 31, 94: 38, 95: 17, 96: 94, 97: 96, 98: 87, 99: 93}, 12: {50: 52, 51: 15, 52: 83, 53: 93, 54: 77, 55: 46, 56: 44, 57: 2, 58: 92, 59: 37, 60: 53, 61: 29, 62: 60, 63: 71, 64: 98, 65: 51, 66: 39, 67: 24, 68: 76, 69: 38, 70: 77, 71: 3, 72: 65, 73: 45, 74: 86, 75: 62, 76: 63, 77: 50, 78: 86, 79: 82, 80: 20, 81: 95, 82: 3, 83: 94, 84: 83, 85: 65, 86: 95, 87: 65, 88: 93, 89: 49, 90: 58, 91: 19, 92: 74, 93: 41, 94: 52, 95: 12, 96: 50, 97: 73, 98: 46, 99: 58}, 13: {50: 82, 51: 38, 52: 78, 53: 87, 54: 97, 55: 66, 56: 0, 57: 12, 58: 24, 59: 97, 60: 40, 61: 82, 62: 55, 63: 13, 64: 16, 65: 44, 66: 8, 67: 40, 68: 0, 69: 80, 70: 83, 71: 4, 72: 24, 73: 4, 74: 63, 75: 18, 76: 51, 77: 24, 78: 11, 79: 7, 80: 78, 81: 17, 82: 76, 83: 53, 84: 71, 85: 38, 86: 22, 87: 6, 88: 27, 89: 82, 90: 11, 91: 68, 92: 82, 93: 74, 94: 30, 95: 40, 96: 24, 97: 31, 98: 18, 99: 13}, 14: {50: 18, 51: 8, 52: 40, 53: 28, 54: 51, 55: 79, 56: 69, 57: 88, 58: 48, 59: 46, 60: 36, 61: 32, 62: 12, 63: 91, 64: 58, 65: 38, 66: 29, 67: 11, 68: 92, 69: 98, 70: 35, 71: 8, 72: 67, 73: 27, 74: 75, 75: 47, 76: 2, 77: 26, 78: 52, 79: 1, 80: 26, 81: 79, 82: 63, 83: 78, 84: 84, 85: 41, 86: 30, 87: 35, 88: 66, 89: 95, 90: 75, 91: 34, 92: 6, 93: 96, 94: 42, 95: 68, 96: 41, 97: 50, 98: 8, 99: 86}, 15: {50: 15, 51: 26, 52: 89, 53: 51, 54: 0, 55: 31, 56: 25, 57: 62, 58: 18, 59: 34, 60: 61, 61: 30, 62: 24, 63: 37, 64: 29, 65: 6, 66: 56, 67: 74, 68: 65, 69: 51, 70: 70, 71: 52, 72: 91, 73: 41, 74: 56, 75: 20, 76: 98, 77: 7, 78: 20, 79: 38, 80: 37, 81: 65, 82: 11, 83: 58, 84: 35, 85: 67, 86: 66, 87: 89, 88: 77, 89: 60, 90: 88, 91: 46, 92: 25, 93: 73, 94: 92, 95: 59, 96: 97, 97: 62, 98: 58, 99: 15}, 16: {50: 75, 51: 40, 52: 43, 53: 53, 54: 26, 55: 82, 56: 10, 57: 51, 58: 52, 59: 10, 60: 21, 61: 71, 62: 47, 63: 85, 64: 2, 65: 65, 66: 49, 67: 36, 68: 53, 69: 86, 70: 88, 71: 89, 72: 91, 73: 13, 74: 57, 75: 16, 76: 97, 77: 35, 78: 79, 79: 15, 80: 69, 81: 73, 82: 19, 83: 65, 84: 95, 85: 30, 86: 39, 87: 71, 88: 97, 89: 13, 90: 54, 91: 98, 92: 48, 93: 4, 94: 63, 95: 76, 96: 75, 97: 85, 98: 95, 99: 47}, 17: {50: 57, 51: 45, 52: 34, 53: 31, 54: 88, 55: 68, 56: 48, 57: 50, 58: 74, 59: 94, 60: 71, 61: 29, 62: 57, 63: 44, 64: 73, 65: 44, 66: 63, 67: 64, 68: 32, 69: 55, 70: 17, 71: 28, 72: 21, 73: 40, 74: 25, 75: 38, 76: 45, 77: 16, 78: 78, 79: 65, 80: 90, 81: 81, 82: 14, 83: 70, 84: 98, 85: 28, 86: 90, 87: 40, 88: 78, 89: 50, 90: 74, 91: 9, 92: 57, 93: 79, 94: 68, 95: 77, 96: 47, 97: 14, 98: 33, 99: 28}, 18: {50: 91, 51: 30, 52: 19, 53: 56, 54: 25, 55: 34, 56: 77, 57: 41, 58: 44, 59: 80, 60: 6, 61: 59, 62: 55, 63: 54, 64: 5, 65: 48, 66: 60, 67: 45, 68: 42, 69: 89, 70: 41, 71: 47, 72: 63, 73: 72, 74: 17, 75: 91, 76: 22, 77: 57, 78: 42, 79: 54, 80: 50, 81: 47, 82: 51, 83: 3, 84: 29, 85: 2, 86: 53, 87: 31, 88: 33, 89: 23, 90: 10, 91: 77, 92: 75, 93: 97, 94: 69, 95: 14, 96: 66, 97: 97, 98: 74, 99: 59}, 19: {50: 6, 51: 48, 52: 37, 53: 76, 54: 62, 55: 57, 56: 98, 57: 45, 58: 50, 59: 29, 60: 60, 61: 83, 62: 88, 63: 20, 64: 87, 65: 96, 66: 15, 67: 2, 68: 58, 69: 73, 70: 60, 71: 5, 72: 38, 73: 68, 74: 18, 75: 64, 76: 12, 77: 75, 78: 23, 79: 25, 80: 34, 81: 28, 82: 81, 83: 63, 84: 2, 85: 3, 86: 51, 87: 11, 88: 42, 89: 15, 90: 32, 91: 72, 92: 98, 93: 61, 94: 84, 95: 45, 96: 35, 97: 57, 98: 23, 99: 73}, 20: {50: 37, 51: 38, 52: 78, 53: 15, 54: 29, 55: 18, 56: 28, 57: 69, 58: 86, 59: 5, 60: 82, 61: 49, 62: 11, 63: 22, 64: 48, 65: 60, 66: 97, 67: 81, 68: 79, 69: 85, 70: 40, 71: 11, 72: 48, 73: 43, 74: 82, 75: 92, 76: 54, 77: 0, 78: 68, 79: 51, 80: 57, 81: 47, 82: 74, 83: 38, 84: 23, 85: 6, 86: 86, 87: 36, 88: 8, 89: 78, 90: 43, 91: 13, 92: 95, 93: 52, 94: 38, 95: 72, 96: 86, 97: 12, 98: 89, 99: 61}, 21: {50: 18, 51: 30, 52: 7, 53: 69, 54: 17, 55: 35, 56: 27, 57: 34, 58: 10, 59: 80, 60: 5, 61: 74, 62: 12, 63: 60, 64: 30, 65: 11, 66: 26, 67: 51, 68: 63, 69: 6, 70: 84, 71: 85, 72: 6, 73: 28, 74: 34, 75: 10, 76: 19, 77: 20, 78: 82, 79: 99, 80: 54, 81: 76, 82: 61, 83: 68, 84: 82, 85: 3, 86: 43, 87: 71, 88: 60, 89: 80, 90: 48, 91: 88, 92: 48, 93: 61, 94: 11, 95: 78, 96: 44, 97: 57, 98: 19, 99: 12}, 22: {50: 0, 51: 56, 52: 92, 53: 58, 54: 22, 55: 14, 56: 18, 57: 31, 58: 39, 59: 37, 60: 44, 61: 30, 62: 33, 63: 43, 64: 98, 65: 23, 66: 73, 67: 30, 68: 34, 69: 84, 70: 5, 71: 81, 72: 44, 73: 69, 74: 59, 75: 83, 76: 66, 77: 93, 78: 84, 79: 5, 80: 28, 81: 20, 82: 59, 83: 30, 84: 86, 85: 67, 86: 24, 87: 60, 88: 42, 89: 41, 90: 5, 91: 72, 92: 53, 93: 98, 94: 62, 95: 55, 96: 57, 97: 54, 98: 52, 99: 56}, 23: {50: 46, 51: 37, 52: 78, 53: 65, 54: 80, 55: 66, 56: 32, 57: 39, 58: 94, 59: 96, 60: 65, 61: 38, 62: 24, 63: 25, 64: 48, 65: 64, 66: 15, 67: 32, 68: 30, 69: 46, 70: 11, 71: 37, 72: 9, 73: 18, 74: 36, 75: 19, 76: 41, 77: 80, 78: 42, 79: 84, 80: 45, 81: 97, 82: 62, 83: 33, 84: 28, 85: 31, 86: 64, 87: 44, 88: 23, 89: 65, 90: 32, 91: 91, 92: 51, 93: 71, 94: 78, 95: 85, 96: 14, 97: 15, 98: 59, 99: 82}, 24: {50: 28, 51: 94, 52: 83, 53: 89, 54: 95, 55: 34, 56: 46, 57: 9, 58: 41, 59: 39, 60: 15, 61: 22, 62: 69, 63: 74, 64: 53, 65: 65, 66: 79, 67: 81, 68: 66, 69: 87, 70: 76, 71: 16, 72: 94, 73: 68, 74: 24, 75: 58, 76: 72, 77: 98, 78: 50, 79: 23, 80: 44, 81: 62, 82: 37, 83: 50, 84: 90, 85: 16, 86: 32, 87: 85, 88: 59, 89: 49, 90: 98, 91: 96, 92: 82, 93: 35, 94: 65, 95: 25, 96: 44, 97: 28, 98: 63, 99: 82}, 25: {50: 66, 51: 83, 52: 99, 53: 95, 54: 72, 55: 41, 56: 50, 57: 62, 58: 14, 59: 0, 60: 2, 61: 72, 62: 66, 63: 40, 64: 99, 65: 29, 66: 87, 67: 99, 68: 28, 69: 78, 70: 6, 71: 72, 72: 11, 73: 35, 74: 38, 75: 38, 76: 35, 77: 95, 78: 74, 79: 36, 80: 39, 81: 10, 82: 15, 83: 98, 84: 58, 85: 84, 86: 88, 87: 26, 88: 39, 89: 93, 90: 81, 91: 77, 92: 21, 93: 69, 94: 93, 95: 69, 96: 46, 97: 59, 98: 36, 99: 71}, 26: {50: 11, 51: 81, 52: 45, 53: 12, 54: 49, 55: 53, 56: 48, 57: 38, 58: 1, 59: 28, 60: 72, 61: 22, 62: 4, 63: 83, 64: 36, 65: 23, 66: 75, 67: 35, 68: 18, 69: 77, 70: 74, 71: 81, 72: 18, 73: 91, 74: 50, 75: 76, 76: 57, 77: 20, 78: 91, 79: 77, 80: 54, 81: 56, 82: 92, 83: 21, 84: 17, 85: 72, 86: 34, 87: 97, 88: 10, 89: 44, 90: 23, 91: 35, 92: 1, 93: 38, 94: 79, 95: 56, 96: 6, 97: 29, 98: 55, 99: 80}, 27: {50: 31, 51: 44, 52: 75, 53: 48, 54: 82, 55: 91, 56: 47, 57: 67, 58: 3, 59: 14, 60: 88, 61: 44, 62: 59, 63: 9, 64: 71, 65: 81, 66: 86, 67: 63, 68: 22, 69: 3, 70: 80, 71: 26, 72: 86, 73: 56, 74: 43, 75: 76, 76: 51, 77: 1, 78: 1, 79: 32, 80: 18, 81: 26, 82: 42, 83: 86, 84: 77, 85: 50, 86: 88, 87: 86, 88: 59, 89: 26, 90: 83, 91: 88, 92: 75, 93: 58, 94: 55, 95: 14, 96: 21, 97: 56, 98: 34, 99: 45}, 28: {50: 60, 51: 80, 52: 16, 53: 83, 54: 28, 55: 49, 56: 46, 57: 13, 58: 38, 59: 85, 60: 42, 61: 47, 62: 91, 63: 82, 64: 3, 65: 17, 66: 27, 67: 86, 68: 42, 69: 55, 70: 81, 71: 57, 72: 7, 73: 53, 74: 82, 75: 90, 76: 14, 77: 70, 78: 85, 79: 51, 80: 37, 81: 13, 82: 12, 83: 72, 84: 79, 85: 43, 86: 49, 87: 78, 88: 24, 89: 74, 90: 48, 91: 97, 92: 44, 93: 55, 94: 24, 95: 100, 96: 30, 97: 13, 98: 13, 99: 24}, 29: {50: 64, 51: 36, 52: 12, 53: 9, 54: 100, 55: 11, 56: 73, 57: 69, 58: 4, 59: 73, 60: 78, 61: 54, 62: 26, 63: 7, 64: 68, 65: 96, 66: 19, 67: 46, 68: 21, 69: 35, 70: 28, 71: 98, 72: 74, 73: 39, 74: 42, 75: 66, 76: 4, 77: 1, 78: 98, 79: 39, 80: 52, 81: 80, 82: 65, 83: 77, 84: 3, 85: 60, 86: 86, 87: 8, 88: 66, 89: 23, 90: 12, 91: 68, 92: 69, 93: 37, 94: 25, 95: 77, 96: 77, 97: 91, 98: 12, 99: 83}, 30: {50: 72, 51: 99, 52: 9, 53: 66, 54: 99, 55: 74, 56: 52, 57: 19, 58: 9, 59: 79, 60: 79, 61: 54, 62: 61, 63: 63, 64: 18, 65: 78, 66: 8, 67: 62, 68: 80, 69: 2, 70: 93, 71: 92, 72: 92, 73: 72, 74: 34, 75: 42, 76: 39, 77: 39, 78: 94, 79: 32, 80: 52, 81: 70, 82: 54, 83: 67, 84: 53, 85: 10, 86: 1, 87: 48, 88: 61, 89: 99, 90: 79, 91: 92, 92: 78, 93: 44, 94: 52, 95: 19, 96: 73, 97: 72, 98: 83, 99: 19}, 31: {50: 5, 51: 16, 52: 64, 53: 77, 54: 42, 55: 86, 56: 95, 57: 39, 58: 51, 59: 80, 60: 22, 61: 98, 62: 73, 63: 35, 64: 40, 65: 74, 66: 93, 67: 39, 68: 47, 69: 19, 70: 75, 71: 98, 72: 39, 73: 89, 74: 20, 75: 37, 76: 37, 77: 96, 78: 85, 79: 50, 80: 57, 81: 47, 82: 3, 83: 44, 84: 13, 85: 43, 86: 71, 87: 44, 88: 47, 89: 78, 90: 84, 91: 60, 92: 34, 93: 22, 94: 44, 95: 67, 96: 72, 97: 4, 98: 90, 99: 14}, 32: {50: 44, 51: 65, 52: 70, 53: 1, 54: 98, 55: 25, 56: 68, 57: 34, 58: 91, 59: 41, 60: 3, 61: 61, 62: 64, 63: 25, 64: 39, 65: 95, 66: 74, 67: 54, 68: 57, 69: 77, 70: 13, 71: 96, 72: 54, 73: 13, 74: 20, 75: 70, 76: 27, 77: 72, 78: 14, 79: 10, 80: 99, 81: 60, 82: 47, 83: 93, 84: 96, 85: 19, 86: 23, 87: 65, 88: 85, 89: 66, 90: 68, 91: 39, 92: 27, 93: 44, 94: 35, 95: 76, 96: 34, 97: 98, 98: 69, 99: 26}, 33: {50: 94, 51: 85, 52: 58, 53: 86, 54: 69, 55: 28, 56: 51, 57: 95, 58: 66, 59: 79, 60: 81, 61: 35, 62: 79, 63: 43, 64: 91, 65: 64, 66: 37, 67: 75, 68: 63, 69: 39, 70: 94, 71: 67, 72: 3, 73: 97, 74: 97, 75: 43, 76: 78, 77: 42, 78: 86, 79: 97, 80: 49, 81: 100, 82: 84, 83: 83, 84: 66, 85: 74, 86: 54, 87: 72, 88: 93, 89: 76, 90: 76, 91: 82, 92: 55, 93: 54, 94: 23, 95: 76, 96: 3, 97: 88, 98: 1, 99: 26}, 34: {50: 67, 51: 70, 52: 10, 53: 12, 54: 77, 55: 1, 56: 18, 57: 47, 58: 96, 59: 29, 60: 89, 61: 33, 62: 0, 63: 78, 64: 69, 65: 15, 66: 2, 67: 68, 68: 93, 69: 11, 70: 36, 71: 62, 72: 26, 73: 9, 74: 57, 75: 15, 76: 14, 77: 28, 78: 67, 79: 20, 80: 30, 81: 28, 82: 11, 83: 48, 84: 91, 85: 7, 86: 68, 87: 85, 88: 39, 89: 73, 90: 7, 91: 24, 92: 93, 93: 68, 94: 41, 95: 8, 96: 29, 97: 48, 98: 22, 99: 28}, 35: {50: 3, 51: 96, 52: 78, 53: 91, 54: 13, 55: 86, 56: 29, 57: 62, 58: 95, 59: 15, 60: 73, 61: 36, 62: 42, 63: 0, 64: 58, 65: 58, 66: 20, 67: 2, 68: 39, 69: 14, 70: 53, 71: 100, 72: 99, 73: 94, 74: 74, 75: 34, 76: 100, 77: 11, 78: 2, 79: 55, 80: 74, 81: 70, 82: 53, 83: 6, 84: 100, 85: 28, 86: 54, 87: 63, 88: 16, 89: 10, 90: 4, 91: 19, 92: 4, 93: 74, 94: 4, 95: 72, 96: 91, 97: 16, 98: 66, 99: 51}, 36: {50: 58, 51: 91, 52: 90, 53: 52, 54: 74, 55: 85, 56: 6, 57: 91, 58: 44, 59: 51, 60: 38, 61: 10, 62: 34, 63: 41, 64: 85, 65: 41, 66: 68, 67: 2, 68: 31, 69: 80, 70: 86, 71: 27, 72: 14, 73: 37, 74: 12, 75: 98, 76: 69, 77: 38, 78: 20, 79: 90, 80: 13, 81: 7, 82: 66, 83: 33, 84: 90, 85: 4, 86: 28, 87: 7, 88: 14, 89: 63, 90: 35, 91: 69, 92: 68, 93: 63, 94: 21, 95: 24, 96: 4, 97: 48, 98: 23, 99: 7}, 37: {50: 36, 51: 18, 52: 16, 53: 23, 54: 67, 55: 30, 56: 25, 57: 70, 58: 2, 59: 31, 60: 44, 61: 18, 62: 59, 63: 41, 64: 55, 65: 71, 66: 34, 67: 77, 68: 34, 69: 50, 70: 86, 71: 37, 72: 65, 73: 23, 74: 3, 75: 54, 76: 57, 77: 56, 78: 25, 79: 35, 80: 32, 81: 5, 82: 62, 83: 11, 84: 40, 85: 42, 86: 71, 87: 20, 88: 32, 89: 68, 90: 87, 91: 83, 92: 16, 93: 6, 94: 15, 95: 78, 96: 84, 97: 85, 98: 19, 99: 77}, 38: {50: 44, 51: 73, 52: 78, 53: 13, 54: 57, 55: 11, 56: 96, 57: 40, 58: 93, 59: 22, 60: 36, 61: 48, 62: 19, 63: 86, 64: 56, 65: 77, 66: 93, 67: 79, 68: 48, 69: 13, 70: 100, 71: 40, 72: 51, 73: 30, 74: 63, 75: 39, 76: 92, 77: 16, 78: 91, 79: 90, 80: 38, 81: 69, 82: 6, 83: 72, 84: 66, 85: 100, 86: 93, 87: 63, 88: 95, 89: 72, 90: 93, 91: 10, 92: 98, 93: 80, 94: 96, 95: 34, 96: 78, 97: 29, 98: 33, 99: 8}, 39: {50: 77, 51: 100, 52: 94, 53: 100, 54: 89, 55: 70, 56: 62, 57: 41, 58: 12, 59: 25, 60: 13, 61: 48, 62: 6, 63: 62, 64: 25, 65: 98, 66: 2, 67: 55, 68: 12, 69: 37, 70: 49, 71: 85, 72: 58, 73: 23, 74: 21, 75: 64, 76: 96, 77: 58, 78: 57, 79: 4, 80: 91, 81: 76, 82: 11, 83: 48, 84: 8, 85: 32, 86: 48, 87: 80, 88: 53, 89: 98, 90: 7, 91: 51, 92: 96, 93: 98, 94: 7, 95: 77, 96: 98, 97: 50, 98: 6, 99: 63}, 40: {50: 96, 51: 55, 52: 38, 53: 99, 54: 92, 55: 2, 56: 12, 57: 57, 58: 93, 59: 52, 60: 16, 61: 68, 62: 85, 63: 67, 64: 42, 65: 12, 66: 95, 67: 87, 68: 0, 69: 71, 70: 0, 71: 72, 72: 54, 73: 58, 74: 52, 75: 69, 76: 76, 77: 16, 78: 76, 79: 95, 80: 24, 81: 91, 82: 42, 83: 92, 84: 52, 85: 13, 86: 66, 87: 72, 88: 34, 89: 29, 90: 57, 91: 42, 92: 100, 93: 83, 94: 34, 95: 30, 96: 53, 97: 32, 98: 76, 99: 88}, 41: {50: 100, 51: 22, 52: 37, 53: 33, 54: 15, 55: 91, 56: 41, 57: 55, 58: 72, 59: 65, 60: 29, 61: 47, 62: 60, 63: 92, 64: 65, 65: 35, 66: 29, 67: 100, 68: 41, 69: 71, 70: 16, 71: 13, 72: 23, 73: 28, 74: 23, 75: 14, 76: 42, 77: 32, 78: 10, 79: 93, 80: 27, 81: 11, 82: 37, 83: 68, 84: 82, 85: 59, 86: 68, 87: 85, 88: 69, 89: 51, 90: 21, 91: 63, 92: 29, 93: 38, 94: 25, 95: 20, 96: 4, 97: 75, 98: 84, 99: 33}, 42: {50: 74, 51: 42, 52: 96, 53: 53, 54: 28, 55: 4, 56: 50, 57: 66, 58: 75, 59: 26, 60: 87, 61: 4, 62: 82, 63: 70, 64: 8, 65: 47, 66: 59, 67: 74, 68: 26, 69: 76, 70: 50, 71: 48, 72: 6, 73: 18, 74: 60, 75: 30, 76: 37, 77: 64, 78: 76, 79: 53, 80: 31, 81: 71, 82: 15, 83: 13, 84: 67, 85: 50, 86: 92, 87: 29, 88: 32, 89: 47, 90: 51, 91: 24, 92: 93, 93: 35, 94: 49, 95: 59, 96: 74, 97: 67, 98: 18, 99: 36}, 43: {50: 17, 51: 0, 52: 31, 53: 63, 54: 70, 55: 47, 56: 74, 57: 74, 58: 97, 59: 53, 60: 89, 61: 52, 62: 12, 63: 31, 64: 63, 65: 86, 66: 21, 67: 98, 68: 2, 69: 20, 70: 60, 71: 25, 72: 92, 73: 5, 74: 81, 75: 74, 76: 76, 77: 68, 78: 85, 79: 86, 80: 25, 81: 78, 82: 65, 83: 13, 84: 35, 85: 31, 86: 24, 87: 11, 88: 96, 89: 32, 90: 85, 91: 6, 92: 32, 93: 13, 94: 31, 95: 32, 96: 92, 97: 81, 98: 44, 99: 81}, 44: {50: 98, 51: 19, 52: 72, 53: 32, 54: 57, 55: 86, 56: 19, 57: 5, 58: 38, 59: 49, 60: 27, 61: 50, 62: 32, 63: 56, 64: 49, 65: 37, 66: 71, 67: 45, 68: 24, 69: 84, 70: 26, 71: 30, 72: 32, 73: 45, 74: 45, 75: 0, 76: 27, 77: 58, 78: 18, 79: 18, 80: 50, 81: 46, 82: 50, 83: 63, 84: 46, 85: 3, 86: 82, 87: 5, 88: 1, 89: 40, 90: 53, 91: 57, 92: 5, 93: 2, 94: 98, 95: 50, 96: 81, 97: 43, 98: 11, 99: 78}, 45: {50: 19, 51: 81, 52: 18, 53: 10, 54: 57, 55: 53, 56: 80, 57: 71, 58: 3, 59: 92, 60: 93, 61: 77, 62: 87, 63: 20, 64: 77, 65: 33, 66: 58, 67: 1, 68: 25, 69: 91, 70: 7, 71: 44, 72: 6, 73: 0, 74: 20, 75: 78, 76: 79, 77: 88, 78: 15, 79: 1, 80: 32, 81: 2, 82: 98, 83: 73, 84: 83, 85: 0, 86: 56, 87: 14, 88: 14, 89: 66, 90: 76, 91: 18, 92: 60, 93: 1, 94: 62, 95: 77, 96: 88, 97: 59, 98: 16, 99: 48}, 46: {50: 35, 51: 58, 52: 30, 53: 46, 54: 38, 55: 76, 56: 33, 57: 31, 58: 11, 59: 87, 60: 65, 61: 51, 62: 1, 63: 20, 64: 84, 65: 80, 66: 70, 67: 21, 68: 93, 69: 45, 70: 83, 71: 52, 72: 28, 73: 74, 74: 28, 75: 37, 76: 93, 77: 90, 78: 43, 79: 71, 80: 74, 81: 33, 82: 60, 83: 56, 84: 67, 85: 55, 86: 82, 87: 49, 88: 29, 89: 97, 90: 67, 91: 73, 92: 2, 93: 39, 94: 58, 95: 35, 96: 40, 97: 17, 98: 9, 99: 54}, 47: {50: 59, 51: 69, 52: 40, 53: 91, 54: 29, 55: 95, 56: 93, 57: 5, 58: 31, 59: 52, 60: 31, 61: 78, 62: 10, 63: 13, 64: 65, 65: 38, 66: 37, 67: 41, 68: 95, 69: 23, 70: 58, 71: 26, 72: 41, 73: 75, 74: 27, 75: 16, 76: 28, 77: 76, 78: 63, 79: 70, 80: 5, 81: 42, 82: 16, 83: 50, 84: 8, 85: 0, 86: 10, 87: 63, 88: 39, 89: 7, 90: 42, 91: 66, 92: 98, 93: 6, 94: 51, 95: 69, 96: 47, 97: 77, 98: 83, 99: 76}, 48: {50: 66, 51: 46, 52: 13, 53: 49, 54: 45, 55: 100, 56: 21, 57: 77, 58: 4, 59: 88, 60: 62, 61: 93, 62: 97, 63: 95, 64: 67, 65: 99, 66: 77, 67: 97, 68: 19, 69: 98, 70: 83, 71: 12, 72: 85, 73: 3, 74: 60, 75: 47, 76: 66, 77: 22, 78: 67, 79: 98, 80: 20, 81: 15, 82: 3, 83: 35, 84: 97, 85: 66, 86: 39, 87: 6, 88: 44, 89: 15, 90: 20, 91: 87, 92: 39, 93: 27, 94: 43, 95: 7, 96: 94, 97: 82, 98: 56, 99: 96}, 49: {50: 40, 51: 5, 52: 80, 53: 4, 54: 6, 55: 9, 56: 50, 57: 49, 58: 39, 59: 29, 60: 52, 61: 74, 62: 22, 63: 38, 64: 15, 65: 38, 66: 33, 67: 32, 68: 6, 69: 55, 70: 100, 71: 100, 72: 13, 73: 55, 74: 22, 75: 23, 76: 61, 77: 63, 78: 62, 79: 67, 80: 65, 81: 94, 82: 47, 83: 82, 84: 24, 85: 68, 86: 86, 87: 61, 88: 85, 89: 59, 90: 65, 91: 100, 92: 8, 93: 18, 94: 21, 95: 70, 96: 76, 97: 99, 98: 60, 99: 3}} ```
Hello, I found an issue with the output.
Code:
from hungarian_algorithm import algorithm
dict = {0: {8: 457, 10: 696, 16: 492}, 2: {8: 973, 10: 566, 16: 1156}, 18: {8: 271, 10: 1324, 16: 469}}
print(algorithm.find_matching(dict, matching_type = 'min', return_type = 'list'))
Output:
[((0, 8), 457), ((2, 10), 566), ((18, 8), 271)]
The number 8 is in the output twice and that should make the output invalid.
Thank you for your help in advance :)
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.