#File Name : 图的拓扑排序算法.py
#拓扑排序：在任何一个节点之前，所依赖的节点都做完
#找到所有入度为0的节点，这些节点代表不需要任何的依赖
#删除这些，又有新的入度为0的节点，删掉代表已经做完
#要求有向图且不能有环，有环代表循环依赖

from queue import Queue

class Node(object):
    def __init__(self,value=None):
        self.value = value #节点的值
        self.come = 0 #节点入度
        self.out = 0 #节点出度
        self.nexts = [] #节点的邻居节点
        self.edges = [] #在节点为from的情况下，边的集合
class Edge(object):
    def __init__(self,weight=None,fro,to):
        self.weight = weight # 边的权重
        self.fro = fro # 边的from节点
        self.to = to #边的to节点
class Graph(object):
    def __init__(self):
        self.nodes = {} #图所有节点的集合  字典形式 ：{节点编号：节点}
        self.edges = [] #图的边集合
def creatGraph(matrix):
    # 二维数组matrix [权重  从那个点的值  去哪个点的值]
    graph = Graph()
    # 建立所有节点
    for edge in matrix:
        weight = edge[0]
        fro = edge[1]
        to = edge[2]
        if fro not in graph.nodes:
            graph.nodes[fro] = Node(fro)
        if to not in graph.nodes:
            graph.nodes[to] = Node(to)
    #建立所有的边
        fromNode = graph.nodes[fro]
        toNode = graph.nodes[to]
        newEdge = Edge(weight,fromNode,toNode)
        fromNode.nexts.append(toNode) #加上邻居指向
        fromNode.out+=1 #出度+1
        toNode.come+=1 #to 的入度+1
        fromNode.edge.append(newEdge) #边的集合+1
        graph.edges.append(newEdge)

    return graph

def sortedTopology(graph):
    inmap = {} #统计当前所有节点的入度
    queue_zero_come = Queue() #所有入度为0的点入队列
    for node in graph.nodes.values():
        inmap[node] = node.come
        if node.come==0:
            queue_zero_come.put(node)
    #将入度为0的节点加入到列表中
    res = []
    while queue_zero_come.empty() == False :
        cur = queue_zero_come.get()
        res.append(cur)
        # 消除影响，将后序节点的入度减一
        for next in cur.nexts:
            inmap[next] = inmap[next]-1
            if inmap[next] == 0:
                queue_zero_come.put(next)
    return  res