Matching

COMP572 -- Fall 2007

Hungarian Algorithm Specification

A: (1 person) Implement Hungarian algorithm

Input:
The input is read from standard input or a file (your documentation should indicate which). The first line contains an integer n where n is the number of nodes of both sides of the bipartite graph. The nodes are referred as x₀ to x_n-1 and y₀ to y_n-1. Each of the next n lines of the input contains n numbers. The j-th integer in the i-th line indicates that the weight of the edge from node x_i to node y_j. Note that the weights should be assumed to be integers (positive, 0 or negative)

You can assume:
n is between 1 and 100.
The absolute weight of all edges is less than 10⁹.
The absolute total weight of the max bipartite matching is less than 10⁹.

Output:
i) Print out the total weight of the max bipartite matching in the first line.

ii) Print out the a₀ to a_n-1, a permutation of 0 to n-1, in next line where a_i specifies that x_i is matched to y_{a_i}.

iii) Print out the associated feasible labellings of y₀ to y_n-1.

iv) Print out the associated feasible labellings of x₀ to x_n-1.

Note that this matching may not be unique. You just need to output one optimal matching

Follow the format as sample output. Don’t print any other text character. Always use a space to separate two values.

Sample input: (Hungarian Algorithm, page 15)

Sample output:

B: (2 person) Implement part (A) and a GUI for the Hungarian Algorithm:

Your program should also include a GUI that includes

A graphical method for inputting/editing a weighted bipartite graph
A graphical method for illustrating the algorithm. That is, at every step it should show the current matching, feasible labellings and how the augmenting tree is built.

Note that, even with the GUI, your program should also permit inputting text data via standard input or from a file following the specifications from part (A)

This page was released on November 2, 2007 and last revised on 11/02/2007 13:26 +0800

Return to main project page