#52 HungarianMethod runs in endless loop

[seven]

HungarianMethod runs in endless loop in following snip code:
while(coveredNodes.size() != partA.size()){

        updateGraph(graph, coveredNodes);
        printBipartiteGraph(partA, partB);

        GraphUtils.clearGraph(graph);

        coveredNodes = getMin(graph, partA, partB);
        debug("Min Number of covered rows/column=" + coveredNodes.size());

}

Please consider if it is bug.
This is the test code I tried:

public void test_debug(){

    MatrixEntry matrix[][] = new MatrixEntry[3][17];
    List<INodeExt> vnodes = new ArrayList<INodeExt>();
    List<INodeExt> wnodes = new ArrayList<INodeExt>();
    for(int i =1; i<4; i++){
        INodeExt newnode = GraphExtentionFactory.createNodeExtention("v" + i);
        vnodes.add(newnode);
    }
    for(int i =1; i<18; i++){
        INodeExt newnode = GraphExtentionFactory.createNodeExtention("w"+i);
        wnodes.add(newnode);
    }

    List<Integer> pnoderes = new ArrayList<Integer>();

    int[][] resultvalue = new int[][]{
            {6,14,4,1,1,16,4,5,1,1,3,1,7,6,4,1,1},
            {6,12,4,1,1,15,4,5,1,1,3,1,7,6,4,1,1},
            {6,13,4,1,1,7,4,5,1,1,3,1,7,8,4,1,1}};

    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 17; j++){
            INodeExt child1 =vnodes.get(i);
            INodeExt child2 =wnodes.get(j);

            MatrixEntry me = new MatrixEntry();
            me.v = child1;
            me.w = child2;

            matrix[i][j] = me;
            me.result = resultvalue[i][j];
        }
    }

    int size[] = {3, 17};

    /* DEBUG */
    printMatrix(matrix, size);

    /* create a bipartite graph from the matrix */
    List<INodeExt> part1 = new ArrayList<INodeExt>();
    List<INodeExt> part2 = new ArrayList<INodeExt>();
    IDirectedGraphExt graph = createBibartitGraph(matrix, size, part1, part2);

    /* an optimization to avoid the creation of an empty matrix */
    if(graph.getEdgeList().size() == 0){
        return;
    }

    /* find max bipartite matching in weighted bipartite graph */
    MaxWeightedBipartiteMatching mwbm = new MaxWeightedBipartiteMatching();
    List<IEdgeExt> MatchedEdges = mwbm.execute(graph, part1, part2);

    /*increase edges weight of matched nodes in bipartite graph*/
    return;

}

[seven]

I re-implement the 'HungarianMethod ' module with python munkres, which can finish the calculating in a short duration:

def execute_with_munkres(self, graph, partA, partB):

    """Executes Hungarian method with munkres(better performance).
    Args: graph - the bipartite graph
    Args: partA - the 1st partition
    Args: PartB - the 2nd partition
    Returns: the list of matched edges
    """

    clear_graph(graph)
    munkres_matrix = []
    for nodea in partA:
        row = []
        for nodeb in partB:
            for edge in graph.get_edges():
                if edge.get_source() == nodea and edge.get_target() == nodeb:
                    row.append(edge.get_counter())
                    break
        if len(row) != len(partB):
            print 'Error, row not complete!'
        munkres_matrix.append(row)
    if len(munkres_matrix) != len(row):
        print 'Error, col not complete'
    m = Munkres()
    indexes = m.compute(munkres_matrix)

    matched_edges = []
    for row_index, column_index in indexes:
        source = partA[row_index]
        target = partB[column_index]
        if source.get_data() is not None and target.get_data() is not None:
            for edge in graph.get_edges():
                if edge.get_source() == source and edge.get_target() == target:
                    matched_edges.append(edge)
                    break
    return matched_edges

[seven]

I've solved the problem with my HungarianMethod java implementation. It is indeed a bug. please fix!