pythonhungarian-algorithm

hungarian algorithm's graph in python


I am trying to implement hungarian algorithm in my project, but I don't understand why it gives a endless loop...I have tried with an other bibartite graph and it works. So I want to know what's wrong with my graph G

 from hungarian_algorithm import algorithm
 G={
'agt2': {'Commentaire':200,'PhotoProfil': 8, 'PhotoSupp': 10, 'Prenom': 0}, 
'coco': {'Commentaire': 300, 'PhotoProfil': 200, 'PhotoSupp': 300, 'Prenom': 300}
 }
res=algorithm.find_matching(G,matching_type='max',return_type='list')
print(res)

Solution

  • The graph is fine, it's probably a bug in the implementation of that package. As pointed out in my comment you can use scipy.optimize.linear_sum_assignment from SciPy instead.

    For example

    import numpy as np
    from scipy.optimize import linear_sum_assignment
    
    # solve the assignment problem
    G = np.array([[200, 8,   10,  0],
                  [300, 200, 300, 300]])
    row_indices, col_indices = linear_sum_assignment(G, maximize=True)
    
    # print results
    row_names = ['agt2', 'coco']
    col_names = ['Commentaire', 'PhotoProfil', 'PhotoSupp', 'Prenom']
    edges = [((row_names[r], col_names[c]), G[r, c]) for r, c in zip(row_indices, col_indices)]
    print(edges)
    

    prints

    [(('agt2', 'Commentaire'), 200), (('coco', 'PhotoSupp'), 300)]