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
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).
Sometimes it hangs indefinitely and sometimes it crashes with the same error as #5