import numpy as np
class KMAlgorithm:
    def __init__(self, weight_matrix):
        """
        初始化KM算法
        :param weight_matrix: 权重矩阵（n×n），numpy数组
        """
        self.n = weight_matrix.shape[0]  # 顶点数
        self.weight = weight_matrix      # 权重矩阵
        self.lx = np.zeros(self.n)       # 左集合顶标
        self.ly = np.zeros(self.n)       # 右集合顶标
        self.match_to = -np.ones(self.n, dtype=int)  # 右集合匹配的左顶点
        self.visited_x = np.zeros(self.n, dtype=bool)  # 左顶点访问标记
        self.visited_y = np.zeros(self.n, dtype=bool)  # 右顶点访问标记
        self.slack = np.zeros(self.n)    # 松弛量，优化查找效率
    def find_augmenting_path(self, x):
        """
        递归寻找增广路
        :param x: 当前左顶点索引
        :return: 是否找到增广路
        """
        self.visited_x[x] = True
        for y in range(self.n):
            if not self.visited_y[y]:
                # 计算当前顶标和与权重的差值
                diff = self.lx[x] + self.ly[y] - self.weight[x][y]
                if abs(diff) < 1e-6:  # 差值足够小，视为相等（处理浮点误差）
                    self.visited_y[y] = True
                    # 如果y未匹配，或y的匹配顶点能找到新的增广路
                    if self.match_to[y] == -1 or self.find_augmenting_path(self.match_to[y]):
                        self.match_to[y] = x
                        return True
                else:
                    # 更新松弛量
                    if self.slack[y] > diff:
                        self.slack[y] = diff
        return False
    def solve(self):
        """
        执行KM算法，返回最优匹配结果和总权重
        :return: 匹配结果（左顶点→右顶点）、总权重
        """
        # 步骤1：初始化左集合顶标为每行最大值
        for i in range(self.n):
            self.lx[i] = np.max(self.weight[i])
        
        # 步骤2：为每个左顶点寻找增广路
        for x in range(self.n):
            # 初始化松弛量为无穷大
            self.slack = np.ones(self.n) * np.inf
            while True:
                # 重置访问标记
                self.visited_x = np.zeros(self.n, dtype=bool)
                self.visited_y = np.zeros(self.n, dtype=bool)
                # 找到增广路，跳出循环
                if self.find_augmenting_path(x):
                    break
                # 未找到，调整顶标
                d = np.min(self.slack[~self.visited_y])  # 计算松弛量d
                # 已访问的左顶点顶标减d
                self.lx[self.visited_x] -= d
                # 已访问的右顶点顶标加d
                self.ly[self.visited_y] += d
                # 更新松弛量
                self.slack[~self.visited_y] -= d
        
        # 计算总权重和匹配结果
        total_weight = 0
        match_result = {}
        for y in range(self.n):
            x = self.match_to[y]
            if x != -1:
                total_weight += self.weight[x][y]
                match_result[x] = y
        
        return match_result, total_weight
# 测试KM算法
if __name__ == "__main__":
    # 测试权重矩阵（岗位-候选人）
    test_weight = np.array([
        [92, 45, 60],
        [40, 95, 55],
        [58, 50, 93]
    ])
    km = KMAlgorithm(test_weight)
    match, total = km.solve()
    print("最优匹配结果（左顶点索引→右顶点索引）：", match)
    print("总匹配度：", total)

import numpy as np
from scipy.spatial.distance import cosine
import networkx as nx
import matplotlib.pyplot as plt
from transformers import AutoTokenizer, AutoModel
import torch
from modelscope.hub.snapshot_download import snapshot_download
# 设置中文字体
plt.rcParams['font.sans-serif'] = ['SimHei', 'Arial']
plt.rcParams['axes.unicode_minus'] = False
# ---------------------- 配置项 ----------------------
cache_dir = "D:\\modelscope\\hub"
model_name = "google-bert/bert-base-chinese"
# 下载模型到本地
local_model_path = snapshot_download(
    model_name,
    cache_dir=cache_dir,
    revision="master"
)
# 加载模型和分词器
tokenizer = AutoTokenizer.from_pretrained(local_model_path)
model = AutoModel.from_pretrained(local_model_path)
# ---------------------- KM算法 ----------------------
class KMAlgorithm:
    def __init__(self, weight_matrix):
        self.n = weight_matrix.shape[0]
        self.weight = weight_matrix
        self.lx = np.zeros(self.n)
        self.ly = np.zeros(self.n)
        self.match_to = -np.ones(self.n, dtype=int)
        self.visited_x = np.zeros(self.n, dtype=bool)
        self.visited_y = np.zeros(self.n, dtype=bool)
        self.slack = np.zeros(self.n)
    def find_augmenting_path(self, x):
        self.visited_x[x] = True
        for y in range(self.n):
            if not self.visited_y[y]:
                diff = self.lx[x] + self.ly[y] - self.weight[x][y]
                if abs(diff) < 1e-6:
                    self.visited_y[y] = True
                    if self.match_to[y] == -1 or self.find_augmenting_path(self.match_to[y]):
                        self.match_to[y] = x
                        return True
                else:
                    if self.slack[y] > diff:
                        self.slack[y] = diff
        return False
    def solve(self):
        for i in range(self.n):
            self.lx[i] = np.max(self.weight[i])
        
        for x in range(self.n):
            self.slack = np.ones(self.n) * np.inf
            while True:
                self.visited_x = np.zeros(self.n, dtype=bool)
                self.visited_y = np.zeros(self.n, dtype=bool)
                if self.find_augmenting_path(x):
                    break
                d = np.min(self.slack[~self.visited_y])
                self.lx[self.visited_x] -= d
                self.ly[self.visited_y] += d
                self.slack[~self.visited_y] -= d
        
        total_weight = 0
        match_result = {}
        for y in range(self.n):
            x = self.match_to[y]
            if x != -1:
                total_weight += self.weight[x][y]
                match_result[x] = y
        
        return match_result, total_weight
# ---------------------- 大模型语义对齐 ----------------------
def get_embedding(text):
    """
    使用本地BERT模型获取文本向量
    :param text: 输入文本
    :return: numpy向量
    """
    text = text.replace("\n", " ")
    try:
        inputs = tokenizer(text, return_tensors="pt", padding=True, truncation=True, max_length=512)
        with torch.no_grad():
            outputs = model(**inputs)
        # 取[CLS] token的向量作为文本的整体嵌入
        embedding = outputs.last_hidden_state[:, 0, :].squeeze().numpy()
        return embedding
    except Exception as e:
        print(f"获取向量失败：{e}")
        return None
def calculate_similarity(vec1, vec2):
    """
    计算两个向量的余弦相似度
    :param vec1: 向量1
    :param vec2: 向量2
    :return: 相似度分数 (0-100)
    """
    if vec1 is None or vec2 is None:
        return 0.0
    similarity = 1 - cosine(vec1, vec2)
    return round(similarity * 100, 2)
# ---------------------- 可视化 ----------------------
def visualize_matching(jobs, candidates, match_result):
    """
    可视化匹配结果
    :param jobs: 岗位列表
    :param candidates: 候选人列表
    :param match_result: 匹配结果（岗位索引→候选人索引）
    """
    # 创建二分图
    G = nx.Graph()
    # 添加左集合节点（岗位）
    job_nodes = [f"岗位{i+1}: {jobs[i][:40]}..." for i in range(len(jobs))]
    # 添加右集合节点（候选人）
    cand_nodes = [f"候选人{chr(65+i)}: {candidates[i][:40]}..." for i in range(len(candidates))]
    G.add_nodes_from(job_nodes, bipartite=0)
    G.add_nodes_from(cand_nodes, bipartite=1)
    
    # 添加所有边（非匹配边为灰色，匹配边为红色）
    all_edges = []
    match_edges = []
    for i, job_node in enumerate(job_nodes):
        for j, cand_node in enumerate(cand_nodes):
            all_edges.append((job_node, cand_node))
            if i in match_result and match_result[i] == j:
                match_edges.append((job_node, cand_node))
    
    # 绘制图形
    pos = nx.bipartite_layout(G, job_nodes)
    plt.figure(figsize=(12, 8))
    # 绘制非匹配边
    nx.draw_networkx_edges(G, pos, edgelist=all_edges, edge_color="gray", alpha=0.3, width=1)
    # 绘制匹配边
    nx.draw_networkx_edges(G, pos, edgelist=match_edges, edge_color="red", alpha=1.0, width=2)
    # 绘制节点
    nx.draw_networkx_nodes(G, pos, nodelist=job_nodes, node_color="lightblue", node_size=2000)
    nx.draw_networkx_nodes(G, pos, nodelist=cand_nodes, node_color="lightgreen", node_size=2000)
    # 绘制节点标签
    nx.draw_networkx_labels(G, pos, font_size=8)
    # 隐藏坐标轴
    plt.axis("off")
    plt.title("岗位-候选人最优匹配结果", fontsize=14, weight="bold")
    plt.tight_layout()
    plt.show()
# ---------------------- 主函数 ----------------------
if __name__ == "__main__":
    # 1. 数据准备
    jobs = [
        "负责用户增长和活动运营，要求良好的沟通能力、文案能力，有1-3年运营经验",
        "负责后端开发，要求熟练掌握Python、MySQL，有接口开发经验，逻辑思维强",
        "负责产品需求分析和原型设计，要求用户思维、跨部门沟通能力，有产品规划经验"
    ]
    candidates = [
        "1年运营经验，擅长文案撰写和用户活动策划，沟通能力良好",
        "3年Python开发经验，熟悉MySQL，做过多个接口开发项目，逻辑思维强",
        "2年产品经验，擅长需求分析和原型设计，有跨部门协调经验，用户思维突出"
    ]
    
    # 2. 文本向量化
    print("正在获取文本向量...")
    job_embeddings = [get_embedding(job) for job in jobs]
    candidate_embeddings = [get_embedding(candidate) for candidate in candidates]
    
    # 3. 计算相似度矩阵
    print("正在计算相似度矩阵...")
    similarity_matrix = np.zeros((len(jobs), len(candidates)))
    for i, job_vec in enumerate(job_embeddings):
        for j, cand_vec in enumerate(candidate_embeddings):
            similarity_matrix[i][j] = calculate_similarity(job_vec, cand_vec)
    print("相似度矩阵：")
    print(similarity_matrix)
    
    # 4. KM算法求解最优匹配
    print("正在求解最优匹配...")
    km = KMAlgorithm(similarity_matrix)
    match_result, total_weight = km.solve()
    print("最优匹配结果（岗位索引→候选人索引）：", match_result)
    print(f"总匹配度：{total_weight}")
    
    # 5. 结果可视化
    print("正在绘制匹配结果图...")
    visualize_matching(jobs, candidates, match_result)
    
    # 6. 输出可读的匹配结果
    print("\n=== 最终匹配结果 ===")
    job_names = ["运营岗", "技术岗", "产品岗"]
    cand_names = ["候选人A", "候选人B", "候选人C"]
    for job_idx, cand_idx in match_result.items():
        print(f"{job_names[job_idx]} → {cand_names[cand_idx]}（匹配度：{similarity_matrix[job_idx][cand_idx]}）")