QPATH.py

from qns.entity.node.app import Application
from topo import WaxManTopology, Node, Channel
from qns.simulator.simulator import Simulator
from qns.simulator.event import func_to_event
from qns.utils.rnd import set_seed
from qns.network.network import QuantumNetwork
import heapq
import numpy as np
from typing import List, Tuple, Union
from qns.network.route import DijkstraRouteAlgorithm
from qns.network.topology.topo import ClassicTopology


def find_link(src: Node, dest: Node, net: QuantumNetwork) -> Union[Channel, None]:
    for channel in net.qchannels:
        if (channel.src == src and channel.dest == dest) or (channel.src == dest and channel.dest == src):
            return channel
    return None


def pur_fidelity(fidelity1: float, fidelity2: float) -> float:
    return (fidelity1 * fidelity2)/(fidelity1 * fidelity2 + (1 - fidelity1) * (1 - fidelity2))


class QPath(Application):
    def __init__(self, network: QuantumNetwork, node: Node, request: Tuple[Node, Node], req_th: int, fth: float = 0.8, q = 0.5):
        super().__init__()
        self.node = node
        self.network = network
        self.request = request  # (src, dest)
        self.req_th = req_th
        self.fth = fth
        self.com = 0  # 资源消耗
        self.th = 0.0  # 吞吐量
        self.total_resurce = 0.0  # 总资源
        self.paths = []  # 储存找到的路径
        self.length = 0.0  # 储存路径总长度
        self.fi = 0.0  # 储存该路径的期望保真度
        self.path_th = []  # 储存该路径的吞吐量
        self.num_pur = []  # 储存纠缠次数
        self.used_capacity = []  # 储存纠缠消耗数
        self.resurce_use_rate = 0.0  # 资源利用率
        self.q = q  # 量子信道的损耗率

    def install(self, node: Node, simulator: Simulator):
        super().install(node, simulator)
        t = simulator.ts
        event = func_to_event(t, self.qpath, by=self)
        self._simulator.add_event(event)

    def calculte_pur_table(self, net: QuantumNetwork):
        # 计算网络中每条链路的提纯表
        for channel in net.qchannels:
            init_fidelity = fidelity = channel.init_fidelity
            pur_table = []
            pur_table.append((fidelity, 0.0))
            for i in range(1, channel.capacity):
                after_pur_fidelity = pur_fidelity(fidelity, init_fidelity)
                fidelity_up = after_pur_fidelity - fidelity
                pur_table.append((after_pur_fidelity, fidelity_up))
                fidelity = after_pur_fidelity
            channel.pur_table = pur_table

    def delete_link(self, net: QuantumNetwork):
        for channel in net.qchannels:
            if channel.pur_table:
                if channel.pur_table[-1][0] < self.fth:
                    channel.capacity = -1  # 删除该链路

    def dijkstra(self, net: QuantumNetwork, src: Node, dest: Node) -> Tuple[float, List[Node]]:
        # 扩展dijkstra算法寻路
        visted = []
        n = len(net.nodes)
        distances = [100000]*n  # 初始化距离
        previous = [-1]*n  # 初始化前驱节点
        # 起始节点
        distances[src.id] = 0

        # 使用最小堆
        heap = [(0, src.id)]  # (log(距离), 节点)

        while heap:
            current_log_dist, current_node_id = heapq.heappop(heap)
            current_node = net.nodes[current_node_id]

            if current_node in visted:
                continue
            visted.append(current_node)
            if current_node == dest:
                break
            for channel in net.qchannels:
                if channel.capacity <= 0:
                    continue
                neighbor = None
                if channel.src == current_node:
                    neighbor = channel.dest
                elif channel.dest == current_node:
                    neighbor = channel.src
                else:
                    continue

                if neighbor in visted or channel.capacity <= 0:
                    continue
                # 计算经过该链路后的距离
                new_log_dist = current_log_dist + 1  # 最小跳数
                if new_log_dist < distances[neighbor.id]:
                    distances[neighbor.id] = new_log_dist
                    previous[neighbor.id] = current_node
                    heapq.heappush(heap, (new_log_dist, neighbor.id))

        # 构建路径
        path = []
        current_node = dest
        if previous[current_node.id] == -1 and current_node != src:
            return []
        while current_node != -1:
            path.append(current_node)
            current_node = previous[current_node.id]
        path.reverse()

        return path

    def find_all_paths_k(self, net: QuantumNetwork, src: Node, dest: Node, k: int) -> List[List[Node]]:
        """
        寻找图中所有从 src 到 dest，且跳数严格为 k 的路径 (不包含环路)
        """
        results = []

        # 1. 预处理：构建邻接表
        adj = {node.id: [] for node in net.nodes}
        # 同时也记录一下信道信息，如果需要判断 capacity
        # 格式: adj[u_id] = [(neighbor_node, channel), ...]
        for channel in net.qchannels:
            if channel.capacity > 0:  # 只考虑有容量的边
                adj[channel.src.id].append((channel.dest, channel))
                adj[channel.dest.id].append((channel.src, channel))

        # 2. 定义 DFS 函数
        # current_node: 当前节点
        # current_path: 当前走过的路径列表
        def dfs(current_node: Node, current_path: List[Node]):
            # 当前跳数 = 路径节点数 - 1
            current_hops = len(current_path)

            # --- 终止条件 1: 达到目标跳数 K ---
            if current_hops == k:
                if current_node == dest:
                    # 找到了一条符合条件的路径，加入结果集 (注意要存副本)
                    results.append(list(current_path))
                return  # 无论是否是终点，达到K跳后都停止继续深入

            # --- 终止条件 2: 超过目标跳数 (剪枝) ---
            if current_hops > k:
                return

            # 遍历当前节点的所有邻居
            for neighbor, channel in adj[current_node.id]:
                # 如果邻居已经在当前路径中，说明形成了环，跳过
                if neighbor not in current_path:

                    # 记录状态
                    current_path.append(neighbor)

                    # 递归搜索
                    dfs(neighbor, current_path)

                    # 回溯 (Backtracking)：探索完该分支后，移除节点，以便探索其他分支
                    current_path.pop()

        # 3. 开始搜索
        # 初始路径包含起点
        dfs(src, [src])

        return results

    def calulate_num_pur(self, net: QuantumNetwork, path: List[Node], fth: float) -> List[int]:
        num_pur = [0]*(len(path)-1)
        while True:
            fidelity = self.calculate_path_fidelity(net, path, num_pur)
            if fidelity >= fth:
                break
            # 计算每条链路增加一次纯化后的增益
            best_increase = 0.0
            best_index = -1
            for i in range(len(path)-1):
                channel = find_link(path[i], path[i+1], net)
                if channel is None:
                    print("Error: Channel not found")
                    exit(1)
                
                if num_pur[i] > len(channel.pur_table) - 1:
                    continue  # 已经达到最大纯化次数，无法再增加
                num_pur[i] = num_pur[i] + 1
                fidelity_after = self.calculate_path_fidelity(net, path, num_pur)
                increase = fidelity_after - fidelity
                if increase > best_increase:
                    best_increase = increase
                    best_index = i
                num_pur[i] = num_pur[i] - 1  # 恢复原状
            if best_index == -1:
                break  # 无法再增加纯化次数
            num_pur[best_index] = num_pur[best_index] + 1

        return num_pur

    def is_path_used(self, path: List[Node], num_pur: List[int]) -> bool:
        for i in range(len(path)-1):
            link = find_link(path[i], path[i+1], self.network)
            if num_pur[i] == -1:
                link.capacity = 0
            elif link.capacity <= (num_pur[i] + 1):
                link.capacity = 0

    def calculate_path_fidelity(self, net: QuantumNetwork, path: List[Node], num_pur: List[int]) -> float:
        fidelity = 1.0
        for i in range(len(path)-1):
            channel = find_link(path[i], path[i+1], net)
            if channel is None:
                print("Error: Channel not found")
                exit(1)
            fidelity = (1/4+3/4*(4*fidelity-1)*(4*channel.pur_table[num_pur[i]][0]-1)/9)
        return fidelity

    def calculate_p_pur_link(self, channel: Channel, num_pur: int) -> float:
        if num_pur == 0:
            return 1.0
        init_fidelity = channel.init_fidelity
        succ = 1.0
        for i in range(num_pur):
            fidelity = channel.pur_table[i+1][0]
            succ *= (fidelity * init_fidelity + (1 - fidelity) * (1 - init_fidelity))
        return succ

    def calculate_p_pur_path(self, net: QuantumNetwork, path: List[Node], num_pur: List[int]) -> float:
        capacity = 10000
        for i in range(len(path)-1):
            channel = find_link(path[i], path[i+1], net)
            if channel is None:
                print("Error: Channel not found")
                exit(1)
            succ_link = self.calculate_p_pur_link(channel, num_pur[i])
            channel_capacity = channel.capacity // (num_pur[i] + 1) * succ_link
            capacity = min(capacity, channel_capacity)
        return capacity

    def calculate_path_capacity(self, net: QuantumNetwork, path: List[Node], num_pur: List[int]) -> int:
        capacity = 10000
        for i in range(len(path)-1):
            channel = find_link(path[i], path[i+1], net)
            if channel is None:
                print("Error: Channel not found")
                exit(1)
            channel_capa = 0

            channel_capa = channel.capacity // (num_pur[i]+1)
            capacity = min(capacity, channel_capa)
        return capacity

    def calculate_path_resource_com_and_delete_link(self, net: QuantumNetwork, path: List[Node], num_pur: List[int], used_capacity: int) -> int:
        com = 0
        tmp_capa1 = 10000
        for i in range(len(path) - 1):
            channel = find_link(path[i], path[i+1], self.network)
            tmp_capa1 = min(tmp_capa1, channel.capacity//(num_pur[i]+1))

        for i in range(len(path)-1):
            channel = find_link(path[i], path[i+1], net)
            if channel is None:
                print("Error: Channel not found")
                exit(1)
            com += (num_pur[i] + 1) * tmp_capa1
            channel.capacity -= (num_pur[i] + 1) * tmp_capa1
        return com

    def is_have_resource(self, path: List[Node], num_pur: List[int]) -> bool:
        for i in range(len(path)-1):
            channel = find_link(path[i], path[i+1], self.network)
            if channel is None:
                print("Error: Channel not found")
                exit(1)
            if channel.capacity < (num_pur[i] + 1):
                return False
        return True

    def qpath(self):
        for link in self.network.qchannels:
            if link.capacity > 0:
                self.total_resurce += link.capacity
        src, dest = self.request
        self.calculte_pur_table(self.network)
        self.delete_link(self.network)

        path = self.dijkstra(self.network, src, dest)
        if path == []:
            return None
        min_cost = len(path)

        max_cost = int(2.5 * len(path))

        heap = []

        for cost in range(min_cost, max_cost + 1):
            path_sets = self.find_all_paths_k(self.network, src, dest, cost)
            if len(path_sets) == 0:
                break
            path_index = 0
            for path in path_sets:
                path_index += 1
                num_pur = self.calulate_num_pur(self.network, path, self.fth)
                path_cost = 0
                if self.is_have_resource(path, num_pur):
                    for i in range(len(path)-1):
                        path_cost += (num_pur[i] + 1)
                    heap.append((path_cost, path, num_pur))

                # 计算吞吐量，并更新网络资源
            heap = sorted(heap, key=lambda x: x[0])
            while heap:
                path_cost, path, num_pur = heap.pop(0)

                if not self.is_have_resource(path, num_pur):
                    continue

                self.is_path_used(path, num_pur)

                self.num_pur.append(num_pur)
                self.paths.append(path)

                fidelity = self.calculate_path_fidelity(self.network, path, num_pur)

                path_capacity = self.calculate_p_pur_path(self.network, path, num_pur)

                capacity = self.calculate_path_capacity(self.network, path, num_pur)

                if capacity <= 0:
                    continue
                self.length += path_capacity
                path_th = path_capacity * self.q**(len(path)-2)  # 考虑中继节点的延迟影响
                self.path_th.append(path_th)
                self.used_capacity.append(path_capacity)
                self.th += path_th
                self.fi += (fidelity * path_th)
                self.com += self.calculate_path_resource_com_and_delete_link(self.network, path, num_pur, path_capacity)
        self.resurce_use_rate = self.com / self.total_resurce if self.total_resurce > 0 else 0
        if self.th > 0:
            self.fi = self.fi / self.th
            self.com = self.com / self.th
        else:
            self.fi = 0.0
            self.com = 0.0
        return self.path_th, self.fi


if __name__ == "__main__":
    end_sim_time = 10
    start_sim_time = 0
    accuracy = 1000000
    set_seed(42)
    nodes_number = 20
    fths = np.arange(0.52, 0.95, 0.1)
    capacity = 40
    th = []
    fi = []
    com = []
    times = []
    num = 10
    for fth in fths:
        topo = WaxManTopology(num_nodes=nodes_number, capacity=capacity)
        t = 0.0
        f = []
        c = []
        for i in range(num):
            print(f"Running simulation for fth = {fth} iteration {i+1}/{num}")
            s = Simulator(start_sim_time, end_sim_time, accuracy=accuracy)
            net = QuantumNetwork(name="network", topo=topo, route=DijkstraRouteAlgorithm(), classic_topo=ClassicTopology.All)

            node = net.nodes[-1]
            src_id = 0
            dest_id = 3
            request = (net.nodes[src_id], net.nodes[dest_id])
            node.add_apps(QPath(network=net, node=node, request=request, req_th=500, fth=fth, q=0.5))
            net.install(s)
            s.run()
            t += node.apps[0].th
            if node.apps[0].th:
                f.append(node.apps[0].fi)
                c.append(node.apps[0].com)
        th.append(t / num)
        fi.append(sum(f) / len(f))
        com.append(sum(c) / len(c))
    print("Final Results:")
    print(f"Fidelities: {fi}")
    print(f"Throughputs: {th}")
    print(f"Average times per simulation (ms): {times}")

    for i in range(len(fths)):
        print(f"fth: {fths[i]:.2f}, Average Fidelity: {fi[i]:.3f}, Average Throughput: {th[i]:.2f}, Consum: {com[i]:.2f}")