import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import random
import itertools
from itertools import *
from docplex.mp.model import Model
# from generate import GenerateNetwork
import copy
from functools import partial
import multiprocessing
from collections import OrderedDict

node_num = 60
sd_num = 30
pro = 90
remaining_num = 6 
β = 0.1



max_slot_num = 30
the_num = 50
# loop_num = 20
Reduction_factor = 50



class QNetwork: 
    def __init__(self, path_for_getxt, remaining_num_changing, node_num_changing):
        self.maxloop = []
        self.nodeList = []
        self.linkListProbability = []
        self.elMatrix = np.zeros((remaining_num_changing, node_num_changing))
        # self.el_success_looping = np.zeros((remaining_num_changing, node_num_changing))
        self.ec_selectNodes = {}
        self.sdList = []
        self.sdList_all = []
        self.elWaste = 0
        self.ec_counter = 0
        self.remainingNumchanging = remaining_num_changing

        # self.window_size = 3
        try:
            self.readDataFromTxt(path_for_getxt)
        except:
            print("读取错误")

    class Link:
        def __init__(self, startNode, endNode, probability):
            self.startNode = startNode
            self.endNode = endNode
            self.probability = probability

    class Node:
        def __init__(self, nodeID):
            self.nodeID = nodeID
            self.adjacentNodes = []
            self.selectNodeID = 0
            self.epsFlag = 0

    def initSelectNodeID(self):
        # 24.1.13 23：43 可能要在这里对el_success做一个初始化，
        # el_success的同步更新，并初始化一个以loop为key的字典  
    # 更新每个eps节点的selectNodeID
        for node in self.nodeList:
            if node.epsFlag == 1:
                # 随机选择一个相邻节点的ID作为selectNodeID，或保持为0
                if node.adjacentNodes:
                    excluded_values = self.get_excluded_values(node.nodeID)
                    valid_nodes = [n for n in node.adjacentNodes if n not in excluded_values]
                    # print(valid_nodes)
                    if valid_nodes:
                        node.selectNodeID = random.choice(valid_nodes) 
                        print(f"eps {node.nodeID} selected neighbor {node.selectNodeID}")
                        self.elMatrix[self.remainingNumchanging-1][node.nodeID-1] = node.selectNodeID

    def old_updateSelectNodeID(self):
    # 更新每个eps节点的selectNodeID
        if_change = False
        # 待修改 ep待建立跳数计算函数   需要根据小el状态矩阵去计算
        sd_pair_step_num_grade_down = self.old_get_ep_step()

        # for ep_link in sd_pair_step_num_grade_down.keys():
        #     print("there is ep_link")
        #     for link_1 in ep_link:
        #         print(link_1.startNode, link_1.endNode)

        for node in self.nodeList:
            if node.epsFlag == 1:
                # print(f"循环到node{node.nodeID},这是一个eps")
                link = {}
                for neighbor in node.adjacentNodes:
                    for linkProbability in self.linkListProbability:
                        if linkProbability.startNode == node.nodeID and linkProbability.endNode == neighbor:
                            link[neighbor] = linkProbability         
                        elif linkProbability.startNode == neighbor and linkProbability.endNode == node.nodeID:
                            link[neighbor] = linkProbability
                ec_counter = {}
                # excluded_values = self.get_excluded_values(node.nodeID)
                # print(f"已经得到node{node.nodeID}需要避开的neighbor：{excluded_values}")
                
                neighbor_pro = {}
                # 在这个对邻居节点的遍历过程中，需要在每一次尝试之后还原记录矩阵
                for neighbor in node.adjacentNodes:
                    # self.el_success_looping = copy.deepcopy(elMatrix)

                    # if neighbor not in excluded_values:
                    if True:
                        mark = self.elMatrix[self.remainingNumchanging-1][node.nodeID-1]

                        self.elMatrix[self.remainingNumchanging-1][node.nodeID-1] = neighbor
                        ec_counter[neighbor] = self.old_calculateEcCount()
                        
                        self.elMatrix[self.remainingNumchanging-1][node.nodeID-1] = mark

                        weight = len(sd_pair_step_num_grade_down)
                        for ep_links in sd_pair_step_num_grade_down.keys():
                            weight *= 1/Reduction_factor # 这一步很关键，修正了所有匹配到的第一个link权重都一样的问题
                            if link[neighbor] in ep_links:
                                ec_counter[neighbor] += weight


                #找到ec_counter[neighbor] 中值最大的键
                if ec_counter:
                    # max_value = max(ec_counter.values())
                    # max_elements = [key for key, value in ec_counter.items() if value == max_value]
                    # # 如果有多个具有最大值的元素，随机选择一个
                    # selected_node = random.choice(max_elements)
                    # node.selectNodeID = selected_node

                    node.selectNodeID = max(ec_counter, key = ec_counter.get)
                    mark_for_check = self.elMatrix[self.remainingNumchanging-1][node.nodeID-1]
                    if node.selectNodeID != mark_for_check:
                        if_change = True
                        self.elMatrix[self.remainingNumchanging-1][node.nodeID-1] = node.selectNodeID
                    self.ec_selectNodes[matrix_to_tuple(self.elMatrix)] = ec_counter[node.selectNodeID]

        return if_change
# 如何把矩阵作为键值对的key保存进字典

                # print(f"找到最大值对应的neighbor{node.selectNodeID},已经修改了self.elMatrix")

    def updateSelectNodeID(self, epList, eps_ep_list, eps_ep_nodes, eps_sd_pair_step_num_grade_down, old_max = 0):
    # 更新每个eps节点的selectNodeID
        if_change = False
        
        # epList = self.get_epList()
        # eps_ep_list, eps_ep_nodes = self.get_eps_ep_list(epList)
        
        # eps_sd_pair_step_num_grade_down = []
        # for node in self.nodeList:
        #     if node.epsFlag == 1:
        #         eps_sd_pair_step_num_grade_down[node.nodeID] = self.get_ep_step(node.nodeID, eps_ep_list, epList)

        arr = [i for i in range(len(self.nodeList))]
        random.shuffle(arr)

        for i in arr:
            node = self.getNode(i+1)
            if node.epsFlag == 1:
                # print(f"循环到node{node.nodeID},这是一个eps")
                sd_pair_step_num_grade_down = eps_sd_pair_step_num_grade_down[node.nodeID]

                link = {}
                for neighbor in node.adjacentNodes:
                    for linkProbability in self.linkListProbability:
                        if linkProbability.startNode == node.nodeID and linkProbability.endNode == neighbor:
                            link[neighbor] = linkProbability         
                        elif linkProbability.startNode == neighbor and linkProbability.endNode == node.nodeID:
                            link[neighbor] = linkProbability
                ec_counter = {}

                # 在这个对邻居节点的遍历过程中，需要在每一次尝试之后还原记录矩阵
                for neighbor in node.adjacentNodes:

                    if True:
                        mark = self.elMatrix[self.remainingNumchanging-1][node.nodeID-1]

                        self.elMatrix[self.remainingNumchanging-1][node.nodeID-1] = neighbor
                        ec_counter[neighbor] = self.calculateEcCount(node.nodeID, eps_ep_list, eps_ep_nodes, epList)
                        
                        self.elMatrix[self.remainingNumchanging-1][node.nodeID-1] = mark

                        weight = len(sd_pair_step_num_grade_down)
                        
                        # print(f"length of sd_pair_step_num_grade_down:{weight} ")
                        for ep_links in sd_pair_step_num_grade_down.keys():
                            weight *= 1/Reduction_factor # 这一步很关键，修正了所有匹配到的第一个link权重都一样的问题
                            if link[neighbor] in ep_links:
                                ec_counter[neighbor] += weight
                    
                    # print(f"eps {node.nodeID} with neighbor {neighbor} with payoff {ec_counter[neighbor]}")

                if ec_counter:
                    # max_value = max(ec_counter.values())
                    # max_elements = [key for key, value in ec_counter.items() if value == max_value]
                    # # 如果有多个具有最大值的元素，随机选择一个
                    # selected_node = random.choice(max_elements)
                    # node.selectNodeID = selected_node

                    if (node.selectNodeID == 0) or (max(ec_counter.values()) > old_max):
                        # print("Condition 1 (node.selectNodeID == 0): ", node.selectNodeID == 0)
                        # print(f"Condition 2 (max(ec_counter, key = ec_counter.get) > ec_counter[node.selectNodeID]): ", max(ec_counter, key = ec_counter.get) > ec_counter[node.selectNodeID] if node.selectNodeID in ec_counter else 'N/A')
                        # if node.selectNodeID != 0:
                        #     print(f"max(ec_counter.values()) {max(ec_counter.values())}")
                        #     print(f"ec_counter[node.selectNodeID]) {ec_counter[node.selectNodeID]}")
                        # if (node.selectNodeID == 0) : 
                        #     print("node.selectNodeID == 0")
                        # # elif (max(ec_counter.values()) >= ec_counter[node.selectNodeID]):
                        # if (node.selectNodeID != 0):
                        #     print(f"the new value:{max(ec_counter.values())}, the old value: {old_max}")

                        node.selectNodeID = max(ec_counter, key = ec_counter.get)
                        old_max = ec_counter[node.selectNodeID]
                        if_change = True
                    self.elMatrix[self.remainingNumchanging-1][node.nodeID-1] = node.selectNodeID

                    # node.selectNodeID = max(ec_counter, key = ec_counter.get)
                    # if_change = True
                    # self.elMatrix[self.remainingNumchanging-1][node.nodeID-1] = node.selectNodeID

                    # if node.nodeID == 3:
                    #     print(f"eps{node.nodeID} choose node{node.selectNodeID}")
                    #     print("the payoff is :",ec_counter[node.selectNodeID])
                    # print(if_change)
                    # print()
                    self.ec_selectNodes[matrix_to_tuple(self.elMatrix)] = ec_counter[node.selectNodeID]
                    

        return if_change, old_max
# 如何把矩阵作为键值对的key保存进字典

                # print(f"找到最大值对应的neighbor{node.selectNodeID},已经修改了self.elMatrix")



    def updateSelectNodeID_bytwo(self):
    # 更新每两个eps节点的selectNodeID
        if_change = False
        twobytwo_eps_nodes = self.get_twobytwo_eps_nodes()
        # 剪枝
        self.prune_bytwo(twobytwo_eps_nodes)
        sd_pair_step_num_grade_down = self.get_ep_step()

        # for ep_link in sd_pair_step_num_grade_down.keys():
        #     print("there is ep_link")
        #     for link_1 in ep_link:
        #         print(link_1.startNode, link_1.endNode)

        for two_node in twobytwo_eps_nodes:
            
            twobytwo_eps_neighbor_nodes = self.get_twobytwo_neighbor_nodes(two_node[0], two_node[1])

            links = {}
            ec_counter_bytwo = {}
            neighbor_pro = {}
            # print(f"the length of ec_counter_bytwo before valuing is {len(ec_counter_bytwo)}")

            for neighbor_bytwo in twobytwo_eps_neighbor_nodes:
                    
                for linkProbability in self.linkListProbability:
                    if ( linkProbability.startNode == two_node[0] and linkProbability.endNode == neighbor_bytwo[0] )\
                        or ( linkProbability.startNode == neighbor_bytwo[0] and linkProbability.endNode == two_node[0] ):
                        links[(two_node[0], neighbor_bytwo[0])] = linkProbability
                        links[(neighbor_bytwo[0], two_node[0])] = linkProbability
                    elif ( linkProbability.startNode == two_node[1] and linkProbability.endNode == neighbor_bytwo[1] )\
                        or ( linkProbability.startNode == neighbor_bytwo[1] and linkProbability.endNode == two_node[1] ):
                        links[(two_node[1], neighbor_bytwo[1])] = linkProbability
                        links[(neighbor_bytwo[1], two_node[1])] = linkProbability
                    
                # print(f"links已经加载完毕:{links.keys()}")

                # self.elMatrix = copy.deepcopy(elMatrix)
                mark1 = self.elMatrix[self.remainingNumchanging-1][two_node[0]-1]
                mark2 = self.elMatrix[self.remainingNumchanging-1][two_node[1]-1]
                self.elMatrix[self.remainingNumchanging-1][two_node[0]-1] = neighbor_bytwo[0]
                self.elMatrix[self.remainingNumchanging-1][two_node[1]-1] = neighbor_bytwo[1]
                ec_counter_bytwo[neighbor_bytwo] = self.calculateEcCount()
                self.elMatrix[self.remainingNumchanging-1][two_node[0]-1] = mark1
                self.elMatrix[self.remainingNumchanging-1][two_node[1]-1] = mark2

                # print(f"the length of ec_counter_bytwo after valuing is {len(ec_counter_bytwo)}")

                weight = len(sd_pair_step_num_grade_down)
                for ep_links in sd_pair_step_num_grade_down.keys():
                    weight *= 1/Reduction_factor
                    if links[(two_node[0], neighbor_bytwo[0])] in ep_links \
                        or links[(two_node[1], neighbor_bytwo[1])] in ep_links :
                            # or links[(neighbor_bytwo[0], two_node[0])] in ep_links \
                            #     or links[(neighbor_bytwo[1], two_node[1])] in ep_links :
                        ec_counter_bytwo[neighbor_bytwo] += weight
                # print("已经完成了pf值的修改")
                        

                # neighbor_pro[neighbor_bytwo] = self.getLinkProbability(self.getNode(two_node[0]).nodeID, neighbor_bytwo[0]) + \
                #                                     self.getLinkProbability(self.getNode(two_node[1]).nodeID, neighbor_bytwo[1])
                # neighbor_pro_grade_down = dict(sorted(neighbor_pro.items(), key=lambda item: item[1], reverse=False))
                # weight_pro = len(neighbor_pro_grade_down)*Reduction_factor
                # for neighbor_with_pro in neighbor_pro_grade_down.keys():
                #     weight_pro *= 1/Reduction_factor
                #     if neighbor_bytwo[0] == neighbor_with_pro or neighbor_bytwo[1] == neighbor_with_pro:
                #         ec_counter_bytwo[neighbor_bytwo] += weight_pro                
            
            # if not ec_counter_bytwo:
                # print(f"the two nodes are {two_node[0]} with neighbors ({self.getNode(two_node[0]).adjacentNodes}),{two_node[1]} with neighbors ({self.getNode(two_node[1]).adjacentNodes}) ")

            if ec_counter_bytwo:
                self.getNode(two_node[0]).selectNodeID = max(ec_counter_bytwo, key = ec_counter_bytwo.get)[0]
                self.getNode(two_node[1]).selectNodeID = max(ec_counter_bytwo, key = ec_counter_bytwo.get)[1]
                mark_for_check1 = self.elMatrix[self.remainingNumchanging-1][two_node[0]-1]
                mark_for_check2 = self.elMatrix[self.remainingNumchanging-1][two_node[1]-1]
                if (mark_for_check1 != self.getNode(two_node[0]).selectNodeID) or (mark_for_check2 != self.getNode(two_node[1]).selectNodeID) :
                    if_change = True
                    self.elMatrix[self.remainingNumchanging-1][two_node[0]-1] = self.getNode(two_node[0]).selectNodeID
                    self.elMatrix[self.remainingNumchanging-1][two_node[1]-1] = self.getNode(two_node[1]).selectNodeID
                self.ec_selectNodes[matrix_to_tuple(self.elMatrix)] = ec_counter_bytwo[(self.getNode(two_node[0]).selectNodeID, self.getNode(two_node[1]).selectNodeID)]
                # print("mark")      
        return if_change
        # 2024/1/13 19:40写到这里，需要想一个排除已存在el的neighbor节点组合的方法，并且以组合为单位更新selectNodeID
                
        # 2024/1/12 17:00写到这里
        #     2024/1/13 12:00写到这里(双节点剪枝部分已经写完)

    # def Old_BestResponse(self, ep_links_of_sd_pair_11_18 = []):

    #     # print("before init")
    #     # for node in self.nodeList:
    #     #     print(node.selectNodeID)

    #     # self.elMatrix = copy.deepcopy(self.elMatrix)    
    #     # self.initSelectNodeID()

    #     # print("after init")
    #     # for node in self.nodeList:
    #     #     print(node.selectNodeID)


        

    #     # print("before updating")
    #     # print(self.elMatrix)
    #     # print(self.elMatrix)

    #     # for loop in range(self.maxloop[0]):
    #     for loop in range(4):
    #         # elMatrix = copy.deepcopy(self.elMatrix) 
    #         if_change = self.updateSelectNodeID() 
    #         # print(f"完成第{loop+1}次循环")
            
    #         #添加判断el_success是否不再变化的语句 
    #         # if np.array_equal(elMatrix, self.elMatrix):
    #         if not if_change:
    #             # print(f"已经在单节点迭代中收敛，轮数为{loop+1}")
    #             # nodes_selected = compare_and_retain_differences(self.elMatrix, self.elMatrix)
    #             # print(f"nodes_selected:{nodes_selected}")
    #             # eps_selectNode = get_eps_selectNode(nodes_selected)
    #             # print("这一轮中的节点选择情况为：", eps_selectNode)

    #             # print("update之前的elMatrix", self.elMatrix)
    #             # 概率更新el，检查是否新建成ec，更新el表和sd对表，滑动el矩阵
    #             self.update_elMatrix(eps_selectNode)
    #             # print("检查ec并清空el之前", self.elMatrix)
    #             # print(len(self.sdList))
    #             self.check_if_ec_and_update(ep_links_of_sd_pair_11_18)
    #             # print("滑动前", self.elMatrix)
    #             self.elMatrix = sliding_matrix(self.elMatrix)
    #             # print("滑动之后", self.elMatrix)
    #             # 需要记录这一个时隙达到博弈收敛用掉的轮数 24.1.23
    #             # 修改一下循环的方式, 这里的loop还没有派上用场
    #             return loop + 1
    #     # print("单节点循环结束,没有收敛")
    #     for loop in range(8):
    #         # elMatrix = copy.deepcopy(self.elMatrix)
    #         if_change = self.updateSelectNodeID_bytwo()
    #         #添加判断el_success是否不再变化的语句
    #         # if np.array_equal(elMatrix, self.elMatrix):
    #         if not if_change:
    #             # print(f"已经在双节点迭代中收敛，轮数为{loop+1}")
    #             nodes_selected = compare_and_retain_differences(self.elMatrix, self.elMatrix)
    #             eps_selectNode = get_eps_selectNode(nodes_selected)
    #             # print("这一轮中的节点选择情况为：", eps_selectNode) 
    #             # 概率更新el，检查是否新建成ec，更新
    #             # el表和sd对表，滑动el矩阵
    #             self.update_elMatrix(eps_selectNode)
    #             self.check_if_ec_and_update()
    #             self.elMatrix = sliding_matrix(self.elMatrix)
    #             # 需要记录这一个时隙达到博弈收敛用掉的轮数 24.1.23
    #             # 修改一下循环的方式, 这里的loop还没有派上用场
    #             return loop + 4
    #     # print("经过单节点迭代和双节点迭代都没有收敛")
    #     # example_matrix = self.elMatrix
    #     ec_selectNodes = self.ec_selectNodes
    #     # print("max(ec_selectNodes, key=ec_selectNodes.get):",max(ec_selectNodes, key=ec_selectNodes.get))
    #     el_success_with_max = tuple_to_matrix(max(ec_selectNodes, key=ec_selectNodes.get))
    #     # print("el_success_with_max",el_success_with_max)
    #     # el_success_with_max = max(ec_selectNodes, key = ec_selectNodes.get)
    #     nodes_selected = compare_and_retain_differences(self.elMatrix, el_success_with_max)
    #     # print("nodes_selected",nodes_selected)
    #     eps_selectNode = get_eps_selectNode(nodes_selected)
    #     # print("这一轮中的节点选择情况为：", eps_selectNode)       
    #     # 概率更新el，检查是否新建成ec，更新el表和sd对表，滑动el矩阵
    #     # print("1111111")
    #     self.update_elMatrix(eps_selectNode)
    #     # print("2222222")
    #     self.check_if_ec_and_update()
    #     # print("3333333")
    #     self.elMatrix = sliding_matrix(self.elMatrix)
    #     # print("4444444")
    #     # 需要记录这一个时隙达到博弈收敛用掉的轮数 24.1.23
    #     # 修改一下循环的方式, 这里的loop还没有派上用场
    #     return 5

    def BestResponse(self, epList, eps_ep_index, eps_ep_nodes):
        self.ec_selectNodes.clear()
        eps_sd_pair_step_num_grade_down = {}
        for node in self.nodeList:
            if node.epsFlag == 1:
                eps_sd_pair_step_num_grade_down[node.nodeID] = self.get_ep_step(node.nodeID, eps_ep_index, epList)

        if_change = False  # 假设 False 表示没有变化
        if_change, old_max = self.updateSelectNodeID(epList, eps_ep_index, eps_ep_nodes, eps_sd_pair_step_num_grade_down)
        loop = 0
        for i in range(15):
            if_change, new_old_max = self.updateSelectNodeID(epList, eps_ep_index, eps_ep_nodes, eps_sd_pair_step_num_grade_down, old_max)
            old_max == new_old_max
            loop += 1
            # print(if_change)
            if not if_change:  # 如果 if_change 为 False，则退出内层循环
                break

        if if_change == True:
            print("本时隙内未完成收敛")
            ec_selectNodes = self.ec_selectNodes
            max_matrix = tuple_to_matrix(max(ec_selectNodes, key=ec_selectNodes.get))
            self.elMatrix[self.elMatrix.shape[0] - 1] = max_matrix[self.elMatrix.shape[0] - 1]

        self.update_elMatrix()
        # print("完成update",qnetwork.elMatrix)
        self.check_if_ec_and_update()
        # print("完成ec check",qnetwork.elMatrix)
        self.elMatrix = sliding_matrix(self.elMatrix)
        # print("qnetwork.ec_counter:", self.ec_counter)

        return loop

    # 通信开销统计函数还有待修改,需要和每个时隙的迭代次数结合起来    
    def communication_cost(self, traffic, loop):
        communication_cost_overall = 0 
        communication_cost_of_links = {}
        # 计算eps节点两两之间的最短跳数*（对应的数据大小）
        twobytwo_eps_nodes = self.get_twobytwo_eps_nodes()
        for two_node in twobytwo_eps_nodes:
            step = len(self.getShortedPath(two_node[0], two_node[1])) 
            degree1 = len(two_node[0].adjacentNodes)
            degree2 = len(two_node[1].adjacentNodes)
            communication_cost_overall += step * (degree1 * traffic[0] + loop * traffic[1] + degree2 * traffic[0] + loop * traffic[1])
        # 统计单link负载，如果某个link出现在某个eps对之间的路径上，
        # 就加一个该eps对的两个节点分别的（每个eps的度数*（linkID：el可持续时隙数）+ （epsNodeID：selectNodeID）），
        # 然后得到所有link中这个值最大的link，以及对应的该值    
            for link in self.linkListProbability:
                communication_cost_of_links[link] = 0
                eps_path_links = self.get_path_links_of_eps_pair(two_node[0], two_node[1])
                if link in eps_path_links:
                    degree1 = len(two_node[0].adjacentNodes)
                    degree2 = len(two_node[1].adjacentNodes)
                    communication_cost_of_links[link] += (degree1 * traffic[0] + loop * traffic[1] + degree2 * traffic[0] + loop * traffic[1])
        max_link, max_traffic = max(communication_cost_of_links.items(), key=lambda x: x[1])

        return communication_cost_overall, communication_cost_of_links, max_link, max_traffic

    def Pro_first(self):
        for node in self.nodeList:
            if node.epsFlag == 1:
                neighbor_pro = {}
                if node.adjacentNodes:
                    for neighbor in node.adjacentNodes:
                        # excluded_values = self.get_excluded_values(node.nodeID)
                        # if neighbor not in excluded_values:
                        if True:
                            neighbor_pro[neighbor] = self.getLinkProbability(node.nodeID, neighbor)
                #找到neighbor_pro[] 中值最大的键
                if neighbor_pro:
                    max_value = max(neighbor_pro.values())
                    max_elements = [key for key, value in neighbor_pro.items() if value == max_value]
                    # 如果有多个具有最大值的元素，随机选择一个
                    selected_node = random.choice(max_elements)
                    # print("最大值的个数", len(max_elements))
                    node.selectNodeID = selected_node
                # 更新elMatrix
                for index in range(self.elMatrix.shape[1]):
                    if index+1 == node.nodeID:
                        choices_array = np.array([node.selectNodeID, 0])
                        # 获取概率值 v
                        v = self.getLinkProbability(node.nodeID, neighbor)
                        self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
        # print("profirst 执行中")
        self.check_if_ec_and_update()
        # print("滑动前", self.elMatrix)
        self.elMatrix = sliding_matrix(self.elMatrix)
        # print("滑动之后", self.elMatrix)

    def Step_first(self):
        sd_pair_step_num = {}
        for sd_pair in self.sdList:
            # EP = self.getShortedPath_EPS(sd_pair[0], sd_pair[1])
            ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])
            el_links = self.get_el_links_elMatrix()
            unique_elements_a = set(ep_links_of_sd)
            unique_elements_b = set(el_links)
            elements_not_in_b = [x for x in unique_elements_a if x not in unique_elements_b]
            # # 计算不存在的元素个数
            # Step_num = len(elements_not_in_b)
            # sd_pair_step_num[tuple(ep_links_of_sd)] = Step_num
            # sd_pair_step_num_grade_down = dict(sorted(sd_pair_step_num.items(), key=lambda item: item[1], reverse=False))
        ### 修改版，遇到多个step_num值相同的键值对时，将他们随机排序而不是按照固定的顺序排列
            Step_num = len(elements_not_in_b)
            sd_pair_step_num[tuple(ep_links_of_sd)] = Step_num

            # 将具有相同值的键值对分组
            grouped_items = {}
            for key, value in sd_pair_step_num.items():
                grouped_items.setdefault(value, []).append((key, value))

            # 对每个值相同的组进行随机排序
            for key, items in grouped_items.items():
                random.shuffle(items)

            # 将随机排序后的键值对重新组合成列表
            sorted_items = [(key, value) for sublist in grouped_items.values() for (key, value) in sublist]

            # 引入微小的随机扰动
            perturbed_items = [(key, value + random.uniform(-0.1, 0.1)) for key, value in sorted_items]

            # 按带有扰动的 step_num 排序
            perturbed_items.sort(key=lambda item: item[1])

            # 转换回字典，去掉扰动部分
            sd_pair_step_num_grade_down = {key: int(value) for key, value in perturbed_items}

            # # 将随机排序后的键值对重新组合成列表，并按 step_num 排序
            # sorted_items = sorted((item for sublist in grouped_items.values() for item in sublist), key=lambda item: item[1])

            # # 转换回字典
            # sd_pair_step_num_grade_down = dict(sorted_items)    

            # sd_pair_step_num_grade_down = dict(sorted(sd_pair_step_num.items(), key=lambda item: item[1], reverse=False))   

        # for ep_link in sd_pair_step_num_grade_down.keys():
        #     print("length of ep_links:")
        #     print(len(ep_link))
            # sorted_sd_pair_step_num  = dict(sorted(sd_pair_step_num.items(), key=lambda item: item[1], reverse=False))   

            # # 创建一个临时字典来存储具有相同 Step_num 的项
            # temp_dict = {}
            # for item in sorted_sd_pair_step_num:
            #     step_num = item[1]
            #     if step_num not in temp_dict:
            #         temp_dict[step_num] = []
            #     temp_dict[step_num].append(item)the new value
            # # 对每个步数相同的组进行随机打乱
            # for step_num in temp_dict:
            #     random.shuffle(temp_dict[step_num])
            # # 将随机打乱后的键值对重新组合成有序列表
            # shuffled_sorted_list = [item for sublist in temp_dict.values() for item in sublist]
            # # 将最终的列表转换为有序字典
            # sd_pair_step_num_grade_down = OrderedDict(shuffled_sorted_list)

        
        for node in self.nodeList:
            if node.epsFlag == 1:
                link = {}
                for neighbor in node.adjacentNodes:
                    for linkProbability in self.linkListProbability:
                        if linkProbability.startNode == node.nodeID and linkProbability.endNode == neighbor:
                            link[neighbor] = linkProbability
                        elif linkProbability.startNode == neighbor and linkProbability.endNode == node.nodeID:
                            link[neighbor] = linkProbability
                    # if neighbor not in link:
                    #     link[neighbor] = []
                exit_loop = False
                for ep_link in sd_pair_step_num_grade_down.keys():
                    for neighbor in node.adjacentNodes:
                        # if neighbor not in self.get_excluded_values(node.nodeID):
                        if True:
                            if link[neighbor] in ep_link:
                                # print("有link在ep中")
                                node.selectNodeID = neighbor
                                exit_loop = True    
                                break
                    if exit_loop:
                        # print("exiting")
                        break
        # 更新elMatrix
        for node in self.nodeList:
            if node.epsFlag == 1:
                for index in range(self.elMatrix.shape[1]):
                    # if node.selectNodeID == 0:
                    #     print("node.selectNodeID is 0")
                    if index+1 == node.nodeID:
                        # if node.selectNodeID == 0:
                        #     print("node.selectNodeID is 0")
                        choices_array = np.array([node.selectNodeID, 0])
                        # 获取概率值 v  
                        v = self.getLinkProbability(node.nodeID, node.selectNodeID)
                        # v = self.getLinkProbability(node.nodeID, node.selectNodeID)*0.8
                        # if v > 1 or v < 0: 
                        #     print(f"link{(node.nodeID, node.selectNodeID)}的el建成概率为{v}")
                        # else:
                        #     self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
                        self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
        self.check_if_ec_and_update()
        self.elMatrix = sliding_matrix(self.elMatrix)
                        
    def Remainning_first(self):
        elMatrix = self.elMatrix
        el_nodes = {}
        for row in elMatrix:
            # print(row, "/n")
            index = 0 
            for element in row:
                index += 1
                if element != 0:
                    # print(f"there is an element: {(index, element)}")
                    row_tuple = tuple(row)
                    if row_tuple not in el_nodes:
                        el_nodes[row_tuple] = []  # 如果该行不存在于 el_nodes 字典中，则创建一个空列表
                    el_nodes[row_tuple].append((index, element))

        # print(len(el_nodes))
        # print("el_nodes is", el_nodes)
        el_links = {}
        for linkProbability in self.linkListProbability:
            for row, nodes in el_nodes.items():
                if row not in el_links:
                    el_links[row] = []  # 初始化列表
                for link_nodes in nodes:
                    if (linkProbability.startNode == link_nodes[0] and linkProbability.endNode == link_nodes[1]) or \
                    (linkProbability.startNode == link_nodes[1] and linkProbability.endNode == link_nodes[0]):
                        el_links[row].append(linkProbability)

        # print(len(el_links))
        # print("el_links is", el_links)
        sd_pair_urgency = {}    
        for sd_pair in self.sdList:
            ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])
            if tuple(ep_links_of_sd) not in sd_pair_urgency:
                sd_pair_urgency[tuple(ep_links_of_sd)] = 0
            for row in el_links.keys():
                weight = remaining_num*5
                for link in el_links[row]:
                    # print("ininininini")
                    if link in ep_links_of_sd:
                        sd_pair_urgency[tuple(ep_links_of_sd)] += weight 
                weight -= 5
    
            # 将具有相同值的键值对分组
            grouped_items = {}
            for key, value in sd_pair_urgency.items():
                grouped_items.setdefault(value, []).append((key, value))

            # 对每个值相同的组进行随机排序
            for key, items in grouped_items.items():
                random.shuffle(items)

            # 将随机排序后的键值对重新组合成列表
            sorted_items = [(key, value) for sublist in grouped_items.values() for (key, value) in sublist]

            # 引入微小的随机扰动
            perturbed_items = [(key, value + random.uniform(-0.1, 0.1)) for key, value in sorted_items]

            # 按带有扰动的 step_num 排序
            perturbed_items.sort(key=lambda item: item[1])

            # 转换回字典，去掉扰动部分
            sd_pair_urgency_grade_down = {key: int(value) for key, value in perturbed_items}

        # sd_pair_urgency_grade_down = dict(sorted(sd_pair_urgency.items(), key=lambda item: item[1], reverse=False))

        # for ep_link in sd_pair_urgency_grade_down.keys():
        #     print("the ep_links have:")
        #     for link in ep_link:
        #         print(f"the link is {link.startNode},{link.endNode}")

    # ### 修改版，遇到多个weight值相同的键值对时，将他们随机排序而不是按照固定的顺序排列
    #     # 将具有相同值的键值对分组
    #     grouped_items = {}
    #     for key, value in sd_pair_urgency.items():
    #         grouped_items.setdefault(value, []).append((key, value))
    #     # 对每个值相同的组进行随机排序
    #     for key, items in grouped_items.items():
    #         random.shuffle(items)
    #     # 将随机排序后的键值对重新组合成字典
    #     sd_pair_urgency_grade_down = dict(item for sublist in grouped_items.values() for item in sublist)    


        # print(sd_pair_urgency_grade_down)
        for node in self.nodeList:
            if node.epsFlag == 1:
                # print(f"{node.nodeID} with epsflag = 1")
                link = {}
                for neighbor in node.adjacentNodes:
                    for linkProbability in self.linkListProbability:
                        if linkProbability.startNode == node.nodeID and linkProbability.endNode == neighbor:
                            link[neighbor] = linkProbability
                        elif linkProbability.startNode == neighbor and linkProbability.endNode == node.nodeID:
                            link[neighbor] = linkProbability
                # for link_neighbor in link:
                #     print(link_neighbor)
                exit_loop = False
                for ep_link in sd_pair_urgency_grade_down.keys():
                    # print("ep_link is ", ep_link)
                    for neighbor in node.adjacentNodes:
                        # print("neighbor's link is", link[neighbor])
                        # if neighbor not in self.get_excluded_values(node.nodeID):
                        if True:
                            if link[neighbor] in ep_link:
                                # print("in~~~~~~~~")
                                node.selectNodeID = neighbor
                                # print(neighbor)
                                # print(f"{node.nodeID}的selectnodeid是{node.selectNodeID}")
                                exit_loop = True    
                                break
                    if exit_loop:
                        # print("exiting")
                        break
                    # else:
                    #     node.selectNodeID = random.choice(node.adjacentNodes)
                    #     print(f"{node.nodeID}的selectnodeid随机为{node.selectNodeID}")
                        # 问题在这里，好像随机出来的结果有一些不在adjacentNodes的范围里

                        # 貌似随机出来的结果虽然是从adjacentNodes里面来的，但是没有一个在ep_link里面的，导致没有break

        # 更新elMatrix
        for node in self.nodeList:
            if node.epsFlag == 1:
                # print(f"node{node.nodeID}的seletnodeid是{node.selectNodeID}")
                for index in range(self.elMatrix.shape[1]):
                        if index+1 == node.nodeID:
                            choices_array = np.array([node.selectNodeID, 0])
                            # 获取概率值 v
                            v = self.getLinkProbability(node.nodeID, node.selectNodeID)
                            # if v > 1 or v < 0: 
                            #     print(f"link{(node.nodeID, node.selectNodeID)}的el建成概率为{v}")
                            # else:
                                # print(f"link{(node.nodeID, node.selectNodeID)}的el将以{v}的概率成功建成")
                                # self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
                            # print(f"link{(node.nodeID, node.selectNodeID)}的el将以{v}的概率成功建成")
                            # else:
                            self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
        # print("sd_pair_urgency_grade_down的长度：", len(sd_pair_urgency_grade_down))
        # print(sd_pair_urgency_grade_down)
        
        # print("sd对的数量：", len(self.sdList))
        # if len(self.sdList) == len(sd_pair_urgency):
        #     print("长度匹配：")
        # else:
        #     print("长度不匹配")
        # print("Length of self.sdList:", len(self.sdList))
        # print("Length of sd_pair_urgency:", len(sd_pair_urgency))
        # if len(sd_pair_urgency_grade_down) == len(sd_pair_urgency):
        #     print("排序没有改变元素数量")
        # else:
        #     print("排序改变了元素数量")


        self.check_if_ec_and_update()

        self.elMatrix = sliding_matrix(self.elMatrix)

    # def Remainning_first(self):
    #     elMatrix = self.elMatrix
    #     el_nodes = {}
    #     for row in elMatrix:
    #         # print(row, "/n")
    #         index = 0 
    #         for element in row:
    #             index += 1
    #             if element != 0:
    #                 # print(f"there is an element: {(index, element)}")
    #                 row_tuple = tuple(row)
    #                 if row_tuple not in el_nodes:
    #                     el_nodes[row_tuple] = []  # 如果该行不存在于 el_nodes 字典中，则创建一个空列表
    #                 el_nodes[row_tuple].append((index, element))

    #     # print(len(el_nodes))
    #     # print("el_nodes is", el_nodes)
    #     el_links = {}
    #     for linkProbability in self.linkListProbability:
    #         for row, nodes in el_nodes.items():
    #             if row not in el_links:
    #                 el_links[row] = []  # 初始化列表
    #             for link_nodes in nodes:
    #                 if (linkProbability.startNode == link_nodes[0] and linkProbability.endNode == link_nodes[1]) or \
    #                 (linkProbability.startNode == link_nodes[1] and linkProbability.endNode == link_nodes[0]):
    #                     el_links[row].append(linkProbability)

    #     # print(len(el_links))
    #     # print("el_links is", el_links)
    #     sd_pair_urgency = {}    
    #     for sd_pair in self.sdList:
    #         ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])
    #         if tuple(ep_links_of_sd) not in sd_pair_urgency:
    #             sd_pair_urgency[tuple(ep_links_of_sd)] = 0
    #         for row in el_links.keys():
    #             weight = remaining_num
    #             for link in el_links[row]:
    #                 # print("ininininini")
    #                 if link in ep_links_of_sd:
    #                     sd_pair_urgency[tuple(ep_links_of_sd)] += weight 
    #             weight -= 1
    
    #     #         if tuple(ep_links_of_sd) in sd_pair_urgency:
    #     #             print(f"sd_pair {sd_pair} is put in")
    #     #             print(f"sd_pair_urgency[{ep_links_of_sd}] is {sd_pair_urgency[tuple(ep_links_of_sd)]}")
    #     # print("sd_pair_urgency is", sd_pair_urgency)
    #     # print("length of sd_pair_urgency is", len(sd_pair_urgency))
    #     # print("length of sd_pair_list is", len(self.sdList))

    #     sd_pair_urgency_grade_down = dict(sorted(sd_pair_urgency.items(), key=lambda item: item[1], reverse=False))


    # # ### 修改版，遇到多个weight值相同的键值对时，将他们随机排序而不是按照固定的顺序排列
    # #     # 将具有相同值的键值对分组
    # #     grouped_items = {}
    # #     for key, value in sd_pair_urgency.items():
    # #         grouped_items.setdefault(value, []).append((key, value))
    # #     # 对每个值相同的组进行随机排序
    # #     for key, items in grouped_items.items():
    # #         random.shuffle(items)
    # #     # 将随机排序后的键值对重新组合成字典
    # #     sd_pair_urgency_grade_down = dict(item for sublist in grouped_items.values() for item in sublist)    


    #     # print(sd_pair_urgency_grade_down)
    #     for node in self.nodeList:
    #         if node.epsFlag == 1:
    #             # print(f"{node.nodeID} with epsflag = 1")
    #             link = {}
    #             for neighbor in node.adjacentNodes:
    #                 for linkProbability in self.linkListProbability:
    #                     if linkProbability.startNode == node.nodeID and linkProbability.endNode == neighbor:
    #                         link[neighbor] = linkProbability
    #                     elif linkProbability.startNode == neighbor and linkProbability.endNode == node.nodeID:
    #                         link[neighbor] = linkProbability
    #             # for link_neighbor in link:
    #             #     print(link_neighbor)
    #             exit_loop = False
    #             for ep_link in sd_pair_urgency_grade_down.keys():
    #                 # print("ep_link is ", ep_link)
    #                 for neighbor in node.adjacentNodes:
    #                     # print("neighbor's link is", link[neighbor])
    #                     if neighbor not in self.get_excluded_values(node.nodeID):
    #                         if link[neighbor] in ep_link:
    #                             # print("in~~~~~~~~")
    #                             node.selectNodeID = neighbor
    #                             # print(neighbor)
    #                             # print(f"{node.nodeID}的selectnodeid是{node.selectNodeID}")
    #                             exit_loop = True    
    #                             break
    #                 if exit_loop:
    #                     # print("exiting")
    #                     break
    #                 # else:
    #                 #     node.selectNodeID = random.choice(node.adjacentNodes)
    #                 #     print(f"{node.nodeID}的selectnodeid随机为{node.selectNodeID}")
    #                     # 问题在这里，好像随机出来的结果有一些不在adjacentNodes的范围里

    #                     # 貌似随机出来的结果虽然是从adjacentNodes里面来的，但是没有一个在ep_link里面的，导致没有break

    #     # 更新elMatrix
    #     for node in self.nodeList:
    #         if node.epsFlag == 1:
    #             # print(f"node{node.nodeID}的seletnodeid是{node.selectNodeID}")
    #             for index in range(self.elMatrix.shape[1]):
    #                     if index+1 == node.nodeID:
    #                         choices_array = np.array([node.selectNodeID, 0])
    #                         # 获取概率值 v
    #                         v = self.getLinkProbability(node.nodeID, node.selectNodeID)
    #                         # if v > 1 or v < 0: 
    #                         #     print(f"link{(node.nodeID, node.selectNodeID)}的el建成概率为{v}")
    #                         # else:
    #                             # print(f"link{(node.nodeID, node.selectNodeID)}的el将以{v}的概率成功建成")
    #                             # self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
    #                         # print(f"link{(node.nodeID, node.selectNodeID)}的el将以{v}的概率成功建成")
    #                         # else:
    #                         self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
    #     # print("sd_pair_urgency_grade_down的长度：", len(sd_pair_urgency_grade_down))
    #     # print(sd_pair_urgency_grade_down)
        
    #     # print("sd对的数量：", len(self.sdList))
    #     # if len(self.sdList) == len(sd_pair_urgency):
    #     #     print("长度匹配：")
    #     # else:
    #     #     print("长度不匹配")
    #     # print("Length of self.sdList:", len(self.sdList))
    #     # print("Length of sd_pair_urgency:", len(sd_pair_urgency))
    #     # if len(sd_pair_urgency_grade_down) == len(sd_pair_urgency):
    #     #     print("排序没有改变元素数量")
    #     # else:
    #     #     print("排序改变了元素数量")


    #     self.br_check_if_ec_and_update()

    #     self.elMatrix = sliding_matrix(self.elMatrix)



    def get_twobytwo_eps_nodes(self):
        nodelist = self.nodeList
        eps_nodes = []
        for node in nodelist:
            if node.epsFlag == 1:
                eps_nodes.append(node.nodeID)
        twobytwo_eps_nodes = []
        twobytwo_eps_nodes = list(itertools.permutations(eps_nodes, 2))
        return twobytwo_eps_nodes

    def get_twobytwo_neighbor_nodes(self, eps_1, eps_2):
        # 注意，这里的eps_1, eps_2是node对象，不是id，不是数字
        twobytwo_eps_neighbor_nodes = []
        eps_1_neighbor = []
        for node in self.getNode(eps_1).adjacentNodes:
            # if node not in self.get_excluded_values(eps_1):
            if True:
                eps_1_neighbor.append(node)
        eps_2_neighbor = []
        for node in self.getNode(eps_2).adjacentNodes:
            # if node not in self.get_excluded_values(eps_2):
            if True:
                eps_2_neighbor.append(node)
        # 经过修改，这里获得的是一个已经提纯过的邻居节点组合了 24.1.13 19：48                       
        twobytwo_eps_neighbor_nodes = product(eps_1_neighbor, eps_2_neighbor)
        return twobytwo_eps_neighbor_nodes
    
    def prune_bytwo(self, twobytwo_eps_nodes):
        for two_node in twobytwo_eps_nodes:
            if len(self.getShortedPath(two_node[0], two_node[1])) > 4:
                del two_node
    
    def br_check_if_ec_and_update(self):

        sd_pair_step_num_grade_down = self.old_get_ep_step()
        for ep_links_of_sd in sd_pair_step_num_grade_down.keys():
            
            el_links = self.old_get_el_links()

            set_a = set(el_links)
            set_b = set(ep_links_of_sd)
            if set_b.issubset(set_a):
                for link in ep_links_of_sd:
                    # 先把link对应到elMatrix上，将值置为0
                    startNode = link.startNode
                    endNode = link.endNode  
                    found = False
                    for row_index in range(self.elMatrix.shape[0]):
                        for column_index in range(self.elMatrix.shape[1]):
                            if self.elMatrix[row_index][column_index] == startNode and column_index + 1 == endNode:
                                self.elMatrix[row_index][column_index] = 0
                                found = True
                                break
                            elif self.elMatrix[row_index][column_index] == endNode and column_index + 1 == startNode:
                                self.elMatrix[row_index][column_index] = 0
                                found = True
                                break
                        if found:
                            break
                self.ec_counter += 1
        # 增加检查还未被利用的即将失效的el
        for elment in self.elMatrix[0]:
            if elment != 0:
                self.elWaste += 1   


    # 检查是否有ec建成，以更新elMatrix（删除已经建成了的ec所包括的el）
    def check_if_ec_and_update(self, ep_links_of_sd_pair_11_18 = []):
        for sd_pair in self.sdList:
            # 检查sd_pair的ep上的所有link是否都存在el，如果是，则更新elMatrix
            ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])

            # if not ep_links_of_sd:
            #     # print("有sd对之间的路径为空,", sd_pair)
            #     # print(self.getShortedPath_EPS(sd_pair[0], sd_pair[1]))
            #     if sd_pair == [11, 18]:
            #         # ep_links_of_sd = self.get_ep_links_of_sd_pair(11, 18)

            #         ep_links_of_sd = ep_links_of_sd_pair_11_18
                    # print("hhhh")
                # [<network.QNetwork.Link object at 0x7fde4c0db610>, <network.QNetwork.Link object at 0x7fde4c0db670>, <network.QNetwork.Link object at 0x7fde4c0dbc10>, <network.QNetwork.Link object at 0x7fde4c0dd130>]
            
            # print(ep_links_of_sd)
            el_links = self.get_el_links_elMatrix()

            # if el_links:
            #     print("存在不为空的el状态矩阵")
            # print("el_links", el_links)

            # if all(el_links for link in ep_links_of_sd):
            set_a = set(el_links)
            set_b = set(ep_links_of_sd)
            # print("set_a", set_a)
            # print("set_b", set_b)

            if set_b.issubset(set_a):
                # print("b is subset")

                # print(f"sd对{sd_pair}, 路径{self.getShortedPath_EPS(sd_pair[0], sd_pair[1])}")
                # print(self.elMatrix)
                # for link in el_links:
                    # print("el_link", (link.startNode, link.endNode))
                # for link in ep_links_of_sd:
                    # print("ep_link", (link.startNode, link.endNode))
                # sd_ec_count = 1
                for link in ep_links_of_sd:
                    # 先把link对应到elMatrix上，将值置为0
                    startNode = link.startNode
                    endNode = link.endNode  
                    # found = False
                    for row_index in range(self.elMatrix.shape[0]):
                        for column_index in range(self.elMatrix.shape[1]):
                            if self.elMatrix[row_index][column_index] == startNode and column_index + 1 == endNode:
                                self.elMatrix[row_index][column_index] = 0
                                # found = True
                                # break
                            elif self.elMatrix[row_index][column_index] == endNode and column_index + 1 == startNode:
                                self.elMatrix[row_index][column_index] = 0
                                # found = True
                                # break
                        # if found:
                        #     break
                # print(self.elMatrix)
                # 将该sd对从列表中删除
                # print(f"刚被建成的ec属于{sd_pair}, 路径为{self.getShortedPath_EPS(sd_pair[0], sd_pair[1])}")
                self.ec_counter += 1
                # self.sdList.remove(sd_pair)   
        # 增加检查还未被利用的即将失效的el
        for elment in self.elMatrix[0]:
            if elment != 0:
                self.elWaste += 1   


    def old_get_ep_step(self):
        sd_pair_step_num = {}
        for sd_pair in self.sdList:
            # EP = self.getShortedPath_EPS(sd_pair[0], sd_pair[1])
            ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])
            el_links = self.get_el_links_elMatrix()
            unique_elements_a = set(ep_links_of_sd)
            unique_elements_b = set(el_links)
            elements_not_in_b = [x for x in unique_elements_a if x not in unique_elements_b]
            # 计算不存在的元素个数
            Step_num = len(elements_not_in_b)
            sd_pair_step_num[tuple(ep_links_of_sd)] = Step_num
            sd_pair_step_num_grade_down = dict(sorted(sd_pair_step_num.items(), key=lambda item: item[1], reverse=False))
        return sd_pair_step_num_grade_down
    
    def get_ep_step(self, eps_id, eps_ep_list, epList):
        sd_pair_step_num = {}
        eps_sdlist = []
        for ep_index in eps_ep_list[eps_id]:
            eps_sdlist.append([epList[ep_index][0], epList[ep_index][-1]])
        for sd_pair in eps_sdlist:
            # EP = self.getShortedPath_EPS(sd_pair[0], sd_pair[1])
            ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])
            el_links = self.get_el_links_elMatrix()
            unique_elements_a = set(ep_links_of_sd)
            unique_elements_b = set(el_links)
            # print(f"length of ep_links_of_sd {(sd_pair[0], sd_pair[1])}",len(unique_elements_a))
            # print("length of el_links",len(unique_elements_b))
            elements_not_in_b = [x for x in unique_elements_a if x not in unique_elements_b]
            # 计算不存在的元素个数
            Step_num = len(elements_not_in_b)
            # print("step_num", Step_num)
            sd_pair_step_num[tuple(ep_links_of_sd)] = Step_num*100 - len(ep_links_of_sd)
            sd_pair_step_num_grade_down = dict(sorted(sd_pair_step_num.items(), key=lambda item: item[1], reverse=False))
        # print(f"sd_pair_step_num_grade_down123:{sd_pair_step_num_grade_down}")
        return sd_pair_step_num_grade_down

    def old_calculateEcCount(self):
        ec_count = 0
        for sd_pair in self.sdList:   
            # 检查sd_pair的ep上的所有link是否都存在el，如果是，则计算并统计ec建成期望
            ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])
            el_links = self.old_get_el_links()

            set_a = set(el_links)
            set_b = set(ep_links_of_sd)
            if set_b.issubset(set_a):
            # if all(el_links for link in ep_links_of_sd):
                sd_ec_count = 1
                for link in ep_links_of_sd:
                    sd_ec_count *= link.probability
                ec_count += sd_ec_count
        
        return ec_count

    def calculateEcCount(self, eps_id, eps_ep_list, eps_ep_nodes, epList):
        ec_count = 0

        sd_pair_step_num_grade_down = self.get_ep_step(eps_id, eps_ep_list, epList)
        for ep_links_of_sd in sd_pair_step_num_grade_down.keys():

        # for sd_pair in self.sdList:   
        #     # 检查sd_pair的ep上的所有link是否都存在el，如果是，则计算并统计ec建成期望
        #     ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])

            el_links = self.get_el_links(eps_ep_nodes)

            set_a = set(el_links)
            set_b = set(ep_links_of_sd)
            if set_b.issubset(set_a):
            # if all(el_links for link in ep_links_of_sd):
                sd_ec_count = 1
                for link in ep_links_of_sd:
                    sd_ec_count *= link.probability
                ec_count += sd_ec_count
        
        return ec_count

    def old_get_el_links(self):
        # el_success_looping = self.el_success_looping
        el_nodes = []
        for row in self.elMatrix:
            index = 0
            for element in row:
                index += 1
                if element != 0:
                    el_nodes.append((index, element))
        el_links = []
        for linkProbability in self.linkListProbability:
            for link_nodes in el_nodes:
                if linkProbability.startNode == link_nodes[0] and linkProbability.endNode == link_nodes[1]:
                    el_links.append(linkProbability)
                elif linkProbability.startNode == link_nodes[1] and linkProbability.endNode == link_nodes[0]:
                    el_links.append(linkProbability)
        return el_links
    
    def get_el_links(self, ep_nodes):
        # el_success_looping = self.el_success_looping
        el_nodes = []
        for node in ep_nodes:
                for row in self.elMatrix:
                        index = 0
                        for element in row:
                            index += 1
                            if  index == node:
                                el_nodes.append((index, element))
        el_links = []
        for linkProbability in self.linkListProbability:
            for link_nodes in el_nodes:
                if linkProbability.startNode == link_nodes[0] and linkProbability.endNode == link_nodes[1]:
                    el_links.append(linkProbability)
                elif linkProbability.startNode == link_nodes[1] and linkProbability.endNode == link_nodes[0]:
                    el_links.append(linkProbability)
        return el_links


    
    # def calculateEcCount_mlp(self, el_success_looping_neighbor):
    #     ec_count = 0
    #     for sd_pair in self.sdList:
    #         # 检查sd_pair的ep上的所有link是否都存在el，如果是，则计算并统计ec建成期望
    #         ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])
    #         el_links = self.get_el_links_mlp(el_success_looping_neighbor)

    #         set_a = set(el_links)
    #         set_b = set(ep_links_of_sd)
    #         if set_b.issubset(set_a):
    #         # if all(el_links for link in ep_links_of_sd):
    #             sd_ec_count = 1
    #             for link in ep_links_of_sd:
    #                 sd_ec_count *= link.probability
    #             ec_count += sd_ec_count
    #     return ec_count

    # def get_el_links_mlp(self, el_success_looping_neighbor):
    #     el_success_looping = el_success_looping_neighbor
    #     el_nodes = []
    #     for row in el_success_looping:
    #         index = 0
    #         for element in row:
    #             index += 1
    #             if element != 0:
    #                 el_nodes.append((index, element))
    #     el_links = []
    #     #  这里的取link函数写的可能有问题，有待检查
    #     for linkProbability in self.linkListProbability:
    #         for link_nodes in el_nodes:
    #             if linkProbability.startNode == link_nodes[0] and linkProbability.endNode == link_nodes[1]:
    #                 el_links.append(linkProbability)
    #             elif linkProbability.startNode == link_nodes[1] and linkProbability.endNode == link_nodes[0]:
    #                 el_links.append(linkProbability)
    #     return el_links

    def get_el_links_elMatrix(self):
        elMatrix = self.elMatrix
        el_nodes = []
        for row in elMatrix:
            index = 0
            for element in row:
                index += 1
                if element != 0:
                    el_nodes.append((index, element))
        el_links = []
        # print("el_links", el_links)
        #  这里的取link函数写的可能有问题，有待检查
        # 24.1.24 这里的方法应该没有问题,可以正常调用startNode
        for linkProbability in self.linkListProbability:
            for link_nodes in el_nodes:
                if linkProbability.startNode == link_nodes[0] and linkProbability.endNode == link_nodes[1]:
                    el_links.append(linkProbability)
                elif linkProbability.startNode == link_nodes[1] and linkProbability.endNode == link_nodes[0]:
                    el_links.append(linkProbability)
        return el_links

    def get_ep_links_of_sd_pair(self , sourceID, destinationID):
        EP = self.getShortedPath_EPS(sourceID, destinationID)
        if not EP:
            print("存在路径为空的sd对")
        ep_links = []
        for linkProbability in self.linkListProbability:
            for index in range(len(EP)-1):
                if linkProbability.startNode == EP[index] and linkProbability.endNode == EP[index+1]:
                    ep_links.append(linkProbability)
                elif linkProbability.startNode == EP[index+1] and linkProbability.endNode == EP[index]:
                    ep_links.append(linkProbability)
        return ep_links

    # def update_elMatrix(self, eps_selectNode):
    #         for index in range(self.elMatrix.shape[1]):
    #             for key, value in eps_selectNode.items():
    #                 if self.getNode(key).epsFlag == 1:
                            
    #                     if index+1 == key:
    #                         # print(key, value[0])
    #                         # 将 [value, 0] 转换为 NumPy 数组
    #                         choices_array = np.array([self.getNode(key).selectNodeID, 0])
    #                         # 获取概率值 v
    #                         v = self.getLinkProbability(key, self.getNode(key).selectNodeID)
    #                         # print("link上的概率(原版本)：", v)
    #                         # print("link上的概率(int版本)：", int(v))
    #                         # 使用 np.random.choice() 来进行随机选择
    #                         if v > 0 :
    #                             self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
    #                         else:
    #                             print(key,value[0], v)
    #                         # if row[index] != 0:
    #                         #     print("有el被成功创建了")

    # def update_elMatrix(self, eps_selectNode):
    #     index = 0 
    #     for value in self.elMatrix[self.elMatrix.shape[0]-1]:
    #         index += 1 
    #         if value != 0:
    #             # print(key, value[0])
    #             # 将 [value, 0] 转换为 NumPy 数组
    #             choices_array = np.array([value, 0])
    #             # 获取概率值 v
    #             v = self.getLinkProbability(index, value)
    #             # print("link上的概率(原版本)：", v)
    #             # print("link上的概率(int版本)：", int(v))
    #             # 使用 np.random.choice() 来进行随机选择
    #             if v > 0 :
    #                 self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
    #             else:
    #                 print(index, value, v)
    #             # if row[index] != 0:
    #             #     print("有el被成功创建了")

    def update_elMatrix(self):
        index = 1  # 索引从 1 开始
        last_row = self.elMatrix[self.elMatrix.shape[0] - 1]
        # print(f"Initial last row: {last_row}")  # 输出初始最后一行的值
        
        for value in last_row: 
            # print(f"index is {index}, value is {value}")  # 输出当前索引和值
            if value != 0:
                # 将 [value, 0] 转换为 NumPy 数组
                choices_array = np.array([value, 0])
                # 获取概率值 v
                v = self.getLinkProbability(index, value)
                # print(f"概率为{v}")
                if v < 0 or v > 1:
                    print(f"link查找异常 {index} {value} {v}")
                else:
                    if v > 0:
                        new_value = np.random.choice(choices_array, p=[v, 1-v])

                        # if index == 3 and value == 2:
                        #     print(f"eps3 with node2 will be in {v} and the el will be {new_value}")
                        # print(f"Setting self.elMatrix[{self.remainingNumchanging-1}][{index-1}] to {new_value}")
                        # if new_value == value:
                        #     print("成功创建el")
                        self.elMatrix[self.remainingNumchanging - 1][index - 1] = new_value
                    elif v == 0:
                        new_value = np.random.choice(choices_array, p=[1, 0.1])

                        self.elMatrix[self.remainingNumchanging - 1][index - 1] = new_value
                        # print(f"link查找异常 {index} {value} {v}")
            index += 1
            # print(f"after index is {index}, value is {value}")
        
        # print(f"Final last row: {self.elMatrix[self.elMatrix.shape[0] - 1]}")  # 输出最后修改后的最后一行的值



    def get_excluded_values(self, value):
        excluded_values = []
        matrix = self.elMatrix
        for row in matrix:
            element = row[value-1] 
            if element != 0:
                excluded_values.append(element)
            # 这里添加检索是否被其他eps选择的代码
            for index in range(matrix.shape[1]):
                if row[index] == value:
                    excluded_values.append(index+1)
        return excluded_values

    def getShortedPath_EPS(self, startNodeID, endNodeID):
        # 创建一个字典来保存节点的距离和路径
        distances = {}
        paths = {}
        visited = set()
        # 初始化距离为无穷大，路径为空列表
        for node in self.nodeList:
            distances[node.nodeID] = float('inf')
            paths[node.nodeID] = []
        # 将起始节点的距离设置为0
        distances[startNodeID] = 0
        while len(visited) < len(self.nodeList):
            # 找到未访问节点中距离最小的节点
            min_distance = float('inf')
            min_node = None
            for node in self.nodeList:
                if node.nodeID not in visited and distances[node.nodeID] < min_distance:
                    min_distance = distances[node.nodeID]
                    min_node = node
            if min_node is None:
                # 没有找到可到达的节点
                break
            # 标记节点为已访问
            visited.add(min_node.nodeID)
            # 更新相邻节点的距离和路径
            for neighborID in min_node.adjacentNodes:
                neighbor = self.getNode(neighborID)
                # 检查当前节点和相邻节点的类型
                is_current_eps = min_node.epsFlag == 1
                is_neighbor_eps = neighbor.epsFlag == 1
                if is_current_eps or is_neighbor_eps:
                    # 计算新的距离
                    new_distance = distances[min_node.nodeID] + 1
                    if new_distance < distances[neighbor.nodeID]:
                        # 更新距离和路径
                        distances[neighbor.nodeID] = new_distance
                        paths[neighbor.nodeID] = paths[min_node.nodeID] + \
                            [neighbor.nodeID]
        paths[endNodeID].insert(0, startNodeID)
        return paths[endNodeID]


  
    
    def getShortedPath(self, startNodeID, endNodeID):
        # 创建一个字典来保存节点的距离和路径
        distances = {}
        paths = {}
        visited = set()
        # 初始化距离为无穷大，路径为空列表
        for node in self.nodeList:
            distances[node.nodeID] = float('inf')
            paths[node.nodeID] = []
        # 将起始节点的距离设置为0
        distances[startNodeID] = 0
        while len(visited) < len(self.nodeList):
            # 找到未访问节点中距离最小的节点
            min_distance = float('inf')
            min_node = None
            for node in self.nodeList:
                if node.nodeID not in visited and distances[node.nodeID] < min_distance:
                    min_distance = distances[node.nodeID]
                    min_node = node
            if min_node is None:
                # 没有找到可到达的节点
                break
            # 标记节点为已访问
            visited.add(min_node.nodeID)
            # 更新相邻节点的距离和路径
            for neighborID in min_node.adjacentNodes:
                neighbor = self.getNode(neighborID)             
                # 计算新的距离
                new_distance = distances[min_node.nodeID] + 1
                if new_distance < distances[neighbor.nodeID]:
                    # 更新距离和路径
                    distances[neighbor.nodeID] = new_distance
                    paths[neighbor.nodeID] = paths[min_node.nodeID] + \
                        [neighbor.nodeID]
        paths[endNodeID].insert(0, startNodeID)            
        return paths[endNodeID]

    def showNetwork(self):
        with open('./data/generate.txt', 'r') as file:
            lines = file.readlines()
        n = int(lines[0])
        nodes = [int(line) for line in lines[1:n+1]]
        G = nx.Graph()
        G.add_nodes_from(nodes)
        m = int(lines[n+1])
        for line in lines[n+2:]:
            start, end, weight = map(int, line.split())
            G.add_edge(start, end, weight=weight)
        fig, ax = plt.subplots()
        pos = nx.spring_layout(G, seed=41)
        nx.draw(G, pos, ax=ax, with_labels=True, node_color='red',
                node_size=300, font_size=8, alpha=1)
        edge_labels = nx.get_edge_attributes(G, 'weight')
        nx.draw_networkx_edge_labels(
            G, pos, edge_labels=edge_labels, font_size=6)
        plt.title("Network Topology")
        plt.show()

    def getLinkProbability(self, startID, endID):
        for linkProbability in self.linkListProbability:
            if linkProbability.startNode == startID and linkProbability.endNode == endID:
                return linkProbability.probability
            if linkProbability.startNode == endID and linkProbability.endNode == startID:
                return linkProbability.probability
        return -1

    def getNode(self, nodeId):
        if nodeId - 1 >= len(self.nodeList) or nodeId - 1 < 0:
            return self.Node(-1)
        return self.nodeList[nodeId - 1]

    def readDataFromTxt(self, path):
        with open(path, 'r') as file:
            lines = file.readlines()
            numNodes = int(lines[0])
            nodeIDs = [int(line.strip()) for line in lines[1: numNodes + 1]]
            for nodeID in nodeIDs:
                self.nodeList.append(self.Node(nodeID))
            numLinks = int(lines[numNodes + 1])
            for i in range(numNodes + 2, numNodes + numLinks + 2):
                linkData = lines[i].split()
                startNode = int(linkData[0])
                endNode = int(linkData[1])
                self.nodeList[startNode - 1].adjacentNodes.append(endNode)
                self.nodeList[endNode - 1].adjacentNodes.append(startNode)
                probability = int(linkData[2])/100
                linkProbability = self.Link(
                    startNode, endNode, probability)
                self.linkListProbability.append(linkProbability)
            sdNum = int(lines[numNodes + numLinks + 2])
            self.sdList = []
            for i in range(numNodes + numLinks + 3, numNodes + numLinks + sdNum + 3):
                sdData = lines[i].split()
                self.sdList.append([int(sdData[0]), int(sdData[1])])
                self.sdList_all.append([int(sdData[0]), int(sdData[1])])
            epsNodeNum = int(lines[numNodes + numLinks + sdNum + 3])
            for i in range(numNodes + numLinks + sdNum + 4, numNodes + numLinks + epsNodeNum + sdNum + 4):
                epsNodeID = int(lines[i])
                self.getNode(epsNodeID).epsFlag = 1
            # # 添加了不同迭代单位的最大迭代次数 的值
            # maxloopNum = int(lines[numNodes + numLinks + sdNum + epsNodeNum + 4])
            # self.maxloop = []
            # for i in range(numNodes + numLinks + sdNum + epsNodeNum +5, numNodes + numLinks + sdNum + epsNodeNum + maxloopNum + 5):
            #     self.maxloop.append(i)         
                
    # 新增数据结构：      self.nodeList      eps_ep_list
    def get_epList(self):
        # 获取包含全部ep的列表
        epList = {}
        index_of_ep = 1
        for sd_pair in self.sdList:
            epList[index_of_ep] = self.getShortedPath_EPS(sd_pair[0], sd_pair[1])
            index_of_ep += 1
        return epList
    
    def get_eps_ep_list(self, epList):
        # 获取包括 每一个eps对应的ep 的列表
        eps_ep = {}
        eps_ep_nodes = {}
        # eps_ep_link_node = {}
        for node in self.nodeList:
            if node.epsFlag == 1:
                for ep, ep_nodes in epList.items():
                    if node.nodeID in ep_nodes:
                        if node.nodeID not in eps_ep:
                            eps_ep[node.nodeID] = []  # 初始化键的值为列表
                        eps_ep[node.nodeID].append(ep)  # 向列表中添加ep
        for eps, ep_list in eps_ep.items():
            ep_list_node = []
            for ep_index in ep_list:
                ep_list_node.append(epList[ep_index])
            eps_ep_nodes[eps] = merge_lists(ep_list_node)
                # 获得link的端点的二元组的数组
        # for eps, ep_nodes in eps_ep_nodes.items():
        #     ep_list_link = []
        #     for node1 in ep_nodes:
        #         for node2 in ep_nodes:
        #             for linkProbability in self.linkListProbability:
        #                     if linkProbability.startNode == node1 and linkProbability.endNode == node2:
        #                         ep_list_link.append((node1,node2))
        #                     elif linkProbability.startNode == node2 and linkProbability.endNode == node1:
        #                         ep_list_link.append((node1,node2))
        #     eps_ep_link_node[eps] = ep_list_link
          
                        
        return eps_ep, eps_ep_nodes#, eps_ep_link_node
    
    
    
    # def get_eps_el_metrix(self, eps_ep, epList):
    #     # 获取包括 每一个eps对应的el状态矩阵 的列表
    #     remaining_num_changing = 2
    #     eps_el_metrix = {}
    #     eps_ep_node = {}
    #     for eps, ep_list in eps_ep.items():
    #         ep_list_node = []
    #         for ep_index in ep_list:
    #             ep_list_node.append(epList[ep_index])
    #         eps_ep_node[eps] = merge_lists(ep_list_node)
    #         print("eps-node_of_ep", eps, eps_ep_node[eps])
    #         eps_el_metrix[eps] = np.zeros((remaining_num_changing, len(self.nodeList)))

    #     return eps_el_metrix

def compare_and_retain_differences(A, B):
    # 检查矩阵A和B是否形状相同
    if A.shape == B.shape:
        # 创建一个新的矩阵C，初始值为0
        C = np.zeros_like(B)
        # 遍历矩阵A和B的每个元素，比较是否相同
        for i in range(A.shape[0]):
            for column_index in range(A.shape[1]):
                if A[i, column_index] != B[i, column_index]:
                    # print("两个矩阵不同")
                    C[i, column_index] = B[i, column_index]  # 如果不同，将B的对应元素保留
        
        # print("elMatrix:", A)
        # print("elMatrix:", B)
        return C  # 返回更新后的矩阵C
    # else:
    #     return None  # 如果形状不同，返回None表示无法比较
        
def get_eps_selectNode(M):
    eps_selectNode = {}
    for row in M:
        for index in range(M.shape[1]):
            if row[index] != 0:
                if (index+1) not in eps_selectNode:
                    eps_selectNode[index+1] = []
                eps_selectNode[index+1].append(row[index])
                # eps_selectNode[index+1].append(", ")
    return eps_selectNode


def sliding_matrix(input_matrix):
    result_matrix = np.copy(input_matrix)
    result_matrix[:-1] = input_matrix[1:]
    result_matrix[-1] = 0

    return result_matrix

# def update_node_select_mlp(node, Self):
#     if node.epsFlag == 1:
#         print(f"node{node.nodeID} is eps")
#         ec_counter = {}
#         if node.adjacentNodes:
#             excluded_values = Self.get_excluded_values(node.nodeID)
#             for neighbor in node.adjacentNodes:
#                 # Self.el_success_looping = copy.deepcopy(Self.elMatrix)
#                 el_success_looping_neighbor = copy.deepcopy(Self.elMatrix)

#                 if neighbor not in excluded_values:
#                     # Self.el_success_looping[self.remainingNumchanging-1][node.nodeID-1] = neighbor
#                     el_success_looping_neighbor[self.remainingNumchanging-1][node.nodeID-1] = neighbor
#                     ec_counter[neighbor] = Self.calculateEcCount_mlp(el_success_looping_neighbor)
#                     print(f"node {node.nodeID} with neighbor {neighbor} has payoff {ec_counter[neighbor]}")
#         if ec_counter:
#             node.selectNodeID = max(ec_counter, key = ec_counter.get)
#             print(f"max is {max(ec_counter, key = ec_counter.get)}")
#             print(f"node{node.nodeID} has selected neighbor {node.selectNodeID}")
#             Self.elMatrix[self.remainingNumchanging-1][node.nodeID-1] = node.selectNodeID

# 将矩阵转换为字符串
def matrix_to_str(matrix):
    return matrix.tostring()

# 将字符串转换为矩阵
def str_to_matrix(string, shape, dtype=int):
    return np.frombuffer(string, dtype=dtype).reshape(shape)

def matrix_to_tuple(matrix):
    """
    将矩阵转换为元组
    """
    return tuple(map(tuple, matrix))

def tuple_to_matrix(tup):
    """
    将元组还原成矩阵
    """
    return np.array(tup)

def merge_lists(lists):
    merged_set = set()
    # print(lists)
    for lst in lists:
        # print(lst)
        merged_set.update(lst)  # 使用update()将每个列表中的元素添加到集合中
        # print(merged_set)

    merged_list = list(merged_set)
    return merged_list

def reorder_array(a, b):
    # 根据a中元素顺序重新排序b数组中元素
    b_sorted = [x for x in a if x in b]
    return b_sorted