本文連結：https://blog.csdn.net/qq_43790749/article/details/111770294

一、什麼是拓撲排序在圖論中，拓撲排序（Topological Sorting）是一個有向無環圖（DAG, Directed Acyclic Graph）的所有頂點的線性序列。且該序列必須滿足下面兩個條件：1.每個頂點出現且只出現一次。2.若存在一條從頂點 A 到頂點 B 的路徑，那麼在序列中頂點 A 出現在頂點 B 的前面。有向無環圖（DAG）才有拓撲排序，非DAG圖沒有拓撲排序一說。

例如，下面這個圖：

它是一個 DAG 圖，那麼如何寫出它的拓撲排序呢？這裡說一種比較常用的方法：

於是，得到拓撲排序後的結果是 { 1, 2, 4, 3, 5 }。通常，一個有向無環圖可以有一個或多個拓撲排序序列。二、拓撲排序的應用拓撲排序通常用來“排序”具有依賴關係的任務。比如，如果用一個DAG圖來表示一個工程，其中每個頂點表示工程中的一個任務，用有向邊表示在做任務 B 之前必須先完成任務 A。故在這個工程中，任意兩個任務要麼具有確定的先後關係，要麼是沒有關係，絕對不存在互相矛盾的關係（即環路）。

深度學習的各節點正好構成了這種拓撲關係。因此可以使用拓撲排序的方法對節點進行排序，從而實現自動求導。三、神經網路拓撲圖的構建實現程式碼如下：

import networkx as nxnode_x, node_k1, node_b1 = 'x', 'k1', 'b1'node_k2, node_b2 = 'k2', 'b2'node_linear_01, node_linear_02, node_sigmoid = 'linear_01', 'linear_02', 'sigmoid'node_loss = 'loss'computing_graph = { # represent model    node_x: [node_linear_01],   node_k1: [node_linear_01],   node_b1: [node_linear_01],   node_linear_01: [node_sigmoid],   node_sigmoid: [node_linear_02],   node_k2: [node_linear_02],   node_b2: [node_linear_02],   node_linear_02: [node_loss],}nx.draw(graph, layout, with_labels=True, node_color='red')plt.savefig("linear_simple.png")

視覺化結果如下

四、拓撲排序實現實現程式碼如下：

#使用拓撲排序找到網路節點的前向計算順序（反向傳播反過來就行）def toplogical(graph):    sorted_graph_nodes = []    while graph:         all_nodes_have_inputs = set()        all_nodes_have_outputs = set()        for have_output_node, have_inputs in graph.items():            all_nodes_have_outputs.add(have_output_node)#包括只有輸出的節點 和既有輸入又有輸出的點            all_nodes_have_inputs |= set(have_inputs) #有輸入的點：包括既有輸入和輸出的點 和只有輸入的點（末尾終點）        need_removed_nodes = all_nodes_have_outputs - all_nodes_have_inputs #減去之後留下只有輸出的節點         if need_removed_nodes:            node = random.choice(list(need_removed_nodes))#隨機刪去一個節點            visited_next = [node]            if len(graph) == 1: visited_next += graph[node]  #當最後刪到只留一個節點                #有輸出的節點）的時候，那麼需要把這個節點對應的輸出節點也加上                #否則會漏掉這個點            graph.pop(node)            sorted_graph_nodes += visited_next            for _, links in graph.items():                if node in links: links.remove(node)#如果刪除的節點在別的節點的連線關係內，那麼把他從連線關係裡刪除        else:            break    return sorted_graph_nodesvisited_orde = toplogical(computing_graph)visited_orde#輸出：['b2', 'k1', 'k2', 'b1', 'x', 'linear_01', 'sigmoid', 'linear_02', 'loss']

首先進行前向傳播過程實現實現程式碼如下：

def visited_procedure(graph, posotion, visited_order, step=None, sub_plot_index=None, colors=('red', 'green'), node_size=5):    changed = visited_order[:step] if step is not None else visited_order    before, after = colors    color_map = [after if c in changed else before for c in graph]        nx.draw(graph, posotion, node_color=color_map, with_labels=True, ax=sub_plot_index, node_size=node_size)

前向傳播

dimension = int(len(visited_order) ** 0.5)fig, ax = plt.subplots(dimension, dimension + 1, figsize=(15, 15))for i in range(len(visited_order) + 1):   ix = np.unravel_index(i, ax.shape)   plt.sca(ax[ix])   ax[ix].title.set_text('Feed Forward:{}'.format(i))   visited_procedure(graph, layout, visited_order, step=i, sub_plot_index=ax[ix], node_size=60)plt.savefig("feed_forward.png")

反向傳播

dimension = int(len(visited_order) ** 0.5)fig, ax = plt.subplots(dimension, dimension + 1, figsize=(15, 15))for i in range(len(visited_order) + 1):    ix = np.unravel_index(i, ax.shape)    plt.sca(ax[ix])    ax[ix].title.set_text('Back Forward:{}'.format(i))    visited_procedure(graph, layout, visited_order[::-1], step=i, sub_plot_index=ax[ix], colors=('green', 'red'), node_size=60)plt.savefig("back_foward.png")

根據拓撲排序的結果，那麼就可以對每個模組的輸出結果和梯度大小進行定義，然後根據鏈式法則和相加法則求導， 從而實現前饋過程和反向傳播過程。五、各節點的構建實現程式碼如下

class Node:    def __init__(self, inputs = [],name=None):        self.name = name        self.outputs = []        self.inputs = inputs  #這個node的輸入         for n in self.inputs:            n.outputs.append(self)   #這個輸入的輸出就是這個node本身        self.value = None  #每個節點對應有一個輸出值        self.gradients = {}  #每個節點可能對應有多個輸出，從而對應有多個梯度    def forward(self):        pass    def backward(self):        pass      def __repr__(self):        return '#Node: {}//'.format(self.name)  class Input(Node):    passclass Placeholder(Node):  #佔位符，給x,k或者b,給一個初始值    """"    def __init__(self, name):        Node.__init__(self, name=name)            def forward(self, value=None):        if value: self.value = value  #初始值，或者是更新的權重和偏差值    def backward(self):        self.gradients = {}  #梯度            for n in self.outputs:            self.gradients[self] += n.gradients[self]         #如果這個節點有多個輸出（那就有多個梯度），那就把每個路徑的梯度加起來（輸入是固定的）     """    passclass Linear(Node):    """"    def __init__(self, x=None, weight=None, bias=None, name=None):            Node.__init__(self, [x, weights, bias], name=name)    def forward(self):        self.value = self.inputs[0].value * self.inputs[1].value + self.inputs[2].value       def backward(self):        k, x, b = self.inputs[1], self.inputs[0], self.inputs[2]             for n in self.outputs:            self.gradients[k] += n.gradients[self] * x.value  #n.gradients[self]：輸出點對輸入的梯度            self.gradients[b] += n.gradients[self] * 1  #如果這個節點有多個輸出（那就有多個梯度），那就把每個路徑的梯度加起來（輸入是固定的）            self.gradients[x] += n.gradients[self] * k.value    """    pass   class Sigmoid(Node):    passclass L2_loss(Node):    pass

對這些節點進行排序

NODE_X = Input(name='x')NODE_LINEAR = Linear(name='linear')NODE_K1 = Placeholder(name='k1')NODE_b1 = Placeholder(name='b2')NODE_Loss = L2_loss(name='loss')simple_graph = {   NODE_X: [NODE_LINEAR],   NODE_K1: [NODE_LINEAR],   NODE_b1: [NODE_LINEAR],   NODE_LINEAR: [NODE_Loss]}toplogical(simple_graph) #排列結果：[#Node: k1//, #Node: x//, #Node: b2//, #Node: linear//, #Node: loss//]