PrivacyScanData/visualize/Visualization-of-popular-algorithms-in-Python/Assignment Problem

Visualisation of Assignment Problem using networkx library

INPUT

Input is taken from the file

input.txt

Sample input

 4
 9 2 7 8
 6 4 3 7 
 5 8 1 8
 7 6 9 4

First line contains n, the number of people which is the same as the number of jobs. Followed by n*n weighted profit matrix.

Draw Graph

A bipartite graph is to be drawn. Person and Job - are the 2 sets of nodes. Since, person is connected to every possible job and a job has connection from every person.

Assignment Problem

Assignment Problem is a combinatorial optimization problem. It consists of finding a maximum weight matching (or minimum weight perfect matching) in a weighted bipartite graph.

Here, we have n people and n jobs that need to be done. Given profit matrix, we need to assign exactly one person to each job and exactly one job to each person in such a way that the total profit of the assignment in maximized. (It is a linear assignment problem, since number of people and jobs are equal.)

Hungarian algorithm is one of the most effient methods that solves the linear assignment problem in polynomial time(with a time complexity of O(n^3)).

The code here,is an implementation of Hungarian algorithm. The resultant graph for the sample input with maximum weight matching (denoted by red edges):

Complexity

Time: O(n^3)
n - number of people( = number of jobs)