Hungarian Algorithm returns Boolean value for Traveling salesman problem

Question

I am trying to implement Hungarian algorithm right off the shelf on a cost dictionary as part of Traveling salesman problem. The goal is to get path with minimum cost which hopefully covers all cities once. Here is the VS code I implemented,(see this link) .

import hungarian_algorithm
from hungarian_algorithm import algorithm
G = {
    'City1': {'City1': 9999, 'City2': 132, 'City3': 217, 'City4': 164, 'City5': 58},
    'City2': {'City1': 132, 'City2': 9999, 'City3': 290, 'City4': 201, 'City5': 79},
    'City3': {'City1': 217, 'City2': 290, 'City3': 9999, 'City4': 113, 'City5': 303},
    'City4': {'City1': 164, 'City2': 201, 'City3': 113, 'City4': 9999, 'City5': 196},
    'City5': {'City1': 58, 'City2': 79, 'City3': 303, 'City4': 196, 'City5':9999 }
}

z = algorithm.find_matching(G, matching_type = 'min', return_type = 'list' )
print (z)

Here G is the dictionary with pairwise distance between 2 cities. Then I did execute the code as follows;

(.venv) (base) jayantsingh@jayants-MacBook-Pro traveling_salesman % python3 -i tsp.py
False

May I know what doe the value False mean here? I was expecting an output as follows;

Expected Output

[(('City1', 'City5'), 58), (('City5', 'City2'), 79), (('City2', 'City1'), 132), (('City3', 'City4'), 113), (('City4', 'City3'), 113)]

Answer 1

The library is probably complaining about the input-graph not being bipartite (which is necessary according to the docs) as you introduced self-loops.

Strangely removing those self-loop edges still doesn't make it work. I wouldn't be too happy with the documentation of this library and move on to something else (e.g. scipy). The author also describes scipy's implementation as more reliable.

Anyway...

Skimming over their examples, it seems, this library really does not like name/node-collisions in-between rows and cols and voila... Introducing a prefix to one of rows / cols makes it work.

G = {
    '_City1': {'City1': 9999, 'City2': 132, 'City3': 217, 'City4': 164, 'City5': 58},
    '_City2': {'City1': 132, 'City2': 9999, 'City3': 290, 'City4': 201, 'City5': 79},
    '_City3': {'City1': 217, 'City2': 290, 'City3': 9999, 'City4': 113, 'City5': 303},
    '_City4': {'City1': 164, 'City2': 201, 'City3': 113, 'City4': 9999, 'City5': 196},
    '_City5': {'City1': 58, 'City2': 79, 'City3': 303, 'City4': 196, 'City5':9999 }
}

-> [(('_City3', 'City4'), 113), (('_City5', 'City2'), 79), (('_City4', 'City3'), 113), (('_City1', 'City5'), 58), (('_City2', 'City1'), 132)]