def main(tutors, players):
  scores = []
  #create cross-scores
  for tutor in tutors:
    # create the score array for each tutor to every player
    scores.append([ getModFLF(tutor, player)*getBaseFLF(tutor,player) for player in players ])
  # print the matrix
  #pretty_print(scores)

  # find max
  maxscore = max(max(row) for row in scores)
  # turn the matrix into a min-problem
  for row in scores:
    for idx,col in enumerate(row):
      row[idx] = maxscore-col
  # using munkres (copy of tutorial)
  m = Munkres()
  indexes = m.compute(scores)

#  pretty_print(scores)
  total = 0
  print "[[Tutor ::: Player]]"
  for row, col in indexes:
    total += scores[row][col]
    print '{0} ::: {1}'.format(tutors[row],players[col])
  print 'total FLF: {0}'.format(maxscore*len(tutors)-total)

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 p345():
    A = [[  7, 53, 183, 439, 863, 497, 383, 563, 79, 973, 287, 63, 343, 169, 583],
        [627, 343, 773, 959, 943, 767, 473, 103, 699, 303, 957, 703, 583, 639, 913],
        [447, 283, 463, 29, 23, 487, 463, 993, 119, 883, 327, 493, 423, 159, 743],
        [217, 623, 3, 399, 853, 407, 103, 983, 89, 463, 290, 516, 212, 462, 350],
        [960, 376, 682, 962, 300, 780, 486, 502, 912, 800, 250, 346, 172, 812, 350],
        [870, 456, 192, 162, 593, 473, 915, 45, 989, 873, 823, 965, 425, 329, 803],
        [973, 965, 905, 919, 133, 673, 665, 235, 509, 613, 673, 815, 165, 992, 326],
        [322, 148, 972, 962, 286, 255, 941, 541, 265, 323, 925, 281, 601, 95, 973],
        [445, 721, 11, 525, 473, 65, 511, 164, 138, 672, 18, 428, 154, 448, 848],
        [414, 456, 310, 312, 798, 104, 566, 520, 302, 248, 694, 976, 430, 392, 198],
        [184, 829, 373, 181, 631, 101, 969, 613, 840, 740, 778, 458, 284, 760, 390],
        [821, 461, 843, 513, 17, 901, 711, 993, 293, 157, 274, 94, 192, 156, 574],
        [ 34, 124, 4, 878, 450, 476, 712, 914, 838, 669, 875, 299, 823, 329, 699],
        [815, 559, 813, 459, 522, 788, 168, 586, 966, 232, 308, 833, 251, 631, 107],
        [813, 883, 451, 509, 615, 77, 281, 613, 459, 205, 380, 274, 302, 35, 805]]

    for r in range(len(A)):
        for c in range(len(A[0])):
            A[r][c] *= -1

    from munkres import Munkres, print_matrix

    m = Munkres()
    indexes = m.compute(A)
    total = 0
    for row, column in indexes:
        value = A[row][column]
        total += value
    return -total

def hun(costMatrix):

    # Check first, if costmatrix is not empty
    if costMatrix.shape==(0,0):
        return []

    # Create squared temporary matrix
    tmpMatrix = numpy.copy(costMatrix)
    tmpMatrix = makeSquareWithNegValues(tmpMatrix)
    sqCostMatrix = numpy.copy(tmpMatrix)
    sqCostMatrix[tmpMatrix==-1]=10e10

    # Solve ASP on the temporary matrix
    m=Munkres()
    i=m.compute(sqCostMatrix)


    # Create resultin matrix that contains ones at matching
    # objects and remove all excluded matches
    binMatrix = numpy.zeros( tmpMatrix.shape,dtype=bool )
    for x,y in i:
        if tmpMatrix[x,y]==-1:
            continue
        binMatrix[x,y]=True

    return binMatrix

def match_rows(X, Y):
    """
    Permute the rows of _X_ to minimize error with Y
    @params X numpy.array - input matrix
    @params Y numpy.array - comparison matrix
    @return numpy.array - X with permuted rows
    """
    n, d = X.shape
    n_, d_ = Y.shape
    assert n == n_ and d == d_

    # Create a weight matrix to compare the two
    W = zeros((n, n))
    for i, j in it.product(xrange(n), xrange(n)):
        # Cost of 'assigning' j to i.
        W[i, j] = norm(X[j] - Y[i])

    matching = Munkres().compute(W)
    matching.sort()
    _, rowp = zip(*matching)
    rowp = array(rowp)
    # Permute the rows of B according to Bi
    X_ = X[rowp]

    return X_

    def __init__(self, G1, G2, nattr='weight', eattr='weight', lamb = 0.5):
        G1, G2 = sorted([G1, G2], key=lambda x: len(x))
        csim = gs.tacsim_combined_in_C(G1, G2, node_attribute=nattr, edge_attribute=eattr, lamb=lamb)
        self.csim = csim / np.sqrt(((csim * csim).sum())) # to ensure valid structural distance
        self.g1 = G1
        self.g2 = G2

        m = Munkres()
        cdist = (1 - self.csim).tolist()
        self.matching = m.compute(cdist)

        nmap = {}
        def _gen_nnid(node):
            if node not in nmap:
                nmap[node] = len(nmap)
            return nmap[node]

        self.mesos = nx.DiGraph()
        for (e1_idx, e2_idx) in self.matching:
            e1 = G1.edges()[e1_idx]
            e2 = G2.edges()[e2_idx]
            ns = _gen_nnid(e1[0])
            nt = _gen_nnid(e1[1])
            self.mesos.add_edge(ns, nt)
            self.mesos.edge[ns][nt][eattr] = 0.5 * (G1.edge[e1[0]][e1[1]][eattr] + G2.edge[e2[0]][e2[1]][eattr])
            self.mesos.node[ns][nattr] = 0.5 * (G1.node[e1[0]][nattr] + G2.node[e2[0]][nattr])
            self.mesos.node[nt][nattr] = 0.5 * (G1.node[e1[1]][nattr] + G2.node[e2[1]][nattr])

def match_rows_sign(X, Y):
    """
    Permute the rows of _X_ to minimize error with Y, ignoring signs of the columns
    @params X numpy.array - input matrix
    @params Y numpy.array - comparison matrix
    @return numpy.array - X with permuted rows
    """
    n, d = X.shape
    n_, d_ = Y.shape
    assert n == n_ and d == d_

    # Create a weight matrix to compare the two
    W = zeros((n, n))
    for i, j in it.product(xrange(n), xrange(n)):
        # Cost of 'assigning' j to i.
        W[i, j] = min(norm(X[j] - Y[i]), norm(X[j] + Y[i]))

    matching = Munkres().compute(W)
    matching.sort()
    _, rowp = zip(*matching)
    rowp = array(rowp)
    # Permute the rows of B according to Bi
    X_ = X[rowp]
    # Change signs to minimize loss
    for row in xrange(n):
        if norm(X_[row] + Y[row]) < norm(X_[row] - Y[row]):
            X_[row] *= -1

    return X_

def fix_parameters(true, guess, weights):
    """Find a column permutation of guess parameters that matches true parameters most closely (i.e. min |A
    - B|_F) also apply this to weights"""

    # The rows of A and B form a weighted bipartite graph. The weights
    # are computed using the vector_matching algorithm.
    # We need to find their minimal matching.
    assert true.shape == guess.shape

    d, k = true.shape
    m = Munkres()

    # Create the weight matrix
    W = sc.zeros((k, k))
    for i in xrange(k):
        for j in xrange(k):
            # Best matching between A and B
            W[i, j] = norm(true.T[i] - guess.T[j])

    matching = m.compute(W)
    matching.sort()
    _, colp = zip(*matching)
    colp = array(colp)
    # Permute the rows of B according to Bi
    guess = guess[:, colp]
    weights = weights[colp]

    return weights, guess

def getFileSim(fileA,fileB,alpha,beta):  	#to find the similarity of two files
	File1=open(dirname+'/'+fileA, "r")
	File2=open(dirname+'/'+fileB, "r")
	content1=File1.readlines()
	flag=0
	content2=File2.readlines()
	if len(content1) > len(content2):
		flag=1
		content1,content2 = content2,content1
	sim=[]
	for sen_A in content1:
		temp = []
		sen_A = sen_A.lower()
		for sen_B in content2:
			sen_B = sen_B.lower()
			temp.append(senSim(sen_A,sen_B,alpha))
		sim.append(temp)
	for i in range(len(sim))		 #to make it a maximum cost problem
		for j in range(len(sim[i])):
			sim[i][j] = 1.0-sim[i][j]
	m=Munkres()
	result_matrix=m.compute(sim)		#implementing hungarian 
	maxSimMatrix = []
	for row,column in result_matrix:
		if	sim[row][column]!=1.0:
			if flag==1:
				row,column=column,row
			maxSimMatrix.append([row,column])	#storing which lines are matched
	FileSim=float(len(maxSimMatrix))/(len(content1))
	
	if FileSim<beta:
		FileSim = 0
	return (FileSim, maxSimMatrix)

def match_parameters(p, q, method="munkres", discard_misses=False):
    """
    Match two sets of parameters.
    TODO: finish greedy
    """
    logger.info("Matching with method %s" % method)
    assert p.shape[1] == q.shape[1], (
        "Shapes do not match (%s vs %s)" % (p.shape, q.shape)
    )

    match_size = min(p.shape[0], q.shape[0])
    corrs = np.corrcoef(p, q)[match_size:, :match_size]
    corrs[np.isnan(corrs)] = 0

    if method == "munkres":
        m = Munkres()
        cl = 1 - np.abs(corrs)
        if (cl.shape[0] > cl.shape[1]):
            indices = m.compute(cl.T)
        else:
            indices = m.compute(cl)
            indices = [(i[1], i[0]) for i in indices]

    elif method == "greedy":
        q_idx = []
        raise NotImplementedError("Greedy not supported yet.")
        for c in range(q.shape[0]):
            idx = corrs[c, :].argmax()
            q_idx.append(idx)
            corrs[:,idx] = 0

    else:
        raise NotImplementedError("%s matching not supported" % method)

    return indices

def accuracy(labels_true, labels_pred):
    labels_true, labels_pred = check_clusterings(labels_true, labels_pred)
    n_samples = labels_true.shape[0]
    classes = np.unique(labels_true)
    clusters = np.unique(labels_pred)
    # Special limit cases: no clustering since the data is not split;
    # or trivial clustering where each document is assigned a unique cluster.
    # These are perfect matches hence return 1.0.
    if (classes.shape[0] == clusters.shape[0] == 1
            or classes.shape[0] == clusters.shape[0] == 0
            or classes.shape[0] == clusters.shape[0] == len(labels_true)):
        return 1.0
    
    # print "accuracy testing..."
    contingency = contingency_matrix(labels_true, labels_pred) #Type: <type 'numpy.ndarray'>:rows are clusters, cols are classes
    contingency = -contingency
    #print contingency
    contingency = contingency.tolist()
    m = Munkres() # Best mapping by using Kuhn-Munkres algorithm
    map_pairs = m.compute(contingency) #best match to find the minimum cost
    sum_value = 0
    for key,value in map_pairs:
        sum_value = sum_value + contingency[key][value]
    
    return float(-sum_value)/n_samples

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 loss1(usersPerCircle, usersPerCircleP):
  #psize: either the number of groundtruth, or the number of predicted circles (whichever is larger)
  psize = max(len(usersPerCircle),len(usersPerCircleP)) # Pad the matrix to be square
  # mm: matching matrix containing costs of matching groundtruth circles to predicted circles.
  #     mm[i][j] = cost of matching groundtruth circle i to predicted circle j
  mm = numpy.zeros((psize,psize))
  # mm2: copy of mm since the Munkres library destroys the data during computation
  mm2 = numpy.zeros((psize,psize))
  for i in range(psize):
    for j in range(psize):
      circleP = set() # Match to an empty circle (delete all users)
      circle = set() # Match to an empty circle (add all users)
      if (i < len(usersPerCircleP)):
        circleP = usersPerCircleP[i]
      if (j < len(usersPerCircle)):
        circle = usersPerCircle[j]
      nedits = len(circle.union(circleP)) - len(circle.intersection(circleP)) # Compute the edit distance between the two circles
      mm[i][j] = nedits
      mm2[i][j] = nedits

  if psize == 0:
    return 0 # Edge case in case there are no circles
  else:
    m = Munkres()
    #print mm2 # Print the pairwise cost matrix
    indices = m.compute(mm) # Compute the optimal alignment between predicted and groundtruth circles
    editCost = 0
    for row, column in indices:
      #print row,column # Print the optimal value selected by matching
      editCost += mm2[row][column]
    return int(editCost)

def __assign_labels_to_clusters__(assignment, labels, clusters, clusts_labels):
    cost_matrix = gen_assignment_cost_matrix(assignment, labels, clusters, clusts_labels)
    munkres = Munkres()
    assignment_list = munkres.compute(cost_matrix)
    # assignment_list = [(i,i) for i in xrange(len(clusters))] #for debugging
    assigned_clusts_labels = dict(assignment_list)  # dictionary {cluster_no: assigned_label_no}
    return assigned_clusts_labels

def Objmatch(objy,objx,ref,refc,L,W,im,length):
    global D_limit_s
    dmtx = np.zeros((L,W))
    cmtx = np.zeros((L,W))
    Wd = 0.5   #weight of distance
    Wc = 1-Wd  #weight of color
    
    for i in range(L):
        dmtx[i,:] =((objy - ref[i][0])**2+(objx - ref[i][1])**2).T
        cmtx[i,:] = Color_Dif(im,objx,objy,refc[i],length[i]) 

    dmtx = dmtx/diag # normalize the distance by divid diag
    dmtx[dmtx>D_limit_s] = 10**6    
    cmtx = cmtx*Wc + dmtx*Wd
    tmp = copy.deepcopy(cmtx)     
    m = Munkres()
    if L<=W:
        indexes = m.compute(cmtx)
    else:     # len(ori) > # live_blobs
        indexes = m.compute(cmtx.T)
        indexes = [(s[1],s[0]) for s in indexes]
    
    D_idx = []
    if vid_idx>=0:
        for i in range(len(indexes))[::-1]:
            if tmp[indexes[i][0],indexes[i][1]]>10**5:
                D_idx.append(i)
                indexes.pop(i)

    return indexes,D_idx  

 def find_ambiguous_mapping(self, res, aa,
                            non_ambiguous_mapping,
                            previous=False):
     from munkres import Munkres
     from numpy import fabs, sum, delete
     
     total_costs = None
     mapping = []
     ambiguous_keys = []
     ambiguous_shifts = []
     res_shifts, res_keys = res.get_carbons(previous)
     aa_shifts, aa_keys = aa.get_carbons()
     
     for i, j in non_ambiguous_mapping:
         if j in aa_keys:
             k = list(aa_keys).index(j)
             aa_shifts = delete(aa_shifts, k)
             aa_keys = delete(aa_keys, k)
     for i, key in enumerate(res_keys):
         if self.ambiguous(key, previous):
             ambiguous_keys.append(key)
             ambiguous_shifts.append(res_shifts[i])
             
     if len(aa_keys) > 0 and len(ambiguous_shifts) > 0:
         costs = fabs(subtract.outer(ambiguous_shifts, aa_shifts))
         munkres = Munkres()
         result = munkres.compute(costs * 1.)
         for i, j in result:
             mapping.append((ambiguous_keys[i], aa_keys[j]))
         
     return mapping

def match(img_location, features, cluster):
    img = cv2.imread(img_location)

    detector = cv2.FeatureDetector_create("SIFT")
    descriptor = cv2.DescriptorExtractor_create("SIFT")
    
    keypoints = detector.detect(img)
    keypoints = sorted(keypoints, key=lambda x: -x.response)
    keypoints, img_features = descriptor.compute(img, keypoints[0:5])
    img_features = img_features.tolist()

    m = Munkres()

    distance = {}
    for filename in cluster:
        distance[filename] = 0
        fea = features[filename]
        matrix = [[0 for i in range(5)] for j in range(5)]
        for i in range(5):
            for j in range(5):
                if matrix[j][i] != 0:
                    matrix[i][j] = matrix[j][i]
                    continue
                try:
                    matrix[i][j] = np.linalg.norm( array(img_features[i]) - array(fea[j]) )
                except:
                    matrix[i][j] = 10000
        indexes = m.compute(matrix)
        for row, column in indexes:
            distance[filename] += matrix[row][column]

    results = sorted(cluster, key = lambda x: distance[x])
    # results = features.keys()
    return results, distance

def assign_projects():
    projects = Project.query.join(Priority).order_by(Project.id).all()
    users = User.query.join(Priority).order_by(User.id).all()
    user_ids = [user.id for user in users]
    default_priority = len(projects) + 1
    matrix = []

    for project in projects:
        priority_query = db.session.query(User.id, Priority.priority).\
            outerjoin(Priority, db.and_(User.id == Priority.user_id,
                                        Priority.project_id == project.id)).\
            filter(User.id.in_(user_ids)).\
            order_by(User.id).all()
        priorities = [user_priority_tuple.priority
                      if user_priority_tuple.priority is not None
                      else default_priority
                      for user_priority_tuple in priority_query]
        matrix.append(priorities)

    if len(matrix) != 0:
        db.session.query(Project).update({Project.assignee_id: None})
        m = Munkres()
        indexes = m.compute(matrix)
        for row, column in indexes:
            projects[row].assignee_id = user_ids[column]
        db.session.commit()

    flash('Project assignments updated.')
    return redirect(url_for('show_index'))

    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 closest_permuted_matrix( A, B ):
    """Find a _row_ permutation of B that matches A most closely (i.e. min |A
    - B|_F)"""

    # The rows of A and B form a weighted bipartite graph. The weights
    # are computed using the vector_matching algorithm.
    # We need to find their minimal matching.
    assert( A.shape == B.shape )

    n, _ = A.shape
    m = Munkres()

    # Create the weight matrix
    W = sc.zeros( (n, n) )
    for i in xrange( n ):
        for j in xrange( n ):
            # Best matching between A and B
            W[i, j] = norm(A[i] - B[j])

    matching = m.compute( W )
    matching.sort()
    _, rowp = zip(*matching)
    rowp = array( rowp )
    # Permute the rows of B according to Bi
    B_ = B[ rowp ]

    return B_