def make_cost_matrix(profit_matrix, inversion_function):
     """
     **DEPRECATED**
     Please use the module function ``make_cost_matrix()``.
     """
     import munkres
     return munkres.make_cost_matrix(profit_matrix, inversion_function)

def similar(list_current,list_called):
	global P,total
	# comparing the length of two files to compare smaller length to bigger 
	if len(list_current)<len(list_called):
		# calling comparison function to compare both files line by line for similarity 
		similarity = comparison(list_current,list_called)
		# storing the lenght of smaller 
		P = len(list_current)
		point=[[0 for x in range(len(list_called))] for y in range(len(list_current))]
	else:
		# calling comparison function to compare both files line by line for similarity
		similarity = comparison(list_called,list_current)
		P = len(list_called)
		point=[[0 for x in range(len(list_current))] for y in range(len(list_called))]
	# calling functions of munkres to form maximum weighted bipartite matching graph
	graph_matrix = make_cost_matrix(similarity, lambda cost: 1.0 - cost)
	m = Munkres()
	indexes =m.compute(graph_matrix)
	total = 0
	for row, column in indexes:
		# forming list of points(lines) of similarity between two files
		value = similarity[row][column]
		if value>0.0:
			total += 1
			point[row][column]=1
	return point

    def calc_hungarian_alignment_score(self, s, t):
        """Calculate the alignment score between the two texts s and t
        using the implementation of the Hungarian alignment algorithm
        provided in https://pypi.python.org/pypi/munkres/."""
        s_toks = get_tokenized_lemmas(s)
        t_toks = get_tokenized_lemmas(t)
        #print("#### new ppdb calculation ####")
        #print(s_toks)
        #print(t_toks)
        df = pd.DataFrame(index=s_toks, columns=t_toks, data=0.)

        for c in s_toks:
            for a in t_toks:
                df.ix[c, a] = self.compute_paraphrase_score(c, a)

        matrix = df.values
        cost_matrix = make_cost_matrix(matrix, lambda cost: _max_ppdb_score - cost)

        indexes = _munk.compute(cost_matrix)
        total = 0.0
        for row, column in indexes:
            value = matrix[row][column]
            total += value
        #print(s + ' || ' + t + ' :' + str(indexes) + ' - ' + str(total / float(np.min(matrix.shape))))

        # original procedure returns indexes and score - i do not see any use for the indexes as a feature
        # return indexes, total / float(np.min(matrix.shape))
        return total / float(np.min(matrix.shape))

def maximum_weight_bipartite(matrix):
    cost_matrix = make_cost_matrix(matrix, lambda cost: 100000 - cost)

    m = Munkres()
    indices = m.compute(cost_matrix)

    return indices

    def get_suitability_score(customer_list, product_list):
        '''
        calculate the total maximum suitability score
        by using munkres algorithm and returns a detailed
        customer_product_enties & total suitability score
        '''
        suitability_scores = []
        customer_suitability_scores = []

        for customer in customer_list:
            for product in product_list:
                customer_suitability_scores.append(SuitabilityScore.calculate_suitability_score(customer,product))
            suitability_scores.append(customer_suitability_scores)
            customer_suitability_scores = []


        customer_product_entries = []
        cost_matrix = make_cost_matrix(suitability_scores, lambda cost: 1e10 - cost)
        munkres = Munkres()
        indexes = munkres.compute(cost_matrix)
        total_suitability_score = 0
        for customer_index, product_index  in indexes:
            suitability_score = suitability_scores[customer_index][product_index]
            total_suitability_score += suitability_score
            suitability_score_entry = SuitabilityScoreEntry(customer_list[customer_index],product_list[product_index],suitability_score)
            customer_product_entries.append(suitability_score_entry)
            #print(customer_index,product_index)

        return customer_product_entries,total_suitability_score

def filter_rects(all_rects, threshold, input_rects=[], max_threshold=1.0, config=None):
    """Takes in all_rects and based on the threshold carries out the stitching process
    as described in the paper."""

    accepted_rects = input_rects

    for i in range(0, config["grid_height"], 1):
        for j in range(0, config["grid_width"], 1):
            relevant_rects = []
            current_rects = [r for r in all_rects[i][j] if r.confidence > threshold]

            for other in accepted_rects:
                for current in current_rects:
                    if other.overlaps(current):
                        relevant_rects.append(other)
                        break

            if len(relevant_rects) == 0 or len(current_rects) == 0:
                accepted_rects += current_rects
                continue

            matrix = []
            for c in current_rects:
                row = []
                for a in relevant_rects:
                    row.append(1000)
                    if a.overlaps(c):
                        row[-1] -=100
                    row[-1] += a.distance(c) / 1000.0
                matrix.append(row)

            m = Munkres()
            cost_matrix = make_cost_matrix(matrix, lambda x: x)
            indices = m.compute(matrix)

            bad = set()
            for row, column in indices:
                c = current_rects[row]
                a = relevant_rects[column]
                if c.confidence > max_threshold:
                    bad.add(row)
                    continue
                if c.overlaps(a):
                    if c.confidence > a.confidence and c.iou(a) > 0.7:
                        c.true_confidence = a.confidence
                        accepted_rects.remove(a)
                    else:
                        bad.add(row)

            for k in range(len(current_rects)):
                if k not in bad:
                    accepted_rects.append(current_rects[k])

    return accepted_rects

def compute_agreements(similarity):
    import munkres
    import numpy as np

    m = munkres.Munkres()
    print("Computing mapping...")
    similarity = munkres.make_cost_matrix(similarity, lambda cost: 1 - cost)
    indexes = m.compute(similarity)

    agreement = np.sum([1 - similarity[r][c] for r, c in indexes]) / len(similarity)
    print("Agreement:", agreement)
    return agreement

def test_profit():
    profit_matrix = [[94, 66, 100, 18, 48],
                     [51, 63, 97, 79, 11],
                     [37, 53, 57, 78, 28],
                     [59, 43, 97, 88, 48],
                     [52, 19, 89, 60, 60]]
    import sys
    cost_matrix = munkres.make_cost_matrix(
        profit_matrix, lambda cost: sys.maxsize - cost
    )
    indices = m.compute(cost_matrix)
    profit = sum([profit_matrix[row][column] for row, column in indices])
    assert_equals(profit, 392)

def matching(male_distances):
    cost_matrix = munkres.make_cost_matrix(male_distances,
                                           lambda cost: 1.0 - cost)
    m = Munkres()
    indices = m.compute(cost_matrix)
    total = 0.0
    pairings = {}
    for row, column in indices:
        value = male_distances[row][column]
        total += value
        pairings[column] = [row]
    #print "Satish was here"
    print 'total profit=%f' % total
    return pairings

def do_hungarian_assignment(dict_a, dict_b, cost_func, yield_condt, cost_matrix_func=None):
    for ka  in dict_a.keys():
        if ka in dict_b:
            ia  = dict_a[ka]
            ib  = dict_b[ka]
            mat = [ [cost_func(a,b) for b in ib] for a in ia]
            #max similarity calculation
            c_mat = None
            if cost_matrix_func is not None:
                c_mat = make_cost_matrix(mat,cost_matrix_func)
            else:
                c_mat = mat
            indexes = MUNKR.compute(c_mat)
            for row, col in indexes:
                # yield only if condition satisfied
                if yield_condt(mat[row][col]):
                    #print '(%d, %d) -> %d' % (row, col, mat[row][col])
                    yield ia[row], ib[col]

def make_match(advertisers, persons, ctrfunc = funky_ctr):
    # make the ctr matrix
    ctr_matrix = make_ctr_matrix(advertisers, persons, ctrfunc)

    # convert it to a cost matrix by subtracting all values from a larger value
    cost_matrix = make_cost_matrix(ctr_matrix, lambda ctr: sys.maxsize - ctr)

    # compute the match
    match = Munkres().compute(cost_matrix)

    # elements in match are two-element lists, where the first is the
    # index into advertisers and second is index into persons

    # compute the total ctr by looking up the match elements in the ctr
    # matrix
    total_ctr = sum(map(lambda pair: ctr_matrix[pair[0]][pair[1]], match))

    return match, total_ctr

def assignDuties(dayA, dayB):
    if len(dayA) != len(dayB):
        print "Illegal!! number of duties should be equal every day"
        exit(1)
    matrix = createMatrix(len(dayA))
    ##Fill the matrix with the similarities
    for i in range(len(dayA)):
        for j in range(len(dayA)):
            matrix[i][j] = calcSimilarity(dayA[i], dayB[j])
    ##The following line is called to make sure we find the maximum sum and not the minimum
    ##Note that since all similarities are in [0,1] 2 is bigger than all.
    cost_matrix = make_cost_matrix(matrix, lambda cost: 2 - cost)
    m = Munkres()
    ##Indexes will contain the assignment
    indexes = m.compute(cost_matrix)
    res = []
    for row, column in indexes:
        res.append(("Driver "+str(row + 1) ,("Day 1 duty: "+str(row + 1),"Day 2 duty: "+str(column + 1))))
    return res

def get_best_matching(source_corpus, target_corpus, scores):
    stripper = LanguageStripper()
    err = 0

    m = munkres.Munkres()
    cost_matrix = munkres.make_cost_matrix(scores, lambda cost: 1 - cost)
    indexes = m.compute(cost_matrix)

    for row, column in indexes:
        s_url = source_corpus.keys()[row]
        t_url = target_corpus.keys()[column]
        success = stripper.strip(t_url) == stripper.strip(s_url)
        if not success:
            err += 1
        # sys.stdout.write("%f\t%s\t%s\t%s\n" %
        #                  (scores[row, column], success, s_url, t_url))

    n = min(len(source_corpus), len(target_corpus))
    sys.stderr.write("Correct: %d out of %d = %f%%\n" %
                     (n - err, n, (1. * n - err) / n))

def calc_hungarian_alignment_score(s, t):
    """Calculate the alignment score between the two texts s and t
    using the implementation of the Hungarian alignment algorithm
    provided in https://pypi.python.org/pypi/munkres/."""
    s_toks = get_tokenized_lemmas(s)
    t_toks = get_tokenized_lemmas(t)

    df = pd.DataFrame(index=s_toks, columns=t_toks, data=0.)

    for c in s_toks:
        for a in t_toks:
            df.ix[c, a] = compute_paraphrase_score(c, a)

    matrix = df.values
    cost_matrix = make_cost_matrix(matrix, lambda cost: _max_ppdb_score - cost)

    indexes = _munk.compute(cost_matrix)
    total = 0.0
    for row, column in indexes:
        value = matrix[row][column]
        total += value
    return indexes, total / float(np.min(matrix.shape))

def hungarianAssignment(cases, controls, numberOfControlsPerCase):
    selectedControls = list()
    convFactor = 100000.00
    m = list()
    for control in controls:
        row = list()
        for _ in xrange(numberOfControlsPerCase):
            row += [(control.relatedTo.get(case) if (control.relatedTo.has_key(case)) else 0) for case in cases]
        m.append(row)
    cm = munkres.make_cost_matrix(m, lambda cost: convFactor - cost * convFactor)
    matrix = cm
    m = Munkres()
    indexes = m.compute(matrix)
    total = 0
    for row, column in indexes:
        value = matrix[row][column]
        total += value
        if value < convFactor:
            selectedControls.append(controls[row % len(controls)])
    print("\tassignment kic score: %f" % (float(len(indexes) * convFactor - total) / convFactor))
    print("\tall kic score: %f" % (kicScore(cases, selectedControls)))
    return [person.id for person in selectedControls]

    def linkTemplates(self, sentence):
        """ link group size and group templates using Hungarian matching algorithm """
        templates = sentence.templates
        qTemplateList = templates.getList(self.quantityType)
        mTemplateList = templates.getList(self.mentionType)

        nQuantities = len(qTemplateList)
        nMentions = len(mTemplateList)
        maxSize = max(nQuantities, nMentions)

        if nQuantities == 0 or nMentions == 0:
            return

        probMatrix = []
        for qIdx in range(maxSize):
            probMatrix.append([])
            for mIdx in range(maxSize):
                probMatrix[qIdx].append(0)

        for fv in templates.featureVectors:
            probMatrix[fv.valueId][fv.mentionId] = fv.prob * 1000

        costMatrix = munkres.make_cost_matrix(probMatrix, lambda cost: 1000 - cost)
        m = munkres.Munkres()
        #    print probMatrix
        #    print costMatrix
        indices = m.compute(costMatrix)
        for qIdx, mIdx in indices:
            if qIdx < nQuantities and mIdx < nMentions:
                prob = probMatrix[qIdx][mIdx]
                if prob >= 500:
                    # this quantity and mention should be associated
                    prob = float(prob) / 1000
                    qTemplate = qTemplateList[qIdx]
                    mTemplate = mTemplateList[mIdx]
                    self.linkQuantityAndMention(qTemplate, mTemplate, prob)

def costify(similarity_matrix):
    """Transform a similarity matrix into a cost matrix."""
    return munkres.make_cost_matrix(similarity_matrix, lambda s: 1 - s)

def cost_matrix(contingency_table):
    """Hungarian method assumes the goal of minimum cost, while our goal with a
    contigency table is maximum cost. To deal with this, the table is inverted in
    an additive sense.
    """
    return make_cost_matrix(contingency_table, lambda cost: sys.maxsize - cost)

    def linkTemplatesHungarian(self, sentence):
        """ link group size and group templates using Hungarian matching algorithm """
        #    print 'linking all templates'
        templates = sentence.templates
        costValueList = templates.getList('cost_value')
        outcomeList = templates.getList('outcome')
        groupList = templates.getList('group')

        nCostValues = len(costValueList)
        nGroupOutcomePairs = len(outcomeList)*len(groupList)

        if nGroupOutcomePairs == 0 or nCostValues == 0:
            return

        maxSize = max(nCostValues, nGroupOutcomePairs)

        # build list of group-outcome pairs
        goPairs = []
        for group in groupList:
            for outcome in outcomeList:
                goPairs.append((group, outcome))

        # initialize cost matrix for matching cost values with group,outcome pairs
        probMatrix = []
        probMultiplier = 100000

        for cvIdx in range(maxSize):
            probMatrix.append([])
            for goIdx in range(maxSize):
                if cvIdx < nCostValues and goIdx < nGroupOutcomePairs:
                    cv = costValueList[cvIdx]
                    (group, outcome) = goPairs[goIdx]

                    outcomeFV = cv.getMatchFeatures(outcome)
                    groupFV = cv.getMatchFeatures(group)
                    groupProb = groupFV.prob
                    outcomeProb = outcomeFV.prob
                    prob = round(groupProb * outcomeProb * probMultiplier)
                else:
                    # no association can be made
                    # this possible match involves either a dummy cost value or a dummy (group,outcome) pair
                    prob = 0

                probMatrix[cvIdx].append(prob)

        costMatrix = munkres.make_cost_matrix(probMatrix, lambda cost: probMultiplier - cost)
        m = munkres.Munkres()
        #    print probMatrix
        #    print costMatrix
        indices = m.compute(costMatrix)
        # threshold is (1/2)^4
        # threshold = 0.0625 * probMultiplier
        threshold = 0.0001 * probMultiplier
        #    threshold = 0.25 * probMultiplier

        for cvIdx, goIdx in indices:
            if cvIdx < nCostValues and goIdx < nGroupOutcomePairs:
                prob = probMatrix[cvIdx][goIdx]
                if prob > threshold:
                    # this quantity and mention should be associated
                    prob = float(prob) / probMultiplier
                    om = costValueList[cvIdx]
                    (group, outcome) = goPairs[goIdx]
                    self.linkOutcomeMeasurementAssociations(om, group, outcome, prob)

gmm_model = sklmix.GMM(n_components=3, covariance_type='full')
gmm_model.fit(iris[['PW', 'PL', 'SW']])
yhat = gmm_model.predict(iris[['PW', 'PL', 'SW']])
crosstab = pd.crosstab(iris['Type'], yhat, rownames=['true'], colnames=['predicted'])
print crosstab

# <headingcell level=4>

# Align the confusion matrix with a non-standard package

# <codecell>

import munkres
import sys
m = munkres.Munkres()
cost = munkres.make_cost_matrix(crosstab.values.tolist(), lambda x : sys.maxint - x)
align = m.compute(cost)
print align, '\n'

permute = [x[1] for x in align]
new_label = np.argsort(permute)
yhat_new = new_label[yhat]
print pd.crosstab(iris['Type'], yhat_new, rownames=['true'], colnames=['predicted'])

# <headingcell level=4>

# Bridging the gap with Rpy2

# <codecell>

from rpy2.robjects import r