scheduling_algorithm_didi/KM.py

import numpy as np
from scipy.optimize import linear_sum_assignment

class KM():
    def __init__(self, graph):
        self.gragh = graph
        self.gragh2 = graph
        print(graph)
        a = len(graph)
        b = len(graph[0])
        print(a)
        print(b)
        self.n = max(a,b)
        if a > b:
            graph = [row + [0] * (a - b) for row in graph]
        elif a < b :
            for i in range(b-a):
                graph = graph + [[0] * b]
        self.gragh = np.array(graph)
        # self.left_label = np.max(self.gragh,axis=1)
        # self.right_label = np.zeros(self.n)

    def compute(self):
        self.gragh = -self.gragh
        print(self.gragh.shape)
        row,col = linear_sum_assignment(self.gragh)
        print("行坐标:", row, "列坐标:", col, "最大组合:", self.gragh[row, col])
        row,col = linear_sum_assignment(-np.array(self.gragh2))
        print("行坐标:", row, "列坐标:", col, "最大组合:", self.gragh[row, col])
        return [(i,j)for i,j,value in zip(row,col,self.gragh[row,col]) if value]